Computational Properties of Resolution-based Grounded Semantics

1 Introduction

In the context of Dung's theory of abstract argumentation frameworks [Dung, 1995] a large variety of semantics have been proposed in the literature, their motivation and mutual comparison often being based on informal intuitions and/or specific examples. To overcome this limitation, recently a set of general principles for semantics evaluation and comparison have been identified [Baroni and Giacomin, 2007]. These principles are defined in term of formal properties of the extensions prescribed by a semantics and cover a wide spectrum of notions, ranging from set-theoretical (Imaximality) to topological ones (directionality), and from defense-related concepts (admissibility and reinstatement) to skepticism-related requirements (skepticism adequacy and resolution adequacy). The analysis of a comprehensive set of literature proposals (namely, complete, grounded, stable, preferred, ideal, semi-stable, CF2 and prudent semantics) has shown that none of them is able to respect all the desirable properties altogether. Subsequently, a newly proposed semantics called resolution-based grounded semantics (GR∗ in the following) has been proved [Baroni and Giacomin, 2008] to satisfy all the desiderata of [Baroni and Giacomin, 2007].

While this might be regarded as a significant advantage of GR∗ with respect to other proposals, an analysis of its computational properties is necessary to assess its potential practical relevance and to complete its comparison with other semantics from this important perspective. This paper provides such an analysis: it turns out that GR∗ is satisfactory also from this viewpoint, its complexity in some significant computational problems being lesser or the same with respect to other multiple-status semantics. The paper is organized as follows: Sec. 2 introduces basic concepts, notations, and the considered decision problems, whose complexity analysis is provided in Sec. 3, while conclusions are given in Sec. 4.

2 Notation and Definitions

Definition 1 collects the basic notions we use in the paper.

Definition 1 An argumentation framework (AF) is a pair G = 〈A, R〉, written also G(A, R), where A is a finite set of arguments and R ⊆ A×A is the attack relationship for G. Given S ⊆ A, the complement of S is denoted as S C = A \ S. The restriction of G to S ⊆ A is the AF G↓S = 〈S, R ∩ (S × S)〉.

A pair 〈x, y〉 ∈ R is referred to as 'y is attacked by x' or 'x attacks y'. For S, T subsets of arguments in G(A,R), we say that t ∈ T is attacked by S - written attacks(S, t) - if ∃s ∈ S : 〈s, t〉 ∈ R, and analogously that S is attacked by t - written attacks(t, S) - if ∃s ∈ S : 〈t, s〉 ∈ R. We define S + = {t ∈ A | attacks(S, t)} and S= {t ∈ A | attacks(t, S)}. We use α(S) to denote the set S ∪ S +. For x ∈ A, every argument y in {x}- ∩ {x}+ is involved in a mutual attack with x, i.e. {〈x, y〉, 〈y, x〉} ⊆ R. A set S ⊆ A is conflict-free if ∄x, y ∈ S : 〈x, y〉 ∈ R. Given S, T ⊆ A, S is stable in T with respect to G, denoted as stG(S, T), if ∀x ∈ (T \ S) x ∈ (S ∩ T)+.

An argument x ∈ A is acceptable with respect to a set S ⊆ A if ∀y ∈ {x}- attacks(S, y). The function FG : 2A → 2A which, given a set S ⊆ A, returns the set of the acceptable arguments with respect to S, is called the characteristic function of G. We also use the notation F 1 G (S) ≜ FG(S) and for i > 1, F iG (S) = FG(F i-1 G (S)).

An argumentation semantics S specifies for any AF G(A,R) a set ES(G) ⊆ 2A of extensions, each extension being a set of arguments which can "survive together" the conflict represented by R. A minimal requirement shared by all literature semantics is that any extension is conflict-free.

It is proved in [Dung, 1995] that FG() has a least fixed point, i.e., in the case of a finite AF G(A,R), there is a finite value i for which F iG (∅) = F i+k G (∅) for all k ≥ 0. The grounded extension of G, denoted as GE(G) is the (unique) least fixed point of FG(). We use EGR(G) to denote the set whose (sole) element is GE(G). Letting S = GE(G) we will also denote as CUT(G) the argumentation framework with arguments AS = A \ α(S) and attack relation RS = R∩ (AS ×AS), i.e. CUT(G) = G↓(A\α(S)).

The concept of resolution-based semantics was introduced in [Baroni and Giacomin, 2008] as a mechanism for treating mutual attacks between arguments. Given G(A,R), let MG ⊆ R be the set of mutual attacks in G, i.e. MG = {〈x, y〉 ∈ R | x ̸= y ∧ 〈y, x〉 ∈ R} (note that self-attacking arguments are not considered to define mutual attacks). A (partial) resolution of G is defined by any subset β ⊂ MG for which at most one element of each of the pairs 〈x, y〉, 〈y, x〉 is in β. The AF Gβ arising from the partial resolution β is 〈A, R\β〉. A full resolution is any partial resolution in which exactly one element of each mutual attack occurs, hence the AF Gγ arising from any full resolution γ of G contains no mutually attacking arguments.

To exemplify, the AF G1 shown in Fig. 1 includes only one mutual attack and has two non-empty resolutions (both full), namely {〈c, d〉} and {〈d, c〉}. The AF G2 shown in Fig. 2 includes five mutual attacks. Given that to define any resolution there are three choices for each mutual attack (selecting one of the attacks or neither) and excluding the empty resolution it follows that G2 admits 242 resolutions. On the other hand, to define a full resolution there are two choices for each mutual attack entailing that G2 has 32 full resolutions, including for instance {〈a, b〉, 〈c, a〉, 〈c, b〉, 〈g, f〉, 〈g, h〉}. It is easy to see that GE(G1) = {a} and GE(G2) = {e}, hence CUT(G1) and CUT(G2) are obtained by suppressing arguments and attacks included in the dashed boxes in Figs. 1 and 2 respectively.

The definition of resolution-based grounded semantics GR∗ is based on the grounded extensions of each different full resolution of an AF and selects those ones which are minimal with respect to set inclusion.

Definition 2 Given an AF G(A,R) EGR∗(G) = min { S ⊆ A : GE(Gγ) = S for some full resolution γ of G}.

Our main focus concerns computational properties of GR∗ with respect to the informal questions and corresponding formal decision problems listed below:

• (a) Given G(A,R) and S ⊆ A decide if S is an extension of GR∗ . Formally this relates to the decision problem VERGR∗ with instances 〈G, S〉 accepted if and only if S ∈ EGR∗ (G).
• (b) Given G(A,R) determine whether its resolution-based grounded extensions are exactly the grounded extension of G. Formally this relates to the decision problem COINGR,GR∗ with instances G accepted if and only if EGR(G) = EGR∗(G).
• (c) Given G(A,R) determine whether there is at least one non-empty resolution-based grounded extension of G. Formally this relates to the decision problem NEGR∗ with instances G accepted if and only if EGR∗ (G) ̸= {∅}.
• (d) Given G(A, R) and x ∈ A determine whether x is credulously accepted with respect to EGR∗(G). Formally this relates to the decision problem CAGR∗ with instances 〈G, x〉 accepted if and only if ∃ S ∈ EGR∗ (G) s.t. x ∈ S.
• (e) Given G(A, R) and x ∈ A determine whether x is skeptically accepted with respect to EGR∗(G). Formally this relates to the decision problem SAGR∗ with instances 〈G, x〉 accepted if and only if ∀ S ∈ EGR∗(G) x ∈ S.

We show that while the problems (a), (b) and (c) admit polynomial time decision processes, in contrast (d) is NPcomplete and (e) coNP-complete.

3 Decision properties of EGR∗

3.1 Polynomial time decidable problems

We need several preliminary lemmata concerning properties of GR. First, any argument attacked by the grounded extension receives at least one non-mutual attack from it.

Lemma 1 Given an AF G(A,R), ∀x ∈ (GE(G))+ ∃y ∈ GE(G) : 〈y, x〉 ∈ R∧ 〈x, y〉 /∈ R.

Proof: The proof is based on the property GE(G) = ⋃∞i=1 F iG (∅) [Dung, 1995] and proceeds by induction on i, showing that the thesis holds for any x ∈ (F iG (∅))+. As to the basis step, note that the thesis holds trivially for x ∈ (F 1 G (∅))+ since ∀y ∈ F 1 G (∅) {y}- = ∅. As to the inductive step, consider x ∈ (F i+1 G (∅))+ with i ≥ 1. Then ∃y ∈ F i+1 G (∅) : 〈y, x〉 ∈ R. If 〈x, y〉 /∈ R the thesis obviously holds, otherwise since y ∈ F i+1 G (∅) it holds that x ∈ (F iG (∅))+ and, by the inductive hypothesis, ∃y′ ∈ F iG (∅) : 〈y′ , x〉 ∈ R∧ 〈x, y′ 〉 /∈ R. ✷

The following lemma states that if GE(G) is stable in a set T then the part of GE(G) outside T coincides with the grounded extension of the AF obtained from G by suppressing the arguments in T and those attacked by GE(G) ∩ T .

Lemma 2 Given an AF G(A,R) and a set T ⊆ A such that stG(GE(G), T), it holds that GE(G) ∩ T C = GE(G↓T C \(GE(G)∩T )+ ).

Proof: To shorten notation let T ≜ T C \ (GE(G) ∩ T)+. We will exploit again the property GE(G) = ⋃∞i=1 F iG (∅). Let us first show by induction on i that for any i (F iG (∅) ∩ T C ) ⊆ GE(G↓T ). As to the base case, for any argument x in (F 1 G (∅) ∩ T C ) it holds that {x}- = ∅ in G and hence in any restriction of G including x. It follows that x ∈ T and x ∈ GE(G↓T ). Let us now assume inductively that (F iG (∅) ∩ T C ) ⊆ GE(G↓T ) and show that (F i+1 G (∅)∩T C ) ⊆GE(G↓T ). Letting x ∈ (F i+1 G (∅)∩T C ), we will show that x is acceptable with respect to GE(G↓T ) in G↓T , namely ∀y ∈ ({x}- ∩ T) y ∈ (GE(G↓T ))+. In fact, since x ∈ F i+1 G (∅), it holds that y ∈ (F iG (∅))+. Now, F iG (∅) ⊆ GE(G) and since y /∈ (GE(G)∩T )+ it follows that y ∈ (F iG (∅) ∩ T C )+, which, by the inductive hypothesis, entails y ∈ (GE(G↓T ))+. It follows that x ∈ GE(G↓T ) given the well-known fact that the grounded extension is complete [Dung, 1995], i.e. it contains all arguments acceptable with respect to it.

We have now to prove that GE(G↓T ) ⊆ (GE(G)∩T C ), by showing (again by induction on i) that for any i F iG↓T (∅) ⊆ (GE(G)∩T C ), which, given the definition of T , is obviously equivalent to F iG↓T (∅) ⊆ GE(G). Preliminarily, we show that ∀x ∈ T , ∀y ∈ {x}- such that y /∈ T , y ∈ (GE(G))+ . In fact y /∈ T implies y ∈ (T C )C ∪(T C ∩(GE(G)∩T)+) = T∪ (T C ∩(GE(G)∩T )+ ). We have two possible cases. If y ∈ T then, in particular, y ∈ (T \ GE(G)) since x /∈ (GE(G) ∩ T)+. Then, since stG(GE(G), T) it follows y ∈ (GE(G))+ . If otherwise y ∈ (T C ∩(GE(G)∩T )+) it follows in particular y ∈ (GE(G) ∩ T)+ hence y ∈ (GE(G))+ . Turning to the inductive proof, consider for the base case any x ∈ F 1 G↓T (∅): we have that for any y ∈ {x}- in G it must be the case that y /∈ T, which, as shown above, entails y ∈ (GE(G))+ . It follows that x is acceptable with respect to GE(G), hence x ∈ GE(G). Now assume inductively that F iG↓T (∅) ⊆ GE(G) and consider any x ∈ F i+1 G↓T (∅). For any y ∈ {x}- in G we can consider two cases: if y ∈ T it must be the case that y ∈ (F iG↓T (∅))+, which, by the inductive hypothesis, entails y ∈ (GE(G))+ . Otherwise, y /∈ T which again entails y ∈ (GE(G))+ , as shown above. Summing up, it turns out that x is acceptable with respect to GE(G), hence x ∈ GE(G), which completes the proof. ✷

An equality involving the operations of restriction and resolution of an argumentation framework will also be useful.

Lemma 3 Given an AF G(A,R) and a set T ⊆ A, for any resolution γ of G it holds that Gγ↓T = (G↓T )γ.

We can now show that the grounded extension of a "resolved" AF Gγ can be "decomposed" into the grounded extension of the original AF G and the grounded extension of the AF resulting from applying the same resolution to CUT(G).

Lemma 4 Given an AF G(A,R), for any resolution γ of G it holds that GE(Gγ ) = GE(G) ∪ GE(CUT(G)γ ).

Proof: The fact that for any resolution γ GE(G) ⊆ GE(Gγ) is proved in [Baroni and Giacomin, 2007] in relation with the property of resolution adequacy of GR. Given that GE(Gγ) is conflict-free, it follows that GE(Gγ)∩ α(GE(G)) = GE(G). Clearly GE(G) is stable in α(GE(G)), therefore taking into account Lemma 1 we have also stGγ (GE(Gγ), α(GE(G))). Then, letting AS = A \ α(GE(G)), noting that AS \(GE(Gγ)∩α(GE(G)))+ = AS and using Lemmata 2 and 3, we have GE(Gγ) ∩ AS = GE(Gγ↓AS ) = GE((G↓AS )γ) = GE(CUT(G)γ). Putting together the two (disjoint) pieces we obtain GE(Gγ) = GE(G) ∪ GE(CUT(G)γ ). ✷

The decomposition identified in Lemma 4 can then be applied to the extensions of GR∗ .

Corollary 1 Given an AF G(A,R), EGR∗(G) = {GE(G) ∪ T | T ∈ EGR∗(CUT(G))}.

Proof: Using definitions and exploiting Lemma 4 at the second equality we have: EGR∗(G) = min{S ⊆ A : GE(Gγ) = S for some full resolution γ of G} = min{GE(G) ∪ GE(CUT(G)γ) for some full resolution γ of G} = min{GE(G) ∪GE(CUT(G)γ) for some full resolution γ of CUT(G)} = {GE(G) ∪ T : T ∈ min{GE(CUT(G)γ) for some full resolution γ of CUT(G)}} = {GE(G) ∪ T | T ∈ EGR∗(CUT(G))}. ✷

Corollary 2 For any AF G(A,R), EGR(G) = EGR∗(G) if and only if there is a full resolution γ of CUT(G) such that in CUT(G)γ every argument has at least one attacker.

Proof: From Corollary 1 we have EGR(G) = EGR∗(G) ⇔ EGR∗(CUT(G)) = {∅}, i.e. if and only if there is a full resolution γ of CUT(G) such that GE(CUT(G)γ) = ∅. This entails the conclusion by recalling that GE(G) = ∅ if and only if F 1 G (∅) = ∅ i.e. if and only if ∀ x ∈ A {x}- ̸= ∅. ✷

Corollary 2 provides a condition for COINGR,GR∗ involving the existence of unattacked arguments in all resolutions of CUT(G). While checking the existence of unattacked arguments is easy, using this condition would impose considering all the full resolutions of CUT(G), whose enumeration would give rise to a combinatorial explosion. Next, we will first derive a simpler to check condition, concerning the case of argumentation frameworks consisting of a single stronglyconnected component and then exploit this result in the general case. We recall that the strongly-connected component (SCC) decomposition of G(A,R) partitions A according to the equivalence classes induced by the relation ρ(x, y) defined over A×A so that ρ(x, y) holds if and only if x = y or there are directed paths from x to y and from y to x in G(A,R). We will denote the set of strongly connected components of G as SCCS(G). It is well-known that the graph obtained by considering strongly connected components as single nodes is acyclic. As a consequence, a partial order ≺ over the SCC decomposition {A1, . . . ,Ak} is defined as (Ai ≺ Aj) ⇔ (i ̸= j) and ∃ x ∈ Ai, y ∈ Aj such that there is a directed path from x to y.

Exemplifying SCCs in Figs. 1 and 2, we have SCCS(G1) = {A1, A2, A3, A4} = {{a}, {b, c, d}, {e}, {f}}, with A1 ≺ A2 ≺ A3 ≺ A4 and SCCS(G2) = {A1,A2,A3,A4} = {{a, b, c}, {e}, {d}, {f, g, h}} with A1 ≺ A3 ≺ A4 and A2 ≺ A3 ≺ A4. Considering the restricted AFs obtained by suppressing the elements in the dashed boxes we have SCCS(CUT(G1)) = {A1,A2,A3} = {{c, d}, {e}, {f}}, with A1 ≺ A2 ≺ A3, and SCCS(CUT(G2)) = {A1, A2} = {{a, b, c}, {f, g, h}}, with no precedence relation between A1 and A2.

The following lemma states that given a SCC T and any argument x ∈ T it is possible to find a full resolution γ of G which resolves all mutual attacks involving elements of T such that in Gγ all elements of T , with the only possible exception of x, receive an attack from an element of T itself.

Lemma 5 Given an AF G(A,R) and a SCC T ∈ SCCS(G), for any x ∈ T there is a full resolution γ of G↓T such that in Gγ ∀y ∈ (T \ {x}) attacks(T, y).

Proof: For a generic x ∈ T , define inductively the following sequence of sets: L0 = {x}, Li+1 = L+i \ (⋃ij=0 Lj) for i ≥ 0. Observe that for any y ∈ T ∃i : y ∈ Li. In fact, x ∈ L0 and for any y ̸= x there is a path from x to y, T being a SCC. Letting d be the minimal path length from x to y it is evident that y ∈ Ld. We can now build the full resolution γ as follows: for any mutual attack involving consecutive sets in the sequence insert in γ the attack coming from the set with higher index, namely for any {〈y′ , y′′ 〉, 〈y′′ , y′ 〉} ⊆ R such that y′ ∈ Li, y′′ ∈ Li+1 for some i, let 〈y′′ , y′ 〉 ∈ γ. Then, resolve arbitrarily any other mutual attack. It is evident that for any y ̸= x the path with minimal length from x to y within T is preserved in Gγ, hence attacks(T, y). ✷

We can now obtain the important result concerning an AF consisting of a single SCC anticipated above.

Lemma 6 Given an AF G(A,R) such that |SCCS(G)| = 1, the condition (i) for any full resolution γ of G ∃x such that in Gγ {x}- = ∅ is equivalent to the conjunction (ii) of the following three conditions:

1. ∀x ∈ A, 〈x, x〉 /∈ R;
2. R is symmetric, i.e. 〈x, y〉 ∈ R ⇔ 〈y, x〉 ∈ R;
3. the undirected graph G formed by replacing each (directed) pair {〈x, y〉, 〈y, x〉} with a single undirected edge {x, y} is acyclic.

Proof: We first prove that (i) implies (ii) by showing that if any of the conditions (a-c) is violated then (i) is violated too. If a) does not hold we can apply Lemma 5 to x such that 〈x, x〉 ∈ R and derive the existence of a full resolution γ where ∀y ̸= x {y}- ̸= ∅ while {x}- ⊇ {x}, thus denying (i). If either b) or c) is violated there is a cycle consisting of at least three distinct elements in G. In fact, if R is not symmetric, for any 〈x, y〉 ∈ R such that 〈y, x〉 /∈ R there must be a path from y to x involving at least another distinct argument z, while if the undirected graph contains a cycle it involves necessarily at least three elements. Now it is easy to build a (possibly empty) resolution γ ′ resolving only the mutual attacks, if any, involving elements of the cycle and preserving the existence of such a cycle in Gγ ′ . Therefore Gγ ′ still consists of exactly one SCC. Consider now any argument x in the cycle: clearly {x}- ̸= ∅ in Gγ ′ and this condition will still hold in any full resolution of Gγ ′ . But we can apply now Lemma 5 to x and derive the existence of a full resolution γ ′′ of Gγ ′ where ∀y ̸= x {y}- ̸= ∅. Summing up we have obtained a full resolution γ = γ ′ ∪ γ ′′ of G such that ∀x {x}- ̸= ∅ in Gγ .

Turning to the other direction of the proof, we will now show that the conjunction of a), b) and c) implies (i), by trying to build a full resolution γ such that ∀x ∈ A {x}- ̸= ∅ in Gγ and showing that this is impossible. Since c) holds, the undirected graph G obtained from G is a tree. Let r be the tree root and for any y ̸= r denote as d(y) the length of the unique (simple) path from r to y. Let m = maxy∈A\{r} d(y): for any y such that d(y) = m it is clearly the case that y is directly connected in G with exactly one element z such that d(z) = m- 1. This entails that y can only attack or be attacked by z in G, and, by b), actually both cases hold, i.e. {〈y, z〉, 〈z, y〉} ⊆ R. Then necessarily 〈y, z〉 ∈ γ, otherwise y, not being self-defeating by c), would be unattacked in Gγ. This entails that for any z such that d(z) = m- 1, z does not receive attacks in Gγ from any argument y such that d(y) = m. But now we can iterate the same reasoning on any argument z such that d(z) = m - 1 showing that there is exactly one w such that d(w) = m - 2, {〈z,w〉, 〈w, z〉} ⊆ R and necessarily 〈z,w〉 ∈ γ. Iterating the same reasoning we reach the arguments x such that d(x) = 1 and {〈x, r〉, 〈r, x〉} ⊆ R. For any such argument x it must be the case that 〈x, r〉 ∈ γ (otherwise x would be unattacked in Gγ) but then r is unattacked in Gγ , showing that the construction of the desired γ is impossible. ✷

Lemma 6 has provided three simple topological conditions which, on the basis of Corollary 2, allow to check the condition EGR(G) = EGR∗(G) (while avoiding the enumeration of full resolutions) when |SCCS(G)| = 1. To extend this result to a generic G we need to focus our attention on the strongly connected components which are minimal with respect to ≺ (i.e. do not receive attacks from other strongly connected components) and satisfy conditions (a-c) of Lemma 6.

Definition 3 Given an AF G(A,R), S ∈ SCCS(G) is minimal relevant if S is a minimal element of ≺ and G↓S satisfies conditions (a-c) stated in Lemma 6. The set of the minimal relevant SCCs of G will be denoted as MR(G).

To exemplify, referring to Figs. 1 and 2, it is easy to see that MR(G1) = {{a}}, MR(G2) = {{e}}, MR(CUT(G1)) = {{c, d}}, and MR(CUT(G2)) = {{f, g, h}}.

The following theorem achieves the desired generalization by showing that verifying the coincidence between GR and GR∗ for an AF G is equivalent to checking whether CUT(G) has some minimal relevant component.

Theorem 1 Given an AF G(A,R), EGR(G) = EGR∗(G) ⇔ MR(CUT(G)) = ∅.

Proof: Suppose first EGR(G) = EGR∗(G). By Corollary 2, there is a full resolution γ of CUT(G) such that in CUT(G)γ every argument has at least one attacker. Let S be any SCC

of CUT(G) minimal with respect to ≺. Clearly there is a full resolution γS of CUT(G)↓S such that every element of S has at least one attacker in (CUT(G)↓S)γS and therefore CUT(G)↓S does not satisfy conditions (a-c) of Lemma 6. It follows MR(CUT(G)) = ∅.

Turning to the other direction of the proof, by Corollary 2 it is sufficient to show that there is a full resolution γ of CUT(G) such that in CUT(G)γ every argument has at least one attacker. To build such a γ, consider first any SCC of CUT(G) minimal with respect to ≺. Given the hypothesis MR(CUT(G)) = ∅, by Lemma 6 there is a full resolution γS of CUT(G)↓S such that every element of S has at least one attacker in (CUT(G)↓S)γS . Turning now to the SCCs of CUT(G) which are not minimal with respect to ≺, we can proceed following the (partial) order induced by ≺. In fact, for any such SCC S ′ we can assume inductively that there is a full resolution γ such that for every SCC S ≺ S ′ every element of S has at least one attacker in CUT(G)γ and we need to show that the same holds also for S ′ . Note first that there must be an element x of S ′ which receives at least an attack from an element y of a SCC S such that S ≺ S ′ and that any such attack must be non mutual (otherwise S and S ′ would not be distinct SCCs), hence for any resolution γ 〈y, x〉 /∈ γ. Now, by Lemma 5 we can define a resolution γ ′ ⊆ (S ′ ×S ′ ) such that any argument z ̸= x in S ′ has at least an attacker, while, as shown above, x has at least an attacker in any resolution. Summing up, we have shown a procedure to incrementally build a full resolution γ of CUT(G) such that any element of CUT(G) has at least an attacker in CUT(G)γ, as desired. ✷

Polynomial complexity results for COINGR,GR∗ and NEGR∗ follow directly fromTheorem 1.

Corollary 3 COINGR,GR∗ ∈ P.

Proof: By Theorem 1, to check EGR(G) = EGR∗(G) do the following steps: i) computeGE(G); ii) compute CUT(G); iii) compute the SCC decomposition of CUT(G); iv) identify those SCCs of CUT(G) which are minimal with respect to ≺; v) on each of them check conditions (a-c) of Lemma 6. Each of these steps is known (or easily seen) to belong to P. ✷

Corollary 4 NEGR∗ ∈ P.

Proof: By Corollary 1, EGR∗(G) = {∅} ⇔ GE(G) = ∅ ∧ EGR(G) = EGR∗(G), thus NEGR∗ reduces to checking first NEGR, which is known to belong to P, and then (possibly) COINGR,GR∗ , which belongs to P by Corollary 3. ✷

We now turn to the problem VERGR∗. Preliminarily, we have to identify some quite technical but useful properties of GR and GR∗ in relation with minimal relevant components.

Lemma 7 Given an AF G(A,R) and S ∈ MR(G), it holds that (i) for any full resolution γ of G↓S GE(Gγ↓S) is a stable extension of Gγ↓S and (ii) EGR∗(G↓S) = {T | T is a stable extension of G↓S}.

Proof: Recall first that a stable extension of an AF G(A,R) is a conflict-free set T ⊆ A such that ∀x ∈ (A \ T) attacks(T, x). As for (ii), we show for any S ∈ MR(G) that {GE(Gγ↓S) | γ is a full resolution of G↓S} = {T |

T is a stable extension of G↓S}, and, since no stable extension can be a proper subset of another one, this set turns out to be equal to EGR∗(G↓S). Condition (i) will arise as an intermediate result.

To show {GE(Gγ↓S) | γ is a full resolution of G↓S} ⊆ {T | T is a stable extension of G↓S} we observe first that, by the definition of MR(G), Gγ↓S is acyclic. In fact, it does not contain self-defeating arguments, any cycle of length 2 in G↓S is resolved by γ and no cycles of length > 2 can be present. It is well-known [Dung, 1995] that in an acyclic argumentation framework the grounded extension is also a stable extension, thus GE(Gγ↓S) is a stable extension of Gγ↓S (we have thus proved (i)) and we can observe further that GE(Gγ↓S) is also a stable extension of G↓S since in G↓S it clearly preserves both the properties of being conflict-free and of attacking all other arguments.

To show that {T | T is a stable extension of G↓S} ⊆ {GE(Gγ↓S) | γ is a full resolution of G↓S}, for any stable extension T of G↓S we have to build a full resolution γ of G↓S such that T = GE(Gγ↓S). To obtain such a γ, note that, by the symmetry of G↓S, for any x in T either x is unattacked or is involved in mutual attacks with some other elements y of S and we can include in γ all the pairs of the form 〈y, x〉. It turns out that any element of T is unattacked in Gγ↓S, and, T being a stable extension, that any element y /∈ T is attacked by T . If follows that T = F 1 Gγ↓S (∅) = F iGγ↓S (∅) for any i >= 1 and hence T = GE(Gγ↓S). ✷

To proceed we have now to recall the property of directionality of argumentation semantics, which is known to be satisfied by both GR [Baroni and Giacomin, 2007] and GR∗ [Baroni and Giacomin, 2008]. It corresponds to the intuitive requirement that an argument y may affect another argument x only if there is a directed path from y to x. This can be formalized by referring to sets of arguments not receiving attacks from outside.

Definition 4 Given an AF G(A,R), a non-empty set S ⊆ A is unattacked if and only if ∄x ∈ (A \ S) : attacks(x, S). The set of unattacked sets of G is denoted as US(G).

Definition 5 A semantics S satisfies the directionality criterion if and only if for any AF G(A,R), ∀T ∈ US(G), AES(G, T ) = ES(G↓T ), where AES(G, T ) ≜ {(E∩ T ) | E ∈ ES(G)} ⊆ 2T .

In words, the intersection of any extension prescribed by S for G with an unattacked set T is equal to one of the extensions prescribed by S for the restriction of G to T , and vice versa. The following theorem provides a characterization of the extensions of GR∗ in terms of three (still quite technical) conditions. We omit its lengthy proof (which uses Lemma 7 and directionality of GR and GR∗ ) for space reasons.

Theorem 2 Given an argumentation framework G(A,R) and letting ΠG = ⋃V ∈MR(CUT(G)) V , U ∈ EGR∗(G) if and only if the following conditions hold:

1. U ∩α(GE(G)) = GE(G)
2. ∀M ∈MR(CUT(G)) stCUT(G)(U,M)
3. (U ∩ΠCG ) ∈ EGR∗(CUT(G)↓ΠCG \(U∩ΠG)+).

Algorithm 1 Verifying that U ∈ EGR∗ (G(A, R))

1: procedure GR∗-VER(G(A,R), U) returns boolean 2: S := GE(G) 3: if (U ∩α(S) ̸= S) then 4: return false 5: end if 6: W := ΠG 7: T := U \ S 8: if W = ∅ and T = ∅ then 9: return true 10: end if 11: if W = ∅ and T ̸= ∅ then 12: return false 13: end if 14: if ¬stCUT(G)(T,W) then 15: return false 16: else 17: return GR∗-VER(CUT(G)↓W C \(T∩W)+, (T ∩W C )) 18: end if 19: end

Theorem 3 VERGR∗ ∈ P.

Proof: The proof refers to the recursive Algorithm 1 which is easily seen to correspond to checking whether conditions (a-c) of Theorem 2 hold, while the correctness in the case W = ∅ comes from Theorem 1. First note that every step of Algorithm 1 is in P. In particular, it is well-known that computing GE(G) is in P, as it clearly is also computing α(S). Computing ΠG basically amounts to compute the minimal relevant components of G, a task we have already commented to be in P in Corollary 3. Verifying whether a set is stable in another one and identifying the arguments attacked by a set is linear in the number of attack relations, while all other operations (e.g. those involved in computing CUT(G), CUT(G)↓W C \(T∩W)+ and (T ∩W C )) only require basic set manipulations. It remains to be seen that the recursion is wellfounded and terminates after a polynomial number of calls. To this purpose it is sufficient to observe that at each recursive call an argumentation framework with a strictly lesser number of arguments is considered, since at least the elements of W (which is not empty, otherwise the procedure would terminate) are suppressed. Moreover the procedure clearly terminates without further recursive calls if invoked on G(∅, ∅). It follows that the procedure terminates after a number of calls which is linear in the number of arguments. ✷

Let us exemplify an execution of Algorithm 1 with arguments G = G1 (Fig. 1) and U = {a, d, f}. We get S = {a}, at line 2 and it follows U ∩ α(S) = {a, d, f} ∩ {a, b} = {a} = S. Then the condition of the if statement of line 3 is false and we obtain W = {{c, d}} at line 6 and T = {d, f} at line 7. Since W ̸= ∅ we skip the following if statements and since T is stable in W the condition at line 14 is false and we enter the else branch at line 17. Here we note that W C = {e, f} and (T ∩ W)+ = {c, e} yielding arguments G({f}, ∅) and {f} for the recursive invocation of the procedure. Then we have S = {f} at line 3, W = ∅ at line 6, T = ∅ at line 7, and the procedure returns true at line 9.

In fact, {a, d, f} ∈ EGR∗(G1). Consider instead an execution of Algorithm 1 with arguments G = G2 (Fig. 2) and U = {a, e, g}. We get S = {e} at line 2, and, skipping easy observations, we obtain W = {{f, g, h}} at line 6 and we are led to a recursive invocation with arguments G2↓{a,b,c} and {a}. Now we obtain S = ∅ at line 3, W = ∅ at line 6 and T = {a} at line 7. Then the condition of the if statement of line 11 is satisfied and the procedure returns false. In fact, {a, e, g} /∈ EGR∗(G2).

By the way, it is not difficult to see that EGR∗(G1) = {{a, c, f}, {a, d, f}} and EGR∗ (G2) = {{e, g}, {e, f, h}}.

3.2 Intractable decision problems

Turning to the credulous and skeptical acceptance problems, in contrast to the polynomial time methods identified in subsection 3.1 we have:

Theorem 4

1. CAGR∗ is NP-complete.
2. SAGR∗ is coNP-complete.

Proof: For part (a), that CAGR∗ ∈ NP follows by observing that any instance 〈G(A,R), x〉 can be decided by checking ∃ T ⊆ A : (x ∈ T) ∧ VERGR∗(G, T). By virtue of Theorem 3 this yields an NP algorithm.

For NP-hardness we use a reduction from 3-SAT. Given an instance ϕ(Zn) = C1 ∧ C2 ∧ · · · ∧ Cm of 3-SAT form the instance 〈G(Aϕ,Rϕ), ϕ〉 of CAGR∗ in which,

We claim that there is some T ∈ EGR∗(G) for which ϕ ∈ T if and only if there is a satisfying instantiation of ϕ(Zn).

It is easily seen that EGR(G) = {∅}. Furthermore, noting that MG contains exactly the set of pairs {〈zi, ¬zi〉, 〈¬zi, zi〉 : 1 ≤ i ≤ n} every full resolution of these yields a distinct set in EGR∗(G).

Suppose first that α = 〈α1, α2, . . . , αn〉 describes a satisfying assignment for ϕ(Zn) and consider the full resolution γ(α) given by

The grounded extension of the AF Gγ(α) = 〈Aϕ, Rϕ \ γ(α)〉 contains exactly the arguments { zi : αi = ⊤} ∪ {¬zi : αi = ⊥}∪{ϕ}: each of the literal arguments (i.e. the yi ∈ {zi, ¬zi} selected) has {yi}- = ∅. Furthermore, since α satisfies ϕ, each clause argument Cj attacking ϕ must be attacked by at least one of these literal arguments. It remains only to note that the resulting subset is minimal among the grounded extensions resulting from full resolutions of G.

On the other hand suppose that γ ⊂ MG defines a full resolution for which ϕ is in the grounded extension, T , of Gγ = 〈Aϕ,Rϕ \ γ〉. From ϕ ∈ T , it follows that Cj ̸∈ T for any 1 ≤ j ≤ m, and thus (at least) one literal yj ∈ {zj, ¬zj} among the literals defining Cj must belong to T . It follows that for each clause, Cj = yj,1∨yj,2∨yj,3, γ must contain at least one of the attacks 〈¬yj,k, yj,k〉 in order for yj,k ∈ T to hold. Now defining the instantiation 〈αγ1 , αγ2 , . . . , αγn〉 of Zn via aγi = ⊤ ⇔ 〈¬zj, zj〉 ∈ γ yields a satisfying assignment of ϕ(Zn) as required.

For part (b), to decide SAGR∗(G(A,R), x) by a coNP method, simply involves verifying for every full resolution γ of G, with Tγ the grounded extension of Gγ, that

Again, by virtue of Theorem 3 the required test (for Tγ ∈ EGR∗(G)) can be performed in polynomial time.

For coNP-hardness, we use a similar construction applied to deciding unsatisfiability: this involves the AF of (a) augmented by a single new argument ψ whose sole attacker is ϕ. We omit the straightforward proof that ψ is skeptically accepted if and only if ϕ is unsatisfiable. ✷

4 Conclusions and Further Work

We have investigated the computational properties of GR∗ with reference to a set of decision problems for abstract argumentation semantics: it turns out that some of them (VERGR∗, COINGR,GR∗, NEGR∗) are tractable while others (CAGR∗ ,SAGR∗) are in general not.

Let us discuss this result with respect to complexity properties of other abstract argumentation semantics, focusing first on Dung's traditional grounded (GR), stable (ST) and preferred (PR) semantics. The (unique) grounded extension is known to be computable with a polynomial algorithm, hence all the decision problems considered in this paper are known to be tractable for GR (we have exploited this property in Section 3). On the other hand, the same decision problems are known to be generally intractable for both ST and PR (see in particular [Dimopoulos and Torres, 1996; Dunne and Bench-Capon, 2002; Dunne and Wooldridge, 2009]) with the only exception of VERST ∈ P (also this property has been exploited in Section 3). In particular CAPR, NEPR, and CAST are NP-complete, VERPR is coNPcomplete, SAPR is Πp2 -complete, and SAST is Dp-complete. We can state therefore that GR∗ has better complexity properties than the traditional multiple-status semantics ST and PR. Complexity properties of recently proposed semantics, e.g. ideal, semi-stable or prudent, have not been fully analyzed yet but preliminary non-tractability results exist [Dunne and Wooldridge, 2009]. Actually, as to our knowledge, no other non-trivial multiple-status semantics in the literature has been shown, up to now, to admit polynomial time decision processes (in the general case) for any of the standard decision problems considered here. In this wider perspective one of the main contributions of this paper consists in showing that, differently from what previous literature results could have suggested, argumentation-based reasoning with multiple extensions is not bound to be computationally intractable.

This result has been obtained combining a variety of techniques into an articulated analysis some of whose steps may be interesting on their own. In particular Lemmata 1 and 2 reveal properties of the traditional grounded semantics, while the role played by SCC decomposition confirms the importance of this topological notion in abstract argumentation [Baroni et al., 2005].

Focusing on the specific scope of the paper, GR∗ has been shown to combine its (already known) merits related to principled conceptual requirements with computational advantages which may turn out to be significant for practical applications. This aspect deserves further investigation: defining criteria for matching an abstract argumentation semantics with the requirements of a specific application context is a largely unexplored issue. It is however worth remarking that the results provided in the paper (in particular the procedure summarized in Corollary 3 and Algorithm 1) lend themselves to a straightforward implementation. As the availability of implemented argumentation systems is growing in recent years, integratingGR∗ into one of them, applying it in practical test cases and comparing results with other semantics appear to be feasible and very interesting future activities.

On the theoretical side, among further research directions we mention the identification of families of argumentation frameworks where also CAGR∗ and SAGR∗ are tractable. A preliminary investigation suggests that this is the case for the family of bipartite argumentation frameworks.

Acknowledgments

The authors thank the referees for their valuable comments.