On the Complexity of Enumerating the Extensions of Abstract Argumentation Frameworks

1 Introduction

Within the area of Artificial Intelligence, argumentation has become one of the major fields over the last two decades [Rahwan and Simari, 2009; Bench-Capon and Dunne, 2007]. Its most prominent approach is given by abstract argumentation frameworks (AFs) due to Dung [1995], a simple, yet powerful formalism for modeling and deciding problems that are integral to various advanced argumentation systems, see e.g. [Caminada and Amgoud, 2007]. In AFs one abstracts away from the actual contents of arguments and from the concrete reason of conflicts. Many different semantics have been proposed in the literature to define the set of possible extensions of an AF - each representing a coherent set of arguments that "jointly survive" the conflicts given by the AF. In contrast to other communities, the multitude of semantics is seen as a virtue of formal argumentation rather than a weakness and thus a significant amount of research has been done in order to understand particular features of the available semantics, see e.g. [Baroni et al., 2011a; Dunne et al., 2015].

Also several computational problems of AFs have been thoroughly analyzed such as skeptical and credulous reasoning, existence of a non-empty extension, and the verification problem [Dimopoulos and Torres, 1996; Dunne and BenchCapon, 2002; Dvoˇr´ak and Woltran, 2010; Gaggl and Woltran, 2013; Dvoˇr´ak and Gaggl, 2016; Baroni et al., 2011b]. Since these problems tend to be intractable for most semantics, structural restrictions on the AFs have been investigated and their potential for reducing the complexity of the aforementioned problems has been pinpointed [Coste-Marquis et al., 2005; Dunne, 2007]. For an overview on complexity results, see also [Dvoˇr´ak, 2012]. The only complexity analysis we are aware of that goes beyond decision problems is about the counting complexity for AFs [Baroni et al., 2010].

In 2015, the first edition of the International Competition on Computational Models of Argumentation (ICCMA) took place and compared the performance of 18 submitted solvers in terms of skeptical and credulous reasoning, finding one extension, and enumerating all extensions [Thimm et al., 2016]. For the next edition of ICCMA 1 , in total seven semantics will be considered. This not only shows the increasing interest in solvers that are capable of dealing with multiple semantics, but also witnesses that the enumeration problem is indeed considered to be important by the community. However, in contrast to the detailed picture of the complexity of decision problems, the enumeration complexity has been left unexplored so far.

Formal tools for the complexity analysis of enumeration problems date back to [Johnson et al., 1988] and have been further refined in recent years [Strozecki, 2010; Creignou et al., 2013]. In particular, several notions of tractability have been introduced, since a complexity classification of enumeration problems has to take the size of the output into account.

The interest in enumeration problems spans various fields, with some of the most prominent and natural examples coming from the database area: in query answering, one is typically interested in obtaining all answers to a query rather than asking if some answer exists. See [Bulatov et al., 2012; Kazana and Segoufin, 2013; Durand et al., 2014; Kr¨oll et al., 2016] for recent works along this line. Enumeration complexity of graph problems has been studied by Goldberg [1991].

As emphasized above, enumeration is a central task for argumentation systems and, in order to understand their adequacy from a complexity theoretic point of view, a systematic study of the enumeration problem of AFs is needed. It is exactly the goal of this paper to provide such an analysis.

Main Contributions. We investigate the enumeration complexity for a total number of 11 multiple-status semantics and, in addition, consider 5 common structural restrictions on AFs, namely bipartite AFs, symmetric AFs (with or without the additional restriction of irreflexivity), AFs without even cycles, and implicitly also acyclic AFs. Our main result is a complete picture of the complexity of the enumeration problem of AFs for all these semantics for unrestricted AFs and for AFs with the above listed restrictions. We thus provide an exact separation between tractable and intractable enumeration for all the resulting 66 settings.

1 http://www.dbai.tuwien.ac.at/iccma17/

Structure. After this introduction, we recall the most relevant basic definitions on abstract argumentation frameworks and on enumeration problems in Section 2. In Section 3, we present an overview of our results. The proof strategy and the main proof ideas will be presented in Section 4. We conclude with Section 5.

2 Background

Abstract argumentation. We first recall some fundamental concepts related to abstract argumentation frameworks (AFs). This will enable us, in Table 1, to give concise definitions of the various semantics of AFs studied in this work.

Formally, an AF is a directed graph (A,R) where A is a finite set of arguments and R ⊆ A × A is the attack relation.

Given an AF F = (A, R), we define S+ F = {a | ∃s ∈ S : (s, a) ∈ R}, SF = {a | ∃s ∈ S : (a, s) ∈ R} and S⊕ F = S ∪ S+ F . The characteristic function FF of AF F is defined as FF : 2A → 2A with FF (S) = {a ∈ A | {a}-F ⊆ S+ F }.

A full resolution β of F is a subset β ⊆ R such that for any two distinct arguments a, b ∈ A with {(a, b), (b, a)} ⊆ R, exactly one of (a, b) and (b, a) is contained in β. We write γ(F) to denote the set of all full resolutions of F. For S ⊆ A, we write F|S for the restriction of F to S, i.e., F|S = (A ∩ S,R ∩ (S × S)). By SCCs(F) we denote the strongly connected components of the directed graph F. For a ∈ A, let CF (a) denote the strongly connected component containing a, i.e., CF (a) ∈ SCCs(F) unique with a ∈ CF (a). An argument b ∈ A is called componentdefeated by S (in F ), if there exists a ∈ S with (a, b) ∈ R and a ̸∈ CF (b). We write DF (S) to denote the set of arguments component defeated by S.

For a set of sets M, we write min(M) to denote the set of inclusion-minimal sets in M and max(M) for the set of inclusion-maximal sets inM.

The semantics of an AF is defined in terms of coherent sets of arguments (so-called "extensions") that jointly survive the conflicts given by the AF. In this work, we study the following semantics [Dung, 1995; Verheij, 1996; Caminada et al., 2012; Baroni et al., 2011b; 2005; Dvoˇr´ak and Gaggl, 2016], which are defined via the extensions of a given AF F: the set of conflict-free sets cf (F), naive sets naive(F), admissible extensions adm(F), preferred extensions pref (F), stable extensions stable(F), complete extensions comp(F), semi-stable extensions semi(F), stage extensions stage(F), resolution-based grounded extensions resGr(F), stage2 extensions stage2(F), and cf2 extensions cf2(F). The formal definitions are given in Table 1. Note that all semantics are multiple-status, i.e. they provide in general more than one extension. We will also occassionally refer to the grounded extension of an AF F, denoted by grd(F); recall that this ex-

tension is unique for each AF. Formally, grd(F) is given by the subset-minimal complete extension of F .

Several decision problems on AFs have been investigated in the literature. We briefly recall the complexity classification of two of the most prominent decision problems defined as follows: given an AF F , semantics σ, and argument a, decide whether a is contained (i) in at least one σ-extension of F (credulous reasoning); (ii) in all σ-extensions of F (skeptical reasoning). Both problems are tractable for cf and naive, and skeptical reasoning is tractable for comp and trivial for adm (since ∅ ∈ adm(F) for any AF). Credulous reasoning is NP-complete for adm, pref , stable, comp, resGr, and cf2 , and ΣP2 -complete for semi , stage and stage2 . Skeptical reasoning is coNP-complete for stable, resGr, and cf2 and ΠP2 -complete for pref , semi , stage and stage2 ; see e.g. [Dvoˇr´ak, 2012; Dvoˇr´ak and Gaggl, 2016] for further details.

Enumeration problems and their complexity. An enumeration problem is a pair (L, Sol) such that L ⊆ Σ∗ (for an alphabet Σ containing at least two symbols) and Sol : Σ∗ → 2Σ∗ is a function such that for all x ∈ Σ∗ , we have that Sol(x) (the set of "solutions") is finite and Sol(x) = ∅ iff x /∈ L.

An enumeration algorithm A for an enumeration problem P = (L, Sol) is an algorithm which, on input x, outputs exactly the elements from Sol(x) without duplicates. We denote the output of algorithm A on x by A(x).

As far as the computation model of enumeration algorithms is concerned, it is common (cf. [Strozecki, 2010]) to use the RAMmodel. This is motivated by the fact that a RAM can access parts of exponential-size data in polynomial time. As we will see below, this may be needed to efficiently detect (and avoid the output of) duplicates. We restrict ourselves to polynomially bounded RAM machines, i.e., the size of each register is polynomially bounded in the size of the input.

Let A be an enumeration algorithm for some problem P. For an input x, let n = |A(x)|. For 0 ≤ i ≤ n, we define delay(i) as follows: delay(0) ("preprocessing") is the time between the start of the algorithm and the first output (or termination of A, if n = 0). For 0 < i < n, delay(i) is the time between outputting solution i and (i + 1). Finally, delay(n) is the time between the last output and the termination of A.

Several notions of tractability have been proposed in the literature [Johnson et al., 1988; Creignou et al., 2013; Strozecki, 2010]. We recall the two most relevant ones for our purposes below, namely DelayP ("polynomial delay") and OutputP ("output-polynomial time"). Alternatively, the latter class is sometimes referred to as TotalP ("total polynomial time") [Strozecki, 2010].

The classes DelayP and OutputP are defined as follows. Let P = (L, Sol) be an enumeration problem.

• P ∈ OutputP, if there exists an enumeration algorithm A for P and some m ∈ N, such that on every input x, algorithm A terminates in time O((|x| + |Sol(x)|)m).
• P ∈ DelayP, if there exists an enumeration algorithmA for P and some m ∈ N, such that on every input x and for every i ∈ {0, . . . , |Sol(x)|}, delay(i) is in O(|x|m).

Clearly, DelayP ⊆ OutputP holds. This inclusion can be seen as follows: suppose that an enumeration algorithm A for some problem P works with delay O((|x|m)) for some m ≥ 1. Moreover, let N = |Sol(x)|. Then the total time of A to output all solutions for input x is O((N+1)∗|x|m). Recall that the factor (N + 1) rather than N is needed for the time between the last output and termination of A. For N = 0, we have O((N + 1) ∗ |x|m) = O(|x|m) = O((N + |x|)m). For N > 0, the sequence of equalities O((N + 1) ∗ |x|m) = O(N ∗ |x|m) = O((N + |x|)m′ ) with m′ = m + 1 holds, which proves the desired OutputP-membership of P.

Hence, membership in DelayP is the stronger tractability result, which entails membership in OutputP. Conversely, the stronger intractability result is to show that a problem is not in OutputP (under the common assumption that P ̸= NP), which entails non-membership in DelayP.

Note that membership in DelayP does not impose a restriction on the space consumption of an enumeration algorithm. More specifically, a DelayP algorithm may require the construction of an index structure for the already found solutions to avoid the output of duplicates. Hence, if there are exponentially many solutions, this index structure and, therefore, the space consumption of the algorithm may become exponential. We will use the notation DelayPP to refer to the class of enumeration problems which can be enumerated with polynomial delay using only polynomial space. In contrast, when we state DelayP membership of a problem, this means that the enumeration may potentially use exponential space.

3 Overview of Results

The overall goal of this work is to study the complexity of the enumeration problem of abstract argumentation under the various semantics recalled in the previous section. We denote by EnumExt (C, σ) the enumeration problem of σ-extensions of argumentation frameworks in a class C of AFs. An algorithm for the EnumExt(C, σ) problem thus takes F ∈ C as input and outputs σ(F).

Recall from Section 2 that, for most of the semantics σ considered here, the principal decision problems such as credulous and skeptical reasoning are intractable. Consequently, several structural restrictions on the AFs have been studied in the literature. In this work, we study three of the most commonly used subclasses of AFs, namely: the restrictions to bipartite graphs, to symmetric graphs and to graphs without even cycles. As far as the restriction to symmetric graphs is concerned, one has often imposed the further restriction of irreflexivity, see e.g. [Coste-Marquis et al., 2005]. In total, we thus consider the following 5 classes of AFs: AFs without any restrictions (which we will denote as C0), AFs restricted to bipartite graphs (denoted as Cbip), irreflexive, symmetric AFs (denoted as C(ir,sym)), symmetric AFs without irreflexivity restriction (denoted as Csym), and AFs restricted to graphs with no even cycles (denoted as Cnoev).

Our results are summarized in Table 2. Each of the 11 semantics is treated in a separate row. We then have 5 columns for the 5 classes of AFs mentioned above. Table 2 provides a complete complexity classification of the enumeration problem - separating the tractable cases (marked with one of the entries "DelayP", "DelayPP" or "trivial") from the intractable ones (marked with "nOP", which is short for "not in OutputP" under the common assumption that P ̸= NP).

Clearly, if tractability even holds in the unrestricted case (e.g. for cf semantics), then tractability propagates to the restricted cases. Likewise, tractability for AFs in Csym (e.g., for pref semantics) carries over to AFs in C(ir,sym). We mark this with the entry "→" in Table 2. Conversely, if at least one of the restricted cases is intractable, then intractability propagates to the unrestricted case. We mark this with the entry "←". The cases where the structural restriction causes the semantics to have at most one nonempty extension (namely the grounded extension, which can always be computed efficiently) are marked with "trivial".

When filling in the remaining entries in Table 2, we can make use of further dependencies between the different cases.

In particular, under various restrictions, some of the semantics coincide. For instance, in symmetric AFs, every conflictfree extension is admissible. Hence the DelayPP-membership of enumerating admissible extensions in case of symmetric AFs requires no separate proof. Similarly, for bipartite AFs, every preferred extension is stable. Hence, the intractability of enumerating stable extensions in case of bipartite AFs carries over to preferred extensions. To distinguish the entries in Table 2 which require a separate proof from the ones which follow by the collapse of different semantics in some restricted case, we display the former results in boldface.

Note that the restriction to acyclic graphs, which has also been used in the literature to achieve tractability of decision problems, is implicitly covered by our results: First, since acyclic AFs are a special case of AFs without even cycles, all the tractability results of the latter case carry over to acyclic AFs. Moreover, the only intractable cases for AFs without even cycles are stage and stage2 semantics. However, for acyclic AFs, these two coincide with grounded semantics (cf. [Dvoˇr´ak and Gaggl, 2016]), which is a trivially tractable case.

4 Proof Strategy andMain Proof Ideas

Before we start discussing the various entries in Table 2, we define the decision problem ManySol(P), which is strongly related to an enumeration problem P. For an arbitrary enumeration problem P = (L, Sol), it is defined as follows:

• ManySol(P): Given x ∈ L and a positive integer m in unary notation, is |Sol(x)| ≥m?

The following property of the ManySol problem will make it a useful tool for our intractability proofs.

Proposition 1. Let P = (L, Sol) be an enumeration problem. If ManySol (P) ̸∈ P, then P ̸∈ OutputP.

Proof Sketch. Let P = (L, Sol) be an enumeration problem. We prove the contrapositive, i.e., assume that P ∈ OutputP. We have to show that then ManySol (P) ∈ P also holds. By P ∈ OutputP, there is an algorithm A computing A(x) = Sol(x) for any x ∈ L in time p(|x| + |Sol(x)|) for some polynomial p. Let x ∈ L, m ≥ 0. Then we can decide whether |Sol(x)| ≥ m as follows: we run algorithm A on input x for at most s = p(|x| + m) many steps. If the algorithm terminates before s many steps, it outputs Sol(x) and we can check whether |Sol(x)| ≥ m. If A has not terminated after s many steps, we must have that |Sol(x)| > m as A produces an output after p(|x| + |Sol(x)|) computational steps.

Since m is given in unary, the size of the input to the ManySol problem equals |x|+m. Hence, we have shown that ManySol (P) can indeed be decided in polynomial time.

The following decision problem, which is parameterized by a semantics σ, is a special case of ManySol(P), provided that σ is guaranteed to have the empty set as an extension.

• Exists ¬∅ σ : Given an AF F = (A,R), does there exist a set ∅ ̸= S ⊆ A with S ∈ σ(F )?

The following property is an immediate consequence of Proposition 1.

Corollary 1. Let σ be a semantics such that ∅ ∈ σ(F) for all AFs F and let C be a class of AFs. If Exists ¬∅ σ ̸∈ P for AFs restricted to C, then EnumExt(C, σ) ̸∈ OutputP.

We are now ready to present the main proof ideas of the results summarized in Table 2. To this end, we inspect one column of the table after the other.

Unrestricted AFs. First consider the complexity of enumerating conflict-free and naive extensions. For an AF F = (A, R), S ⊆ A is a (maximal) conflict-free set iff it is a (maximal) independent set in the corresponding undirected graph. It was shown in [Johnson et al., 1988] that the maximal independent sets can be enumerated in DelayPP. The same result holds for enumerating all independent sets. Hence, we get EnumExt (C0, σ) ∈ DelayPP with σ ∈ {naive, cf }.

The tractability result for cf2 semantics is obtained by applying standard algorithms for recursively enumerating extensions, see e.g. [Cerutti et al., 2014].

Theorem 1. EnumExt(C0, cf2 ) ∈ DelayPP holds.

Proof Sketch. Let F = (A, R) with strongly connected components S1, . . . , Sm ⊆ A. W.l.o.g., assume that S1, . . . , Sn are the bottom components for some n ≤ m, i.e. strongly connected components without an incoming edge from another component. By the definition of cf2, every naive extension on a bottom component is part of some S ∈ cf2(F). As for each such bottom component the naive extensions are enumerable with polynomial delay using polynomial space, we can fix some naive set Ni ⊆ Si for 1 ≤ i ≤ n. Next we get rid of the arguments of the bottom components S1 = ⋃ Si and the ones which are component defeated by N1 = ⋃ Ni, resulting in the AF F 1 = F |A\(S1∪N1). As before, we choose a naive extension for every bottom component of F 1 , thus again obtaining a union of naive extensions N2. After repeating this process at most k many times for some k ≤ |A|, we have that F k ̸= ∅ and F k+1 = ∅. Then S = ⋃ki=1 Ni is a cf2 extension of F. By selecting a single different naive extension of a bottom component of some F j , the same procedure obtains an S′ ∈ cf2(F) with S′ ̸= S. Through backtracking, we can thus enumerate all extensions S ∈ cf2(F) with polynomial delay using polynomial space.

It only remains to establish the tractability of resGr and the intractability of adm semantics, since for all further semantics, the intractability in the unrestricted case carries over from the intractability of some restricted case.

For resGr , an enumeration algorithm is given in [Baroni et al., 2011b, Algorithm 2]. This algorithm can be refined to an algorithm with polynomial delay using polynomial space by making use of an algorithm for maximal independent sets and backtracking. For adm, we recall that the Exists ¬∅ adm problem is NP-complete, which follows from results in [Dimopoulos and Torres, 1996]. Hence, by Corollary 1, we may conclude that EnumExt (C0, adm) ̸∈ OutputP holds unless P = NP.

Bipartite AFs. We first inspect the tractability for adm semantics. It is easy to verify that, given an admissible set S in a bipartite AF F = (A1 ∪ A2, R), the restrictions S ∩ A1

and S ∩ A2 are also admissible. The crucial properties of bipartite AFs used here are that, for i ∈ {1, 2}, all subsets of Ai are conflict-free and all defenders of an argument in Ai must also be in Ai. To compute all admissible sets of F, we have to find the sets Ai of admissible subsets of Ai for each i ∈ {1, 2} separately and then find all conflict-free combinations S1 ∪ S2 with Si ∈ Ai. For the computation of Ai, the following lemma, which holds for arbitrary AFs, is crucial.

Lemma 1. Given an AF (A, R) and a conflict-free set M ⊆ A, enumerating all admissible subsets S ⊆ M is in DelayP.

Proof Sketch. It is shown in [Dunne et al., 2013, Lemma 1] that, given a conflict-free set M ⊆ A, there exists a unique maximal admissible subset S∗ ⊆ M, which can be computed in polynomial time. Then the desired algorithm for enumerating all admissible subsets of M works as follows: we maintain two queues P and Q of admissible sets, such that P contains the already printed and processed ones while Q contains those which have been found but not printed and processed yet. Initially, P = ∅ and Q = {S∗ }. As long as Q is not empty, we take an element from Q, output it and search recursively for admissible subsets of S \ {x} for each x ∈ S. For every admissible set S′ thus found, we check if S′ ̸∈ P ∪Q and, if so, add it to Q.

The correctness of this algorithm is easy to verify. The polynomial delay can be seen as follows: the already found extensions have to be organized in some index structure. In principle, any balanced search tree formalism (e.g., AVL trees) can be used. Yet simpler, we can arrange extensions of an AF with n arguments in a binary tree of depth n where each leaf node (or, equivalently, each path from the root to a leaf) represents an already found extension. A node at depth i is either labelled with "ai in" or with "ai out" depending on whether argument ai is contained in the extension or not. Checking if the current extension is new and extending the tree in case it is, can thus be done in time O(n).

Note that Lemma 1 only states DelayP membership rather than DelayPP membership. Indeed, the algorithm in the proof of Lemma 1 crucially depends on an index structure of all the already found solutions to avoid the output of duplicates. Hence, if there are exponentially many solutions, the space requirement of the algorithm becomes exponential as well.

Theorem 2. EnumExt(Cbip, adm) ∈ DelayP holds.

Proof Sketch. Consider a bipartite AF F = (A1 ∪ A2,R). Then each of the two sets Ai is conflict-free. As mentioned in the proof of Lemma 1, we can thus compute the unique maximal admissible set S∗ i ⊆ Ai efficiently by applying [Dunne et al., 2013, Lemma 1]. In principle, using our Lemma 1 above, we could compute with polynomial delay the set Ai of all admissible subsets of Ai and finally check each pair (S1, S2) ∈ A1 ×A2 for conflict-freeness to find and output all admissible sets S1 ∪ S2 with elements from both sides A1 and A2. However, the challenge with bipartite AFs is that there may exist exponentially many pairs (S1, S2) but only a small number of them yields a conflict-free set S1 ∪ S2.

Hence, we have to be careful to get an overall enumeration algorithm which works in polynomial delay. The solution to overcome this problem is an interleaved output of the admissible subsets Si of Ai with i ∈ {1, 2} and of admissible subsets of the form S1 ∪ S2:

Whenever an admissible subset S1 ⊆ A1 is processed, we search recursively for the maximal admissible subsets of S1 \ {x} for each x ∈ S1 as in the proof sketch of Lemma 1 and, moreover, we also search for all admissible subsets S2 ⊆ A2 such that S1 ∪ S2 is conflict-free. For the latter task, we first compute M ⊆ A2 containing all arguments that have no conflict with S1. Clearly M is conflict-free, since it only has arguments from one side of the bipartite AF. We can then find all admissible subsets S2 ⊆ M with polynomial delay by Lemma 1. For every S2 thus found, we output S1 ∪S2. Note that in this way also all admissible subsets S1 ⊆ A1 are output (namely when we combine S1 with S2 = ∅) and also admissible subsets S2 ⊆ A2 are output (namely when we combine S2 with S1 = ∅), since ∅ is guaranteed to be among the admissible subsets of A1 and A2, respectively.

Before we switch to intractability, we recall that the stable, stage, semi , and pref semantics all coincide for bipartite AFs. This follows from the fact that bipartite AFs are oddcycle free, hence stable and pref coincide; this also guarantees the existence of a stable extension which implies that stable, semi-stable and stage extensions coincide. Hence, to prove the intractability results of bipartite AFs in Table 2, it suffices to consider the stable, stage2 , and comp semantics. To this end, we first recall the following definition. Let G = (V,E) be a directed graph and K ⊆ V . Then K is called a kernel of G, if K is an independent dominating set, i.e. the nodes in K are pairwise non-adjacent and for every v ∈ V \K there exists a k ∈ K with (k, v) ∈ E. As shown by Dimopoulos et al. [1997] it is NP-complete to decide whether a given graph has more than two kernels and that this problem remains NP-complete even if the graphs are restricted to bipartite graphs with a single SCC. Building upon this result, we prove the following intractability results for bipartite AFs.

Theorem 3. Let σ ∈ {stable, comp, stage2}. Then EnumExt (Cbip, σ) ̸∈ OutputP holds unless P = NP.

Proof Sketch. "stable". Clearly, for an AF F = (A,R), S ⊆ A is a stable extension iff it is a kernel in the corresponding graph. This means that for the class Cbip of AFs and stable semantics, the ManySol problem is NP-hard. Hence EnumExt (Cbip, stable) ̸∈ OutputP by Proposition 1.

"stage2". Since stable and stage semantics coincide for bipartite AFs, the enumeration of stage extensions shares the hardness of stable ones. Since the underlying NP-hardness results for kernels holds even for bipartite graphs with a single SCC, we also have EnumExt (C, stage2 ) ̸∈ OutputP.

"comp". We can use the reduction of the NP-hardness proof in [Dimopoulos et al., 1997] to show that for the class Cbip of AFs and comp semantics, the ManySol problem is NP-hard. Instead of kernels, satisfying truth assignments correspond to non-trivial complete extensions, which are subsets of the nontrivial kernels of the bipartite graph.

Symmetric AFs. In symmetric AFs, every argument defends itself against any attacks. Hence, cf and adm semantics coincide and so do naive and pref semantics. The DelayPP membership of cf and naive semantics thus carries over to adm and pref semantics. For cf2 , and resGr, DelayPP membership carries over from the unrestricted case. For the remaining semantics, no collapse with an already shown tractable case occurs in case of symmetric AFs. Indeed, for the following semantics, we can show intractability:

Proof Sketch. In [Dvoˇr´ak, 2012] it was shown that for an arbitrary AF F one can construct in polynomial time a symmetric AF F ′ with self-loops such that stage(F ) = stage(F ′ ) = semi(F ′ ) and stable(F) = stable(F ′ ). In other words, the problem of enumerating the stage extensions of an arbitrary AF F can be reduced to the problem of enumerating the stage (resp. semi-stable) extensions of a symmetric AF F ′ ∈ Csym. Likewise, the problem of enumerating the stable extensions of an arbitrary AF F can be reduced to the problem of enumerating the stable extensions of a symmetric AF F ′ ∈ Csym. This means that EnumExt(Csym, σ) ̸∈ OutputP holds for σ ∈ {stage, stable, semi } unless P = NP.

For stage2, we observe that the aforementioned reduction from F to F ′ preserves strong connectivity. Using the AF F to be constructed in the proof of Theorem 7, we have that stage(F) = stage(F ′ ) = stage2(F ′ ), thus proving intractability also for EnumExt (Csym, stage2 ).

It only remains to consider comp semantics. To study this case, we define the following decision problem:

• ExtSolComplete Given an AF F = (A,R) and sets of arguments I,O ⊆ A, is there some S ∈ comp(F) with I ⊆ S and O ∩ S = ∅?

While this problem is intractable for arbitrary AFs, it can be shown tractable for comp semantics over symmetric AFs.

Lemma 2. ExtSolComplete is in P for symmetric AFs.

Proof Sketch. Intuitively, I (resp. O) contains the arguments that we want to be in (resp. out). A polynomial time algorithm A for solving this decision problem works as follows: On input F = (A, R) and I, O ⊆ A, we first check whether I ∈ cf (F). If this is not the case then A ends in a rejecting state; otherwise, we compute the minimal fixpoint S of FF such that I ⊆ S holds. Since, for symmetric AFs, conflict-free sets are admissible, S is the minimal complete set containing I. So A accepts the input iff S ∩ O = ∅.

Similarly to algorithms in [Creignou and H´ebrard, 1997] and [Kr¨oll et al., 2016], we can use algorithm A for ExtSolComplete from Lemma 2 to design an efficient enumeration algorithm for complete extensions on symmetric AFs.

Theorem 5. EnumExt(Csym, comp) ∈ DelayPP holds.

Proof Sketch. Let F = (A, R) with A = {a1, . . . , an}. The idea of the enumeration algorithm is the following: We extend single arguments to complete extensions successively, by repeatedly adding arguments to such partial extensions as well as fixing a set of arguments that cannot be added to such partial extensions. Starting with the argument a1, the enumeration algorithm first obtains the answers of algorithm A from Lemma 2 on input (F, {a1}, {}) and (F, {}, {a1}). For every input Ω = (F, IΩ, OΩ) accepted by A we add a2 to either IΩ or OΩ resulting in two new inputs Ω1 = (F, IΩ ∪ {a2}, OΩ) and Ω1 = (F, IΩ,OΩ ∪ {a2}). Repeating this n times, we obtain all complete extensions IΩ for inputs Ω of A such that A accepts and IΩ ∪ OΩ = {a1, . . . , an}. By a depth-first computation and backtracking, this enumeration can be done with polynomial delay using polynomial space.

Irreflexive, symmetric AFs. We now consider AFs which are symmetric and irreflexive. Clearly, all tractability results carry over from symmetric AFs. It remains to consider those cases, for which the enumeration problem of symmetric AFs with self-loops is intractable. The restriction to irreflexive, symmetric AFs implies that stable and preferred semantics coincide [Coste-Marquis et al., 2005]. Hence, DelayPPmembership of pref semantics carries over to stable, and consequently to semi and stage semantics (since we are guaranteed that a stable extension exists). Finally, stage2 and stage extensions coincide, since in symmetric AFs different components are not connected at all. Hence, we also have DelayPP-membership for stage2 semantics.

No-even AFs. Let F = (A, R) be an AF without even cycles. As shown in [Dunne and Bench-Capon, 2001], the grounded extension S ⊆ A is the only complete (and also preferred and semi-stable) extension and is computable in polynomial time. Moreover, S is the only candidate for a stable extension and we can test whether S ∈ stable(F ) efficiently. Hence, for any of the semantics stable, pref , comp, and semi , the enumeration problem becomes trivial. It remains to consider the adm, stage, and stage2 semantics. Below, we show that adm leads to tractability while the latter two lead to intractability.

Theorem 6. EnumExt(Cnoev, adm) ∈ DelayP holds.

Proof Sketch. For AF F ∈ Cnoev, comp and grd semantics coincide. Hence, the grounded extension of F (which can be computed efficiently) is the unique maximal admissible set of F. In particular, it is conflict-free and contains all admissible sets of F as subsets. By Lemma 1, we can enumerate all admissible sets S ⊆ M with polynomial delay.

Theorem 7. Let σ ∈ {stage, stage2}. Then EnumExt (Cnoev, σ) ̸∈ OutputP holds unless P = NP.

Proof Sketch. By Proposition 1, it suffices to show that the ManySol problem of stage and stage2 extensions is NPhard on AFs without even cycles. The proof is by reduction from SAT. For stage semantics, we can take over almost literally the construction from [Dvoˇr´ak, 2012, Theorem 30] (which, in turn, uses ideas similar to [Dvoˇr´ak et al., 2014, Proposition 13]). The only modification needed is to delete an auxiliary argument q from the AF constructed there.

Apart from a self-cycle, the resulting AF is acyclic, i.e., every argument builds its own SCC. The main task to prove NP-hardness also for stage2 semantics is a general one: we are given an acyclic AF and we have to extend it in such a way that the resulting AF consists of a single SCC. The challenge here is that we must not introduce an even cycle.

Our construction proceeds in two steps: first, we assume an appropriate topological sort of the arguments in the directed acyclic graph (ignoring self-cycles) from [Dvoˇr´ak, 2012, Theorem 30] and we introduce "backward paths" of length 2 between any two successive vertices. That is, let A be sorted as A = {a1, . . . , aN}. Then, for every i ∈ {1, . . . ,N - 1}, we add vertices ui and arcs (ai+1, ui), (ui, ai), (ui, ui). The self-cycles prevent the ui's from being selected in a stage extension. The idea of these paths of length 2 is that every simple cycle in the resulting graph consists of a "forward" arc (i.e., from some ai to some ai+k) and a sequence of k - 1 "backward paths" of length 2. Hence, these cycles have odd length. Moreover, since a1 can be chosen such that every other vertex in A is reachable from it, the additional paths of length 2 thus make sure that the graph has a single SCC.

The second step then adds further auxiliary vertices vi, v′i together with a cycle of length 3 for every i ∈ {1, . . . , N-1}: (vi, ui), (ui, v′i ), (v′i , vi), (v′i , v′i ); the AF thus remains to consist of a single component. Moreover, every stage extension contains the "auxiliary" vertices vi and, thus, has all vertices ui in its range. This is needed to guarantee that the maximality condition of stage extensions only depends on the original vertices in A and not on the question as to which of the additional vertices ui are contained in the range.

Analogously to [Dvoˇr´ak, 2012, Theorem 30], one can show that the resulting AF is guaranteed to have 2m stage extensions, where m denotes the number of clauses in the instance ϕ of the SAT problem. Further stage extensions exist if and only if ϕ is satisfiable. Hence, the ManySol problem is NPhard and intractability of EnumExt(Cnoev, σ) for the semantics σ ∈ {stage, stage2 } follows from Proposition 1.

5 Conclusion

In this work, we have started a systematic study of the enumeration problem in the context of abstract argumentation. As our main result, we have identified the border between tractable and intractable enumeration for AFs under 11 of the most common semantics of AFs. A great variety of settings has been explored by considering unrestricted AFs as well as AFs with common structural restrictions (namely, bipartite graphs, symmetric graphs with or without self-loops, graphs without even cycles, and implicitly also acyclic graphs).

These tractability and intractability results can now be used as guidance for developers of argumentation tools which compute the set of extensions under a given semantics. Developers have to make sure that, in the tractable cases identified here, the tools indeed work efficiently. In particular, for reduction-based argumentation tools (working by reduction to SAT or ASP), it is not guaranteed a priori that favorable structural properties of an input AF are preserved under the reduction and exploited by the target solvers.

Note that further structural restrictions of AFs have been studied in the literature, such as AFs with no odd cycles. Since they provide a generalization of the class Cbip of AFs restricted to bipartite graphs, our intractability results for the semantics pref , stable, comp, semi , stage, and stage2 carry over to AFs with no odd cycles. Likewise, the DelayPP membership for the semantics cf , naive, resGr, and cf2 carries over from the unrestricted case C0. In contrast, the adm semantics remains as an interesting open question. Further structural restrictions to be considered can be found in [Dunne, 2007]. A particularly interesting class is given by AFs which, when interpreted as undirected graphs, have bounded treewidth. For this class, MSO encodings as given in [Dunne, 2007; Dvoˇr´ak et al., 2012] readily pave the way for showing tractable enumeration via meta-theorems as provided in [Flum et al., 2002; Bagan, 2006; Courcelle, 2009].

Our study has revealed that the boundary between easy and hard cases of enumeration may well differ from related decision problems. For instance, as recalled in Section 2, both credulous and skeptical reasoning with cf2 semantics is intractable. Nevertheless, the enumeration of all cf2 extensions is feasible with polynomial delay. Hence, for future work, the search for further tractable fragments of computational problems in the area of argumentation should take the enumeration problem as an additional focus into account.

Acknowledgments

This research was supported by the Austrian Science Fund (FWF): P25207-N23, P25518-N23, I2854-N35, W1255N23. We thank Wolfgang Dvoˇr´ak for many fruitful discussions and his help.