Abstract
Abstract Argumentation Frameworks (AFs) provide a formal way to represent arguments and their conflicts, but determining sets of acceptable arguments (extensions) is computationally demanding, typically residing in the first or second level of the Polynomial Hierarchy. This paper introduces backdoor-treewidth, a novel hybrid structural parameter that combines the advantages of backdoors and treewidth. By focusing on the treewidth of a backdoor's torso graph, the authors identify new fixed-parameter tractable (FPT) fragments of AFs. Experimental evaluations using the argBTW system show that this approach significantly extends the reach of automated reasoning in cases where traditional structural parameters are prohibitively large.
Introduction
In abstract argumentation, an Argumentation Framework (AF) is a directed graph where nodes represent arguments and edges represent attacks. Reasoning tasks, such as finding stable or complete extensions, are generally NP-hard. To manage this complexity, researchers often rely on structural parameters like treewidth (measuring tree-likeness) or backdoors (small sets of nodes whose removal simplifies the graph). However, many real-world AFs possess both high treewidth and large minimum backdoor sizes, rendering these individual techniques ineffective. This work addresses this limitation by proposing a hybrid parameter: backdoor-treewidth.
The Backdoor-Treewidth Approach
The core idea of backdoor-treewidth ($btw_C$) is to exploit the internal structure of a backdoor set rather than just its size. A set of arguments $B$ is a backdoor into a class $C$ if removing $B$ leaves a graph belonging to $C$ (e.g., an acyclic graph). Instead of requiring $B$ to be small, the authors require that the torso graph of $B$ has small treewidth.
The torso graph represents the backdoor arguments as nodes, with edges added between them if they are connected through a component of the "easy" fragment. This allows for the "hiding" of complex but tractable sub-frameworks within the structure of a tree decomposition, effectively providing a "best of both worlds" guarantee: the backdoor-treewidth is always less than or equal to both the treewidth and the minimum backdoor size.
Technical Implementation and Discovery
The authors developed a complete pipeline, argBTW, to utilize this parameter. Since finding the optimal backdoor-treewidth is NP-hard, the system uses a SAT-based encoding to find backdoors of minimal width incrementally. Once a backdoor is found, the torso graph is decomposed into a tree structure.
A dynamic programming (DP) algorithm then runs over the tree decomposition, reducing the argumentation problem to propositional formulas solved by a specialized model counter (NestHdb). The paper proves that for fragments like acyclic (ACYC) or no-even-cycles (NOEVEN), reasoning for stable and complete semantics is fixed-parameter tractable with respect to backdoor-treewidth.
Experimental Results
The approach was tested on standard ICCMA competition instances and synthetic "extreme" benchmarks designed to have high treewidth and large backdoors. Key findings include:
- Superior Performance: In head-to-head tests, the
argBTWsystem solved significantly more hard instances than solvers relying solely on treewidth (argTW) or backdoors (argBW). - Parameter Efficiency: In over half of the tested instances, backdoor-treewidth was strictly smaller than treewidth, often by more than half.
- Portfolio Effectiveness: A hybrid strategy—starting with a treewidth solver for a short duration and then switching to
argBTW—proved most robust, solving 1,110 out of 1,134 instances in the most challenging test scenarios.
Conclusion and Future Work
Backdoor-treewidth represents a significant advancement in making abstract argumentation tractable. While highly effective for many semantics, the authors noted that preferred semantics remain hard for certain fragments, indicating that the choice of the "easy" class $C$ is critical. Future research will focus on extending these results to more complex semantics and exploring applications in structured argumentation where arguments have internal logical structures.
Summary updated