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.
In the last decades of argumentation research, several formalizations have been considered for
suitable abstractions of argumentation processes—Dung’s approach of abstract argumentation
frameworks (AFs) [
In this paper, we use the tools of parameterized complexity analysis and focus on the parameter
of minimum-size deletion-backdoors. The backdoor-concept is used in different contexts such as
constraint satisfaction problems (CSP), satisfiability checking (SAT), answer set programming
(ASP) (see e.g. [
Our main contributions are as follows: (i) we introduce the concept of deletion-backdoors
for SETAFs utilizing the concept of primal-graphs for SETAFs [
We start by recalling the definition of argumentation frameworks with collective attacks
(SETAFs) [
} × A is the attack relation. For an attack (T, h) ∈ R we call T the tail and h the head of the attack. SETAFs (A, R), where for all (T, h) ∈ R it holds that |T | = 1, amount to (standard Dung) AFs. In that case, we usually write (t, h) to denote the set-attack ({t}, h). For S ⊆ A, we say S attacks an argument a ∈ A if there is an attack (T, a) ∈ R with T ⊆ S. We use SR+ t+o denote the set {a | S attacks a} and define the range of S (w.r.t. R), denoted SR⊕ , as the set S ∪ SR .
The well-known notions of conflict and defense from classical Dung-style AFs naturally generalize to SETAFs.
Definition 2. Let SF = (A, R) be a SETAF. A set S ⊆ A is conflicting in SF if S attacks a for some a ∈ S. S ⊆ A is conflict-free in SF, if S is not conflicting in SF, i.e. if T ∪ {h} ̸⊆ S for each (T, h) ∈ R. cf(SF) denotes the set of all conflict-free sets in SF.
The semantics we study in this work are the admissible, complete, preferred, stable, and
semistable semantics, which we will abbreviate by adm, com, pref, and stb, and sem, respectively [
Definition 4. Given a SETAF SF = (A, R) and a conflict-free set S ∈ cf(SF). Then, • S ∈ adm(SF), if S defends itself in SF, • S ∈ com(SF), if S ∈ adm(SF) and a ∈ S for all a ∈ A defended by S, • S ∈ pref(SF), if S ∈ adm(SF) and there is no T ∈ adm(SF) s.t. T ⊃ S, • S ∈ stb(SF), if SR⊕ = A, • S ∈ sem(SF), if S ∈ adm(SF) and ∄T ∈ adm(SF) s.t. T R⊕ ⊃ SR⊕ .
The relationship between the semantics has been clarified in [
stb(SF) ⊆ sem(SF) ⊆ pref(SF) ⊆ com(SF) ⊆ adm(SF) ⊆ cf(SF)
We assume the reader to have basic knowledge in computational complexity theory1, in
particular we make use of the complexity classes P (polynomial time), NP (non-deterministic
polynomial time), coNP, Σ2P, and ΠP. For a SETAF SF = (A, R) and an argument a ∈ A, we
2
consider the standard reasoning problems (under semantics σ ):
• Credulous acceptance Credσ : Is a contained in at least one σ extension of SF?
• Skeptical acceptance Skeptσ : Is a contained in all σ extensions of SF?
The complexity landscape of SETAFs coincides with that of Dung AFs and is depicted in Table 1.
As SETAFs generalize Dung AFs the hardness results for Dung AFs [
For a more fine-grained complexity analysis we also make use of the complexity class FPT
(fixed-parameter tractability): a problem is fixed-parameter tractable w.r.t. a parameter if there
is an algorithm with runtime O( f (p) · poly(n)), where n is the size of the input, p is an integer
describing the instance called the parameter value, and f (· ) is an arbitrary computable function
independent of n (typically at least exponential in p). We also make use of the class XP. A
problem is in XP w.r.t. a parameter if there is an algorithm with runtime O(nO(p)), where n is the
size of the input, and p is the parameter value. We have that P ⊆ FPT ⊆ XP.
1For a gentle introduction to complexity theory in the context of formal argumentation, see [
f
i
b
j
g
c
3. Graph Properties and Backdoors for SETAFs
The underlying structure of SETAFs is a directed hypergraph, which makes it hard to apply
certain notions of graph properties. We can avoid these issues by utilizing “standard” directed
graphs to describe SETAFs, and analyze graph properties (such as backdoors). There are different
such directed graph-representations [
It is easy to see that several SETAFs can map to the same primal graph. However, restrictions on
the primal graph are often useful to obtain computational speedups for otherwise hard problems [
i e f j g c
For this, we need the notion of the projection. Intuitively, a SETAF SF = (A, R) projected to a set of arguments S ⊆ A (we write SF↓S) can be seen as the result of removing the arguments outside of S while retaining as much of the original structure as possible.
Definition 6. Let SF = (A, R) be a SETAF and let C be a class of SETAFs. We call a set B ⊆ A a C-backdoor if SF↓A\B belongs to C, where
SF↓A\B= (A \ B, {(T \ B, h) | (T, h) ∈ R, T \ B ̸= 0/ , h ∈ A \ B}).
We denote the size of a smallest C-backdoor by bdC(SF).
Corollary 7. Let SF be a SETAF.
1. We can recognize whether SF belongs to ACYC or NOEVEN in polynomial time. 2. We can find a NOEVEN-backdoor of size at most p in time |SF|O(p) (or if no such backdoor exists correctly detect so). 3. We can find an ACYC-backdoor of size at most p in time f (p) · poly|SF| (or if no such backdoor exists correctly detect so).
This means, that the fragment ACYC is in principle suitable for FPT algorithms, while for NOEVEN we aim for XP algorithms (however, it is principally possible that faster algorithms for ifnding NOEVEN-backdoors exist).
In this section we tackle the evaluation of backdoors of constant size, i.e., assume we are given a
backdoor, how can we efcfiiently compute the extensions. We adapt the results from [
The basic idea of the backdoor evaluation algorithm is to guess parts of an extension on the arguments in the backdoor, and then cleverly propagate this guess to the rest of the instance. As the remaining instance is even-cycle-free, there are no supportive cycles to consider in the propagation step. Algorithm 1 captures the whole process; in the following we will verify its correctness and give an intuition for each step. If we provide for a SETAF SF a NOEVEN-backdoor B, Algorithm 1 returns a set of admissible candidates pref ∗ (SF, B) for preferred extensions.
Algorithm 1: Computation of pref ∗ (SF, B) 1 pref ∗ (SF, B) ← 0/ ; 2 foreach I ⊆ B do 3 let λ be a partial labeling on B; 4 set λ (a) = in for a ∈ I; 5 set λ (a) = out for a ∈ B \ I; 6 λ ∗ ← propagateIO(SF, λ ); 7 set λ ∗ (a) = und for a ∈ A \ DEF(λ ∗ ); 8 λ † ← propagateU(SF, λ ∗ ); 9 if IN(λ †) ∩ B = I then 10 pref ∗ (SF, B) ← pref ∗ (SF, B) ∪ {IN(λ †)};
We capture the concept of the partial guess by partial labelings (cf. [
Definition 8. Let SF = (A, R) be a SETAF and let X ⊆ A be a set of arguments. A partial labeling is a function λ : X → {in, out, und}. By IN(λ ) we denote the set {a ∈ X | λ (a) = in} (similarly, OUT(λ ), UND(λ )). We write DEF(λ ) to identify the set X . For a set S ⊆ X we fix the corresponding partial labeling on X as λS(a) = ⎧in ⎪ ⎨
if a ∈ S, out if a ∈ SR+, ⎪⎩und else, i.e. a ∈ X \ SR⊕ .
A labeling λ is compatible with a set S ⊆ A if ∀a ∈ DEF(λ ) it holds λ (a) = λS(a).
We consider two “phases” of propagation. In the first, we propagate the in/out labels of the guess as far as possible. The second phase fixes incorrectly labeled arguments and assured admissibility in the generated labeling. We will show that with this approach we can capture all preferred extensions. out d a out h e
i in b out in j f in out g c in (a) (b) in d a in h e in i out b in f in j out in g c out
Definition 9. Let SF = (A, R) be a SETAF and λ be a partial labeling on X ⊆ A. Consider the following propagation rules for λ : 1. set λ ∗ (a) = out if ∃(T, a) ∈ R with T ⊆ IN(λ ∗ ), 2. set λ ∗ (a) = in if ∀(T, a) ∈ R there is a t ∈ T with λ ∗ (t) = out.
We define propagateIO(SF, λ ) as the result of initializing λ ∗ with λ on DEF(λ ), and then exhaustively applying the rules 1. and 2. to each argument a ∈ A \ DEF(λ ).
3. set λ †(a) = und if λ †(a) = in and there is (T, a) ∈ R s.t. ∄t ∈ T : λ †(t) = out, 4. set λ †(a) = und if λ †(a) = out and there is no (T, a) ∈ R s.t. T ⊆ IN(λ †). We define propagateU(SF, λ ) as the result of initializing λ † with λ on DEF(λ ), and then exhaustively applying the rules 3. and 4. to each argument a ∈ IN(λ ) ∪ OUT(λ ).
In the following Lemma 10 we formalize the intuition of propagateIO. We propagate the labels we guessed on B and treat them at this stage as if they are “confirmed”, i.e., whenever we have a reason to assume an argument is defended, we add it (by labeling it in), whenever we have a reason to assume an argument is defeated, we keep track of this fact (by labeling it out). In this stage, no argument will be labeled und. We revisit our running example from Figure 2. Assume we guess λ1(a) = λ1(b) = out for the backdoor {a, b}. The labeling λ 1∗ after exhaustively applying rules 1. and 2. is depicted in Figure 3(a). In general, we will incorrectly label arguments: as can be seen, the argument a is labeled out, but there is no attack towards a that verifies this label. Now assume we guess λ2(a) = λ2(b) = in. One can see in Figure 3(b) that there is a problem with the propagated labeling λ 2∗ : the arguments d and a are both labeled in, effectively causing a conflict. Though we will correct this problem in the second step of the propagation algorithm, we will have to change the label of a from in to und. We will see that we can actually already stop at this point, as we will then compute (a subset of) the extension we get from the guess λ3(a) = out, λ3(b) = in. In the following lemma we establish that we label all arguments a ∈ ER⊕ correctly (i.e., in and out, resp.).
Lemma 10. Let SF = (A, R) be a SETAF, let E ∈ pref(SF), and B ⊆ A a NOEVEN-backdoor for SF. For the input (SF, B) to Algorithm 1, assume in step 2 we choose I = E ∩ B, let λ be the corresponding partial labeling from steps 4 and 5. Set λ ∗ = propagateIO(SF, λ ). Then for each a ∈ A: (a) if λ ∗ (a) = in then a ∈/ ER+, (b) if λ ∗ (a) = out then a ∈/ E, (c) if a ∈/ DEF(λ ∗ ) then a ∈/ ER⊕ , (d) E ⊆ IN(λ ∗ ), and (e) ER+ ⊆ OUT(λ ∗ ).
Proof. We show (a) and (b) by induction on the number of labeled arguments in the construction of λ ∗ . For the base case λ ∗ = λ it is easy to see that all conditions (a) and (b) hold (by assumption we have OUT(λ ) = B \ IN(λ ) = (A ∩ B) \ E). For the step we consider the rules 1. and 2.:
Assume a is labeled via rule 1., i.e. we set λ ∗ (a) = out for some a ∈ A \ DEF(λ ). Clearly, (a) is not violated by labeling a as out, for (b) we show a ∈/ E. Since we invoked rule 1., there is an attack (T, a) ∈ R with T ⊆ IN(λ ∗ ). By our induction hypothesis we know that (a) holds for each t ∈ T , i.e. T ∩ ER+ = 0/. This means E does not defend a against the attack (T, a), and since E ∈ pref(SF), we get a ∈/ E.
Now assume a is labeled via rule 2., i.e. we set λ ∗ (a) = in for some a ∈ A \ DEF(λ ). Clearly, (b) is not violated by labeling a as in, for (a) we show a ∈/ E+. Since we invoked rule 2., for all R attacks (T, a) ∈ R there is some t ∈ T with λ ∗ (t) = out. By our induction hypothesis we know that (b) holds for each such t, i.e. t ∈/ E. Hence, there can be no attack (T, a) with T ⊆ E, i.e., a ∈/ E+.
R
For (c) assume towards contradiction there is an argument a1 ∈ E such that a1 ∈/ DEF(λ ∗ ). If there is no attack (T, a1) ∈ R towards a1, we would have λ ∗ (a1) = in, hence, there is such an attack. Moreover, there is a (T, a1) ∈ R s.t. for no t ∈ T we have λ ∗ (t) = out, otherwise we would have λ ∗ (a1) = in. However, by admissibility of E there is at least one t1 ∈ T ∩ E+. For this t1 we R have t1 ∈ A \ DEF(λ ∗ ), i.e. t1 is unlabeled (the only other option, the label in, violates (b)). Since t1 ∈ E+, there is an attack (S,t1) ∈ R, but since t1 is unlabeled, S ̸⊆ IN(λ ∗ ), i.e., there is an a2 ∈ S
R such that a2 is unlabeled. We have a1 ̸= a2, as this would imply an even-length cycle (a2,t1). As for a2 we can reason in the same way as for a1, we obtain another unlabeled argument t2 ∈ E+, R and eventually a sequence a1,t1, a2,t2, . . . of arguments. However, as SF is finite and all ai are different, eventually there is either (i) an unlabeled argument ak where no attack (Tk, ak) towards ak has an unlabeled tk ∈ Tk, but then λ ∗ (ak) = in, a contradiction, or (ii) an unlabeled argument tk where there is no counter-attack (Sk,tk) with an unlabeled ak+1 ∈ Sk, but then λ ∗ (tk) = out, a contradiction. Hence, no such a1 can exist. Assuming there is an unlabeled argument t1 ∈ ER+ analogously leads to a contradiction.
Finally, from (a) and (c) follows (d) and from (b) and (c) follows (e).
Lemma 11 shows that the procedure propagateU(SF, λ ) is sound. In particular, it is easy to see that any partial labeling λ ∗ with DEF(λ ∗ ) = A that we give as input to propagateU will give us an admissible set (rule 3. removes conflicts and both rules 3. and 4. resolve undefended arguments). An argument is incorrectly labeled in if it is not defended against each attack; it is incorrectly labeled out if it is not attacked from within the set IN(λ ). By exhaustively applying the propagation rules 3. and 4. we fix these incorrect labels. To illustrate this, we revisit our running example. In Figure 3 we see the resulting labelings λ 1∗ , λ 2∗ for the backdoor B = {a, b} for the guesses (a) λ1(a) = λ1(b) = out, and (b) λ2(a) = λ2(b) = in. Following Algorithm 1, in step 7 we set the un-labeled argument to und and compute propagateU for both labelings. In und d a und und und h i e und b out in j f in out g c in (a) (b) und d a und und und h i e und
f b in in j out in g c out
Figure 4 we see the resulting labelings λ1†, λ2†. Our algorithm outputs the sets {c, f , j}, {b, g, j} respectively, and it can be indeed verified that these sets are preferred in SF. Now consider the guess λ3(a) = out, λ3(b) = in. It turns out that λ3† = λ2†: the fact that both labelings result in the same propagation means in particular that there is no preferred extension E where {a, b} ⊆ E, as by trying to construct such an extension in (b) we had to correct the label of a. In general, whenever we re-label one of the guessed in-labels, we can abort the run of the algorithm on this guess and proceed with a different guess, as we will always compute (a superset of) the thereby “missed” set when we start with the corresponding “correct” labeling on the backdoor arguments.
We show in the following Lemma 11 that for every argument a where we fix the label und, a is indeed neither in the corresponding extension nor attacked by it, i.e. a ∈/ ER⊕ . This together with the results of Lemma 10 suffices to show that if we guess correctly, the algorithm computes every preferred extension.
Lemma 11. Let SF = (A, R) be a SETAF, let E ∈ pref(SF), and B ⊆ A a NOEVEN-backdoor for SF. For the input (SF, B) to Algorithm 1, assume in step 2 we choose I = E ∩ B, let λ ∗ be the corresponding propagated partial labeling from step 7 with und labels. Set λ † = propagateU(SF, λ ∗ ). Then E = IN(λ †).
Proof. We first show by induction on the number of re-labeled arguments (i.e., arguments that are labeled und during the construction of λ †) that for each a ∈ A it holds if λ †(a) = und then a ∈ A \ ER⊕ . The base case where λ † = λ ∗ is covered by Lemma 10(c). For the inductive step consider the rules 3. and 4.:
Assume a is re-labeled by rule 3., i.e. we set λ †(a) = und for some a ∈ IN(λ ∗ ). By Lemma 10(a) we know a ∈/ E+, we show a ∈/ E. Since we invoked rule 3., there is (T, a) ∈ R
R s.t. ∄t ∈ T with λ †(t) = out. By induction hypothesis and Lemma 10(a) and (c), this means E+
R ∩ T = 0/, i.e. a is not defended by E against (T, a). By admissibility this means a ∈/ E.
Assume a is re-labeled by rule 4., i.e. we set λ †(a) = und for some a ∈ OUT(λ ∗ ). By Lemma 10(b) we know a ∈/ E, we show a ∈/ E+. Since we invoked rule 4., there is no (T, a) ∈ R
R s.t. T ⊆ IN(λ ∗ ). By induction hypothesis and Lemma 10(c), this means T ̸⊆ E, i.e. a is not attacked by E.
Next, we show IN(λ †) ∈ adm(SF). By E′ we identify the set IN(λ †). Assume towards contradiction there is a conflicting attack (T, h) ∈ R with T ∪ {h} ⊆ E′. However, this means we would re-label h by rule 3., as there is no t ∈ T with λ †(t) = out, a contradiction. Hence, E′ ∈ cf(SF). Now assume towards contradiction there is an undefended argument a ∈ E′, i.e., there is an attack (T, a) ∈ R s.t. for no t ∈ T there is an attack (S,t) ∈ R with S ⊆ E′. As a ∈ E′, there is some t ∈ T where either (i) we set λ ∗ (t) = out during the computation of λ ∗ and did not change the label later, in which case we did not invoke propagation rule 4., and there is indeed an attack (S,t) ∈ R towards t with S ⊆ E′ and a is defended, or (ii) we set λ ∗ (t) = out during the computation of λ ∗ and during the computation of λ † update it to λ †(t) = und, but then if no t′ ∈ T with λ †(t′) = out is left, we would have invoked propagation rule 3. for a and set it to und, and if such a t′ exists where we did not change the label, then a is also defended as in case (i). In all cases we see that indeed a is defended by E′ and can conclude E′ ∈ adm(SF).
Finally, by Lemma 10(d) and the formerly established fact that for each a ∈ A it holds if λ †(a) = und then a ∈ A \ ER⊕ we know also E ⊆ E′. Since E′ ∈ adm(SF) and we assumed E is preferred, we get E = E′.
These correctness results for the propagation procedures are the basis for the main result of this section, namely the efficient computation of preferred extensions if a suitable backdoor is given. Theorem 12. Let C ∈ {NOEVEN, ACYC} be a SETAF class, let SF = (A, R) be a SETAF, and B ⊆ A a C-backdoor for SF with |B| ≤ p. With Algorithm 1 we can enumerate all σ -extensions in time 2p · poly(|SF|) for σ ∈ {pref, stb, sem} on input (SF, B).
Proof. Let E ∈ pref(SF), we show that E is in the output of Algorithm 1, i.e., E ∈ pref ∗ (SF, B). Since in step 2 we try all subsets of B, we will try I = E ∩ B. Lemma 11 ensures E ∈ pref ∗ (SF, B). It remains to show that all steps 3-10 can be done in polynomial time w.r.t. |SF|. It is easy to see that (assuming we use reasonable data structures) this is the case for steps 3-5, 7, 9, and 10. For step 6 and 8 note that each argument is (re)-labeled at most once, and the check for each propagation rule can clearly be carried out in polynomial time. Hence, the overall runtime is 2p · poly(|SF|). Finally, we can then check whether the extensions are (range)-subset-maximal or attack every argument not in them, as all candidates are available. Hence, we can remove those sets that are not preferred/stable/semi-stable.
As we can efficiently enumerate all extensions, also reasoning becomes efficient in this
case. This result also carries over to admissible and complete semantics, as the respective
credulous acceptance problems coincide with preferred semantics, Skeptcom is already possible in
polynomial time and Skeptadm is trivial. We want to highlight that even if we have a
NOEVENbackdoor of size p, there can be up to O(3p) complete extensions. Clearly we cannot enumerate
them with our approach, which is why we capture the preferred extensions (in contrast to the AF
approach [
Corollary 13. Let C ∈ {NOEVEN, ACYC} be a SETAF class, let SF = (A, R) be a SETAF, and B ⊆ A a C-backdoor for SF with |B| ≤ p. Then we can decide the problems Credσ and Skeptσ in time 2p · poly(|SF|) for σ ∈ {adm, com, pref, stb, sem}.
Combining Corollary 7 and Corollary 13, we immediately obtain the following main result that captures finding and exploiting minimal backdoors for SETAFs.
Theorem 14. Let SF be a SETAF and let σ ∈ {adm, com, pref, stb, sem} be a semantics. 1. If bdACYC(SF) ≤ p, we can solve Credσ and Skeptσ in FPT w.r.t. parameter p. 2. If bdNOEVEN(SF) ≤ p, we can solve Credσ and Skeptσ in XP w.r.t. parameter p.
In fact, our algorithm for exploiting a small backdoor that is already given is only in 2p for the
parameter value p, which is an improvement over the existing 3p approach [
Conjecture 1 (Strong Exponential Time Hypothesis (SETH)). For each ε > 0 there is a k such that k-CNF-SAT on n variables and m clauses cannot be solved in O(2(1− ε)n · poly(n + m)) time.
Let p be the parameter for the backdoor size. We will show that any NOEVEN-backdoor evaluation that runs in time O(2(1− ε)p · poly(|F|)) for AFs F would violate SETH and thus imply a major break-through in the development of SAT algorithms.
Theorem 15. Let F = (A, R) be an AF and let C ∈ {NOEVEN, ACYC} and let p the size of the given backdoor. There is no O(2(1− ε)p · poly(|A|)) C-backdoor evaluation algorithm for Credσ for σ ∈ {adm, com, pref, stb, sem} unless SETH is false.
Proof. Given an instance from SETH, i.e. a CNF formula ϕ with n variables and m clauses.
Let X = {x1, . . . , xn} be the set of variables and C = {c1, . . . , cm} be the set of clauses appearing
in ϕ. Consider the standard translation [
Towards, a contradiction let us assume we have a O(2(1− ε)p · poly(|A|)) C-backdoor evaluation algorithm. Then we can decide whether a CNF formula ϕ is satisfiable as follows: We first construct the AF Fϕ (which is polynomial in n + m) and then run the C-backdoor evaluation with backdoor X and return the answer for the credulous decision problem as answer to the satisfiability problem. By assumption the latter step has a running time of O(2(1− ε)n · poly(n + m)). That is, we have a O(2(1− ε)n · poly(n + m)) algorithm for k-CNF-SAT for arbitrary k > 1, which contradicts SETH. ϕ c2 c1
c3 y1 y¯1 y2 y¯2 z1 z¯1 z2 z¯2
In this paper, we have applied the well known concept of backdoors for the first time to argumentation frameworks with collective attacks. Instead of simply adapting previous work in this direction, we came up with a genuinely new approach for computing extensions utilizing backdoors to acyclicity and no-even graphs that shows improved runtime bounds compared to the known algorithms for standard AFs. Moreover, we proved that under some complexity-theoretic assumptions further such improvements are not possible. We focused on graph restrictions on the primal graph rather than the SETAF’s hypergraph structure, as this allows us to exploit established ideas for finding backdoors—the situation for directed hypergraphs is less diverse. Future work includes the implementation of these techniques and the optimization for heuristics to find suitable backdoors.
This research has been supported by the Vienna Science and Technology Fund (WWTF) through project ICT19-065, and by the Austrian Science Fund (FWF) through projects P32830 and Y698.