Augmenting Tractable Fragments of Abstract Argumentation

1 Introduction

The study of arguments as abstract entities and their interaction in form of attacks as introduced by Dung [1995] has become one of the most active research branches within Artificial Intelligence, Logic and Reasoning [Bench-Capon and Dunne, 2007; Besnard and Hunter, 2008; Rahwan and Simari, 2009]. Abstract argumentation provides suitable concepts and formalisms to study, represent, and process various reasoning problems most prominently in defeasible reasoning (see, e.g., [Pollock, 1992; Bondarenko et al., 1997]) and agent interaction (see, e.g., [Parsons et al., 2003]).

A main issue for any argumentation system is the selection of acceptable sets of arguments, called extensions. However, important computational problems such as determining whether an argument belongs to some extension (Credulous Acceptance) or all extensions (Skeptical Acceptance), are intractable (see, e.g., [Dimopoulos and Torres, 1996; Dunne and Bench-Capon, 2002]). The significance of efficient algorithms for these problems is evident. However, a few tractable fragments are known where the acceptance problems can be efficiently solved: the fragments of acyclic [Dung, 1995], symmetric [Coste-Marquis et al., 2005], bipartite [Dunne, 2007], and noeven [Dunne and Bench-Capon, 2002] argumentation frameworks.

∗Research funded by the ERC (COMPLEX REASON, 239962).

It seems unlikely that an argumentation framework originating from a real-world application belongs to one of the known tractable fragments, but it might be "close" to a tractable fragment. In this paper we study the natural and significant question of whether we can solve the relevant problems efficiently for argumentation frameworks that are of small distance to a tractable fragment. One would certainly have to pay some extra computational cost that increases with the distance from the tractable fragment, but ideally this extra cost should scale gradually with the distance.

Results We show that the fragments of acyclic and noeven argumentation frameworks admit an augmentation. In particular, we show that we can solve Credulous and Skeptical Acceptance in polynomial time for argumentation frameworks that are of bounded distance from either of the two fragments. We further show that with respect to the acyclic fragment, the order of the polynomial time bound is independent of the distance, which means that both acceptance problems are fixedparameter tractable (see [Downey and Fellows, 1999]) when parameterized by the distance from the acyclic fragment.

In way of contrast, we show that the fragments of bipartite and symmetric argumentation frameworks do not admit an augmentation. In particular, we show that the problems Credulous and Skeptical Acceptance are already intractable (i.e., (co)NP-hard) for argumentation frameworks at distance 1 from either of the two fragments.

We further show that the parameter "distance to the fragment of acyclic frameworks" is incomparable with previously considered parameters that also admit fixed-parameter tractable argumentation [Dunne, 2007; Dvoˇr´ak et al., 2010]. Hence our approach provides an efficient solution for instances that are hard for known methods.

To get a broad picture of the complexity landscape we take several popular semantics into consideration, namely admissible, preferred, complete, semi-stable and stable semantics (see [Baroni and Giacomin, 2009]).

Our approach is inspired by the notion of "backdoors" which are frequently used in the area of propositional satisfiability (see, e.g., [Williams et al., 2003; Gottlob and Szeider, 2006; Samer and Szeider, 2009]), and also for quantified Boolean formulas and nonmonotonic reasoning [Samer and Szeider, 2009a; Fichte and Szeider, 2011].

2 Preliminaries

An abstract argumentation system or argumentation framework (AF, for short) is a pair (X,A) where X is a finite set of elements called arguments and A ⊆ X × X is a binary relation called attack relation. If (x, y) ∈ A we say that x attacks y and that x is an attacker of y.

An AF F = (X, A) can be considered as a directed graph, and therefore it is convenient to borrow notions and notation from graph theory. For a set of arguments Y ⊆ X we denote by F [Y ] the AF (Y, { (x, y) ∈ A | x, y ∈ Y }) and by F - Y the AF F [X \ Y ].

Example 1. An AF with arguments 1, . . . , 5 and attacks (1, 2), (1, 4), (2, 1), (2, 3), (2, 5), (3, 2), (3, 4), (4, 1), (4, 2), (4, 3), (5, 4) is displayed in Fig. 1.

Let F = (X,A) be an AF, S ⊆ X and x ∈ X. We say that x is defended (in F) by S if for each x′ ∈ X such that (x′ , x) ∈ A there is an x′′ ∈ S such that (x′′ , x′ ) ∈ A. We denote by S+ F the set of arguments x ∈ X such that either x ∈ S or there is an x′ ∈ S with (x′ , x) ∈ A, and we omit the subscript if F is clear from the context. We say S is conflictfree if there are no arguments x, x′ ∈ S with (x, x′ ) ∈ A.

Next we define commonly used semantics of AFs, see the survey of Baroni and Giacomin [2009]. We consider a semantics σ as a mapping that assigns to each AF F = (X, A) a family σ(F) ⊆ 2X of sets of arguments, called extensions. We denote by adm, prf, com, sem and stb the admissible, preferred, complete, semi-stable and stable semantics, respectively. These five semantics are characterized by the following conditions which hold for each AF F = (X, A) and each conflict-free set S ⊆ X.

• S ∈ adm(F) if each s ∈ S is defended by S.
• S ∈ prf(F) if S ∈ adm(F) and there is no T ∈ adm(F) with S ⊊ T .
• S ∈ com(F) if S ∈ adm(F) and every argument that is defended by S is contained in S.
• S ∈ sem(F) if S ∈ adm(F) and there is no T ∈ adm(F ) with S+ ⊊ T +.
• S ∈ stb(F) if S+ =X.

Let F = (X, A) be an AF, x ∈ X and σ ∈ {adm, prf, com, sem, stb}. The argument x is credulously accepted in F with respect to σ if x is contained in some extension S ∈ σ(F), and x is skeptically accepted in F with respect to σ if x is contained in all extensions S ∈ σ(F).

Each semantics σ gives rise to the following two fundamental computational problems: σ-CREDULOUS ACCEPTANCE and σ-SKEPTICAL ACCEPTANCE, in symbols CAσ and SAσ, respectively. Both problems take as instance an AF F = (X,A) together with an argument x ∈ X. Problem CAσ asks whether F is credulously accepted in F, problem SAσ asks whether F is skeptically accepted in F. Table 1, summarizes the complexities of these problems for the considered semantics (see [Dvoˇr´ak and Woltran, 2010]).

Example 2. Consider the AF F from Example 1 and the complete semantics (com). F has two complete extensions ∅ and {1, 3, 5}, see Fig. 1. Consequently, the arguments 1, 3 and 5 are credulously accepted in F and the arguments 2 and 4 are not. Furthermore, because of the complete extension ∅, no argument of F is skeptically accepted.

In the following we list classes of AFs for which CA and SA are known to be solvable in polynomial time [Dung, 1995; Baroni and Giacomin, 2009; Coste-Marquis et al., 2005; Dunne, 2007].

• ACYC is the class of acyclic argumentation frameworks, i.e., of AFs that do not contain directed cycles.
• NOEVEN is the class of noeven argumentation frameworks, i.e., of AFs that do not contain directed cycles of even length.
• SYM is the class of symmetric argumentation frameworks, i.e., of AFs whose attack relation is symmetric.
• BIP is the class of bipartite argumentation frameworks, i.e., of AFs whose sets of arguments can be partitioned into two conflict-free sets.

Lemma 1. The classes ACYC, NOEVEN, SYM and BIP can be recognized in polynomial time (i.e., given an AF F, we can decide in polynomial time whether F belongs to any of the four classes).

Proof. The statement of the lemma is easily seen for the classes ACYC, BIP and SYM. For class NOEVEN it follows by a result of Robertson et al. [1999].

Since the recognition and the acceptance problems are polynomial for these classes, we consider them as "tractable fragments of abstract argumentation."

Parameterized Complexity For our investigation we need to take two measurements into account: the input size n of the given AF F and the distance k of F from a tractable fragment. The theory of parameterized complexity, introduced and pioneered by Downey and Fellows [1999], provides the adequate concept and tools for such an investigation. We outline the basic notions of parameterized complexity that are relevant for this paper, for an in-depth treatment we refer to other sources [Flum and Grohe, 2006; Niedermeier, 2006].

An instance of a parameterized problem is a pair (I, k) where I is the main part and k is the parameter; the latter is usually a non-negative integer. A parameterized problem is fixed-parameter tractable (FPT) if there exist a computable function f such that instances (I, k) of size n can be solved in time f(k) · nO(1) . Fixed-parameter tractable problems are also called uniform polynomial-time tractable because if k is considered constant, then instances with parameter k can be solved in polynomial time where the order of the polynomial is independent of k, in contrast to non-uniform polynomialtime running times such as nO(k) . Thus we have three complexity categories for parameterized problems: (1) problems that are fixed-parameter tractable (uniform polynomial-time tractable), (2) problems that are non-uniform polynomialtime tractable, and (3) problems that are NP-hard or coNPhard if the parameter is fixed to some constant (such as k-SAT which is NP-hard for k = 3).

Backdoors We borrow and adapt the concept of backdoors from the area of propositional satisfiability [Williams et al., 2003; Gottlob and Szeider, 2006; Samer and Szeider, 2009]. Let C be a class of AFs, F = (X, A) an AF, and Y ⊆ X. We call Y a C-backdoor for F if F - Y ∈ C. We write distC(F) for the size of a smallest C-backdoor for F , i.e., distC(F) represents the distance of F from the class C. For an illustration see Fig. 2.

In the following we consider CA and SA parameterized by the distance to a tractable fragment C.

3 Tractability Results

Regarding the fragments of acyclic and noeven argumentation frameworks we obtain the following two results which show that these two fragments admit an amplification.

Theorem 1. The problems CAσ and SAσ are fixedparameter tractable for parameter distACYC and the semantics σ ∈ {adm, com, prf, sem, stb}.

Theorem 2. The problems CAσ and SAσ are solvable in non-uniform polynomial-time for parameter distNOEVEN and the semantics σ ∈ {adm, com, prf, sem, stb}.

The remainder of this section is devoted to a proof of Theorems 1 and 2.

The solution of the acceptance problems involves two tasks: (i) Backdoor Detection: to find a C-backdoor B for F of size at most k. (ii) Backdoor Evaluation: to use the C-backdoor B for F for deciding whether x is credulously/skeptically accepted in F .

For backdoor detection we utilize recent results from fixedparameter algorithmics. For backdoor evaluation we introduce and use the new concept of partial labelings.

Backdoor Detection The following proposition gives an easy upper bound for the complexity of detecting a C-backdoor for any class C of AFs that can be recognized in polynomial time.

Proposition 1. Let C be a class of AFs that can be recognized in polynomial time and F = (X, A) an AF with distC(F) ≤ k. Then a C-backdoor for F of size at most k can be found in time |X|O(k) and hence in non-uniform polynomial-time for parameter k.

Proof. To find a C-backdoor for F of size at most k we simply check for every subset B ⊆ X of size ≤ k whether F - B ∈ C. There are O(|X|k ) such sets and each check can be carried out in polynomial time.

Together with Lemma 1 we obtain the following consequence of Proposition 1.

Corollary 1. Let C ∈ {ACYC, NOEVEN, SYM, BIP} and F = (X,A) an AF with distC(F) ≤ k. Then a C-backdoor for F of size at most k can be found in time |X|O(k) and hence in non-uniform polynomial-time for parameter k.

It is a natural question to ask whether the above result can be improved to uniform-polynomial time. We get an affirmative answer for three of the four classes under consideration.

Lemma 2. Let C ∈ {ACYC, SYM, BIP} and F = (X, A) an AF with distC(F) ≤ k. Then the detection of a C-backdoor for F of size at most k is fixed-parameter tractable for parameter k.

Proof. The detection of ACYC-backdoors is easily seen to be equivalent to the so-called directed feedback vertex set problem which has recently been shown to be fixed-parameter tractable by Chen et al. [2008]. Similarly, the detection of BIP-backdoors is equivalent to the problem of finding an odd cycle traversal which is fixed-parameter tractable due to a result of Reed et al. [2004]. Finally, the detection of a SYMbackdoor set is equivalent to the vertex cover problemwhich is well known to be fixed-parameter tractable [Downey and Fellows, 1999].

We must leave it open whether the detection of NOEVENbackdoors of size at most k is fixed-parameter tractable for parameter k. Since already the polynomial-time recognition of NOEVEN is highly nontrivial, a solution for the backdoor problem seems very challenging. However, it is easy to see that C-backdoor detection, considered as a non-parameterized problem, where k is just a part of the input, is NP-complete for C ∈ {ACYC, NOEVEN, SYM, BIP}. Hence it is unlikely that Lemma 2 can be improved to a polynomial-time result.

Backdoor Evaluation Let F = (X,A) be an AF. A partial labeling of F, or labeling for short, is a function λ : Y →

{IN, OUT, UND} defined on a subset Y of X. Partial labelings generalize total labelings which are defined on the entire set X of arguments [Modgil and Caminada, 2009].

We denote by IN(λ), OUT(λ) and UND(λ) the sets of arguments x ∈ X with λ(x) = IN, λ(x) = OUT and λ(x) = UND respectively. Furthermore, we set DEF(λ) = Y and UD(λ) = X \ DEF(λ) and denote by λ∅ the the empty labeling, i.e., the labeling with DEF(λ∅) = ∅. For a set S ⊆ X we define lab(F, S) to be the labeling of F with respect to S by setting IN(lab(F, S)) = S, OUT(lab(F, S)) = S+ \ S and UND(lab(F, S)) = X \ S+. We say a set S ⊆ X is compatible with a labeling λ if λ(x) = lab(F, S)(x) for every x ∈ DEF(λ).

Let F = (X,A) be an AF and λ a partial labeling of F. The propagation of λ with respect to F, denoted λ∗ , is the labeling that is obtained from λ by initially setting λ∗ (x) = λ(x), for every x ∈ DEF(λ), and subsequently applying one of the following three rules to unlabeled arguments x ∈ X as long as possible.

Rule 1. x is labeled OUT if x has at least one attacker that is labeled IN.

Rule 2. x is labeled IN if all attackers of x are labeled OUT.

Rule 3. x is labeled UND if all attackers of x are either labeled OUT or UND and at least one attacker of x is labeled UND.

It is easy to see that λ∗ is well-defined and unique.

For an AF F, a set B of arguments of F and a partial labeling λ of F we set:

com∗ (F, λ) = { IN(λ∗ ) ∪S | S ∈ adm(F - DEF(λ∗ )) }; com∗ (F,B) = ⋃λ:B→{IN,OUT,UND} com∗ (F, λ).

The following lemma can be established by induction on the number of arguments that have been labeled according to Rules 1-3 (omitted proofs can be found in a longer version of this paper at http://arxiv.org/abs/1104.2842).

Lemma 3. Let F = (X,A) be an AF, λ a partial labeling of F, and S a complete extension that is compatible with λ. Then the propagation λ∗ of λ is compatible with S.

The following lemma can be shown using Lemma 3.

Lemma 4. Let F = (X,A) be an AF and B ⊆ X. Then com(F ) ⊆ com∗ (F, B).

For an AF F we set F ∗ = F - DEF(λ∗∅ ). In other words, F ∗ is obtained from F after deleting all arguments from F that, starting from the empty labeling, are labeled according to the Rules 1-3. We observe that because we start from the empty labeling Rule 3 will not be invoked.

We say a class C of AFs is fully tractable if (i) for every F ∈ C the set adm(F ∗ ) can be computed in polynomial time, and (ii) C is closed under the deletion of arguments, i.e., if F = (X, A) ∈ C and Y ⊆ X, then F - Y ∈ C.

Theorem 3. Let C be a fully tractable class of AFs, F = (X,A) an AF and B a C-backdoor for F with |B| ≤ k. Then the computation of the sets com(F), prf(F), sem(F) and stb(F) can be carried out in time 3k |X|O(1) and is therefore fixed-parameter tractable for parameter k.

Proof. Let C be a fully tractable class of AFs, F = (X, A) an AF and B a C-backdoor for F with |B| ≤ k. We first show that the computation of com(F) is fixed-parameter tractable for parameter k. Let λ be one of the 3k partial labelings of F defined on B. We first show that we can compute com∗ (F, λ) = { IN(λ∗ ) ∪ S | S ∈ adm(F - DEF(λ∗ )) } in polynomial time, i.e., in time |X|O(1) . Clearly, we can compute the propagation λ∗ of λ in polynomial time. Furthermore, because F - B ∈ C (B is a C-backdoor) also F - DEF(λ∗ ) ∈ C; this follows since B ⊆ DEF(λ∗ ) and C is closed under argument deletion since C is assumed to be fully tractable. Moreover, since C is assumed to be fully tractable and F - DEF(λ∗ ) ∈ C, we can compute adm((F - DEF(λ∗ ))∗ ) = adm(F - DEF(λ∗ )) in polynomial time. Consequently, we can compute the set com∗ (F, λ) in polynomial time. Since there are at most 3k partial labelings of F defined on B, it follows that we can compute the entire set com∗ (F,B) in time 3k |X|O(1) .

By Lemma 4 we have com(F) ⊆ com∗ (F,B). Thus we can obtain com(F) from com∗ (F,B) by simply testing for each S ∈ com∗ (F,B) whether S is a complete extension of F. It is a well-known fact that each such a test can be carried out in polynomial time (see e.g. [Dvoˇr´ak andWoltran, 2010]). Hence, we conclude that indeed com(F) can be computed in time 3k |X|O(1) .

For the remaining sets prf(F), sem(F) and stb(F) we note that each of them is a subset of com(F). Furthermore, the extensions in prf(F) are exactly the extensions in com(F) which are maximal with respect to set inclusion. Similarly, the extensions in sem(F) are exactly the extensions in S ∈ com(F) where the set S+ is maximal with respect to set inclusion, and stb(F) are exactly the extensions S ∈ com(F) where S+ = X. Clearly, these observations can be turned into an algorithm that computes from com(F) the sets prf(F), sem(F), stb(F) in polynomial time.

Lemma 5. The classes ACYC and NOEVEN are fully tractable.

Proof. It is easy to see that both classes satisfy condition (ii) of being fully tractable, i.e., both classes are closed under the deletion of arguments. It remains to show that they also satisfy condition (i) of being fully tractable, i.e., for every F ∈ ACYC ∪ NOEVEN = NOEVEN it holds that the set adm(F ∗ ) can be computed in polynomial time. Dunne and Bench-Capon [2001] have shown that if F ∈ NOEVEN and every argument of F is contained in at least one directed cycle, then adm(F) = {∅}. Consequently, it remains to show that if F ∈ NOEVEN then every argument of F ∗ lies on a directed cycle. To see this it suffices to show that every argument x of F ∗ has at least one attacker in F ∗ . Suppose not, i.e., there is an argument x ∈ X \ DEF(λ∗∅ ) with no attacker in F ∗ . It follows that every attacker of x must be labeled and hence x ∈ DEF(λ∗∅ ), a contradiction.

Combining Theorem 3 with Lemma 5 we conclude that if C ∈ {ACYC, NOEVEN} then the backdoor evaluation problem is fixed-parameter tractable parameterized by the size of the backdoor set for the semantics σ ∈ {com, prf, sem, stb}. For the remaining case of admissible semantics, we recall from Table 1 that SAadm is trivial. Furthermore, we observe that every admissible extension is contained in some complete extension, and every complete extension is also admissible. We conclude that an argument is credulously accepted with respect to the admissible semantics if and only if the argument is credulously accepted with respect to complete semantics. Hence, we have shown that backdoor evaluation is also fixed-parameter tractable with respect to admissible semantics. Together with Lemma 2 and Lemma 1 this establishes our main results Theorem 1 and Theorem 2 of this section.λ

Example 3. Consider again the AF F from Example 1. We have observed above that F has an ACYC-backdoor B consisting of the arguments 2 and 4. We now show how to use the backdoor B to compute all complete extensions of F using the procedure given in Theorem 3. Table 2 shows the propagations for all partial labelings of F defined on B together with the set IN(λ∗ ) and for every λ it is indicated whether the set IN(λ∗ ) is a complete extension of F. Because F -B is acyclic it follows that adm(F - DEF(λ∗ )) = {∅} (see the proof of Lemma 5) and hence com∗ (F, λ) = {IN(λ∗ )}. It is now easy to compute com∗ (F,B) as the union of all the sets IN(λ∗ ) given in Table 2. Furthermore, using the rightmost column of Table 2 we conclude that com(F ) = {∅, {1, 3, 5}}, which is in full correspondence to our original observation in Example 2.

4 Hardness Results

The hardness results for CAσ and SAσ are not completely symmetric since for σ ∈ {adm, com} the former problem is NP-complete, the latter is solvable in polynomial time (recall Table 1).

Theorem4. (1) The problemCAσ is NP-hard for AFs F with distBIP(F) = 1 and σ ∈ {adm, com, prf, sem, stb}. (2) The problem SAσ is coNP-hard for AFs F with distBIP(F) = 1 and σ ∈ {prf, sem, stb}.

Proof. (Sketch.) The hardness results follow by reductions from Monotone 3-Satisfiability [Garey and Johnson, 1979] and its complement, similar to reductions used by Dunne [2007]. Because of space restrictions we omit details and only illustrate the constructions in Fig. 3.

Theorem5. (1) The problemCAσ is NP-hard for AFs F with distSYM(F) = 1 and σ ∈ {adm, com, prf, sem, stb}. (2) The problem SAσ is coNP-hard for AFs F with distSYM(F) = 1 and σ ∈ {prf, sem, stb}.

Proof. (Sketch.) We use a reduction from 3-Satisfiability [Garey and Johnson, 1979] and its complementary problem, similar to reductions used by Dimopoulos and Torres [1996]. We illustrate the reductions in Fig. 4.

5 Comparison with other Parameters

In this section we compare our new structural parameters distACYC and distNOEVEN to the parameters treewidth and clique-width that have been introduced to the field of abstract argumentation by Dunne [2007] and Dvoˇr´ak et al. [2010], respectively. Due to space requirements we cannot give the definitions of these parameters and must refer the reader to the above references. The following two propositions show that treewidth and clique-width are both incomparable to our distance parameters.

Proposition 2. There are acyclic and noeven AFs that have arbitrarily high treewidth and clique-width.

Proof. Consider any symmetric AF F of high treewidth or clique-width together with an arbitrary but fixed ordering < of the arguments of F. By deleting all attacks from an argument x to an argument y with y < x we obtain an acyclic AF F ′ whose treewidth and clique-width is at least as high as the treewidth and clique-width of F, but distNOEVEN(F) = distACYC(F ) = 0.

Proposition 3. There are AFs with bounded treewidth and clique-width where distNOEVEN and distACYC are arbitrarily high.

Proof. Consider the AF F that consists of n disjoint directed cycles of even length. It is easy to see that the treewidth and the clique-width of F are bounded by a constant but distNOEVEN(F ) = distACYC(F ) = n.

6 Conclusion

We have introduced a novel approach to the efficient solution of acceptance problems for abstract argumentation frameworks by "augmenting" a tractable fragment. This way the efficient solving techniques known for a restricted fragment, like the fragment of acyclic argumentation frameworks, become generally applicable to a wider range of argumentation frameworks and thus relevant for real-world instances. Our approach is orthogonal to decomposition-based approaches and thus we can solve instances efficiently that are hard for known methods.

The augmentation approach entails two tasks, the detection of a small backdoor and the evaluation of the backdoor. For the first task we could utilize recent results from fixedparameter algorithm design, thus making results from a different research field applicable to abstract argumentation. For the second task we have introduced the concept of partial labelings, which seems to us a useful tool that may be of independent interest. In view of the possibility of an augmentation, our results add significance to known tractable fragments and motivate the identification of new tractable fragments. For future research we plan to extend our results to other semantics and new tractable fragments.