Deletion-Backdoors for Argumentation Frameworks with Collective Attacks

Abstract

Analyzing computational aspects of argumentation has the ultimate goal to find efficient tools to reason in an argumentative setting. In particular, exploiting islands of tractability leads to enhancements of our ability to create such tools. In this work, we identify as such an island of tractability deletion-backdoors for argumentation frameworks with collective attacks (SETAFs). A backdoor is the part of a problem instance, the removal of which leads to a simple structure. If we can find such a backdoor and guess the solution on this part (in the context of argumentation: extensions), the rest of the solution follows almost effortlessly. In terms of complexity analysis, this means for constant backdoor sizes, general argumentation tasks become efficiently solvable—they are fixed-parameter tractable. In this work, we generalize the respective techniques that are known for the special case of Dung-style argumentation frameworks (AFs) and show that they also apply to the more general case of SETAFs. In addition, we can show an improvement in the asymptotic runtime compared to earlier approaches for AFs. Along the way, we point out similarities and interesting situations arising from the more general setting.