Complexity-Sensitive Decision Procedures for Abstract Argumentation (Extended Abstract)

1 Introduction

Formal argumentation has evolved into an important field in Artificial Intelligence. Abstract argumentation frameworks (AFs for short), as introduced by Dung [1995], are central in formal argumentation, providing a simple yet powerful formalism to reason about conflicts between arguments. The power of the formalism, however, comes at a price. In particular, many important reasoning problems for AFs are located on the second level of the polynomial hierarchy, including skeptical reasoning in the preferred semantics [Dunne and Bench-Capon, 2002], and both skeptical and credulous reasoning in the semi-stable and the stage semantics [Dvoˇr´ak and Woltran, 2010]. This naturally raises the question about the origin of this high complexity and, in particular, calls for research on lower complexity fragments of the reasoning tasks. The focus of this article is both on the identification of such lower-complexity fragments of second-level reasoning problems arising from abstract argumentation, and on exploiting this knowledge in developing efficient complexity-sensitive decision procedures for the generic second-level problems.

Tractable (i.e., polynomial-time decidable) fragments have been quite thoroughly studied in the literature (see [CosteMarquis et al., 2005; Dunne, 2007; Dvoˇr´ak et al., 2010; 2012b; 2012a] for instance). However, there is only little work on identifying fragments which are located on the first level (NP/coNP layer), that is, in-between tractability and full second-level complexity.

Identification of first-level fragments of second-level reasoning tasks is important due to several reasons. Firstly, from a theoretical point of view, such fragments show particular (but not all) sources of complexity of the considered problems. Secondly, NP fragments can be efficiently reduced to the problem of satisfiability in classical propositional logic (SAT). This allows for realizations of argumentation procedures by employing sophisticated SAT-solver technology [Marques-Silva and Sakallah, 1999; E´en and S¨orensson, 2004] for reasoning over argumentation frameworks.

Going even further, in this work we aim at designing decision procedures for second-level argumentation problems by distance: graph-based distance measures, where the parameter is the number of arguments to be deleted from a given AF in order to fall into a specified class; and extension-based distance measures, which apply to the semantical subclasses.

∗This paper is an extended abstract of [Dvoˇr´ak et al., 2014].

We show that graph-based distance measures are in most cases tight: already a small distance from the subclass at hand leads to the full second-level complexity. For the semantic distance measures, we show that certain problems can be solved by a bounded number (in terms of the distance) of NP-oracle calls. Exploiting extension-based distances, we develop a generic framework of complexity-sensitive decision procedures for different second-level reasoning problems within abstract argumentation. We have implemented this idea in a prototype system, called CEGARTIX, that exploits current state-of-the-art conflict-driven clause learning (CDCL) SAT-solver technology as the underlying NP oracle. Experiments show the high potential of the proposed approach compared to other state-of-the-art implementations for abstract argumentation, in particular the logicprogramming approach based on monolithic encodings of second-level problems [Egly et al., 2010].

In the long version of this extended abstract ([Dvoˇr´ak et al., 2014]) we further investigate in detail the semi-stable and stage semantics for argumentation frameworks. Decision problems for these two semantics are, like for the preferred semantics, located at the second level of the polynomial hierarchy, and we have extended our complexity analysis, complexity sensitive decision procedures, implementation, and empirical evaluation to these semantics as well.

2 Preliminaries

In this section we review argumentation frameworks [Dung, 1995], the semantics studied in this work (see also [Baroni et al., 2011]), and known complexity results for decision problems under the different semantics.

Definition 1. An argumentation framework (AF) is a pair F = (A,R) where A is a finite set of arguments and R ⊆ A × A is the attack relation. An argument a ∈ A is defended by a set S ⊆ A if for each b ∈ A such that (b, a) ∈ R, there is a c ∈ S s.t. (c, b) ∈ R.

Semantics for argumentation frameworks assign to each AF F = (A, R) a set σ(F ) ⊆ 2A of extensions. We consider here for σ the functions stb, adm, prf , com, which stand for stable, admissible, preferred, and respectively, complete semantics.

Definition 2. Let F = (A,R) be an AF. A set S ⊆ A is conflict-free (in F), denoted S ∈ cf (F), iff there are no a, b ∈ S such that (a, b) ∈ R. For S ∈ cf (F), it holds that

• S ∈ stb(F) if for each a ∈ A \ S, there exists a b ∈ S s.t. (b, a) ∈ R;
• S ∈ adm(F) if each a ∈ S is defended by S;
• S ∈ prf (F) if S ∈ adm(F) and there is no T ∈ adm(F) with T ⊃ S; and
• S ∈ com(F) if S ∈ adm(F) and for each a ∈ A defended by S, a ∈ S holds.

We recall that for each AF F, stb(F) ⊆ prf (F) ⊆ com(F) ⊆ adm(F) holds, and that for each of the considered semantics σ (except stable) σ(F) ̸= ∅ holds.

Example 1. Consider the AF F = (A,R), with A = {a, b, c, d, e} and R = {(a, b), (c, b), (c, d), (d, c), (d, e), (e, e)}. The graph representation of F is shown in Figure 1. Here stb(F) ={{a, d}}. The admissible sets of F are ∅, {a}, {c}, {d}, {a, c} and {a, d}. The set of preferred extensions is prf (F) = {{a, c}, {a, d}}. The complete extensions are {a}, {a, c} and {a, d}. ✸

Given an AF F = (A,R), a semantics σ and an argument a ∈ A, the credulous reasoning problem (Credσ) asks whether there exists an E ∈ σ(F) with a ∈ E , while the skeptical reasoning problem (Skeptσ) asks whether a ∈ E for all E ∈ σ(F) holds. We have Credadm = Credcom = Credprf . These three problems and Credstb are NP-complete. On the other hand, Skeptadm is trivial, Skeptcom is Pcomplete, Skeptstb is coNP-complete, and Skeptprf is ΠP2 - complete [Coste-Marquis et al., 2005; Dimopoulos and Torres, 1996; Dung, 1995; Dunne and Bench-Capon, 2002].

3 Complexity of Subclasses of AFs

In this section we review several classes of AFs where reasoning with preferred semantics becomes easier. Both earlier and new results are discussed. First, we consider the classes of acyclic and weakly cyclic AFs.

Definition 3. An AF F is acyclic if there is no directed cycle of attacks in F; F is weakly cyclic if F can be made acyclic by deleting one argument (and its incident attacks) from each strongly connected component 1 (SCC) of F . We denote these classes of AFs by acyc and wcyc.

It is well known that Skeptprf becomes tractable when restricted to acyclic AFs. For the class wcyc (these are the AFs where the graph parameter cycle-rank is at most 1) we can make use of a result in [Dvoˇr´ak et al., 2012b] to show that Skeptprf is coNP-complete. Moreover one can efficiently decide whether a given AF falls into one of these two classes.

The next class relates preferred and stable extensions and was already introduced in Dung's seminal paper [1995]. Later it has been thoroughly discussed in [Dunne and BenchCapon, 2002].

Definition 4. An AF F is coherent if prf (F) = stb(F). We denote the class of such AFs by coherent.

1 A set of arguments is called strongly connected in an AF if there is a path from each argument to every other argument in the set. A strongly connected component of an AF is a ⊆-maximal strongly connected set.

Skeptical reasoning under preferred semantics is coNPcomplete when restricted to AFs from coherent. Unfortunately, testing coherence is ΠP2 -complete [Dunne and BenchCapon, 2002]. At first glance this restricts the practical value of this fragment, but there is a class of easy detectable coherent AFs, namely the AFs without odd-length cycles.

Definition 5. An AF F is odd-cycle free if there is no directed cycle consisting of an odd number of attacks in F . We denote the class of odd-cycle free AFs by ocf.

In fact, testing for odd-length cycles in digraphs can be done in polynomial time (see e.g. [Bang-Jensen and Gutin, 2010]). Dunne [2007] observed that for F ∈ ocf reasoning with preferred semantics is complete for the first level of the polynomial hierarchy.

The final fragment we introduce is another semantical one. It makes use of the complexity gap between credulous and skeptical acceptance for preferred semantics.

Definition 6. We denote the class of AFs F satisfying |prf (F)| = 1 by uniqpref.

The problem Skeptprf is in NP if we restrict to AFs F ∈ uniqpref. It is open whether these problems are also NPhard. However, we can show NP-hardness under so-called randomized reductions [Valiant and Vazirani, 1986].

To summarize, we have introduced several kinds of AFsubclasses. They can be grouped into syntactical (acyc, wcyc, ocf), and semantical classes (coherent, uniqpref). The complexity results are shown in Table 1. Next, we study possibilities of extending the "good" complexity behavior of these classes. To this end, we will introduce certain distance measures with the aim of maintaining lower complexity as long as the distance to such a class is bound.

Graph-Based DistanceMeasures A natural way to generalize a subclass is to consider the minimal number of arguments one has to delete from an AF so that the modified AF falls into the respective class (see also [Dvoˇr´ak et al., 2012a]). This gives rise to the following distance measure.

Definition 7. Let G be a graph class and F = (A,R) an AF. We define distG(F) as the minimal number k such that there is a set S ⊆ A with |S| = k and (A\S, R∩(A\S×A\S)) ∈ G. If there is no such set S we define distG(F) =∞.

Table 1 summarizes our results which are all negative in the sense that full second-level complexity is reached when fragments are parameterized in a "syntactic" way (hardness holds even for distG(F) = 1); only acyc yields some positive results (due to [Dvoˇr´ak et al., 2012a]). Here FPT (fixedparameter tractability) means that for a fixed distance, a problem can be solved in polynomial time and the order of the polynomial time bound does not depend on the distance.

Extension-Based Distance Measures Next, we consider different distance measures which take the number of extensions into account and thus naturally apply only to the semantical subclasses of AFs, i.e. coherent and uniqpref.

Definition 8.

An AF F is k-coherent, for k ≥ 0, if |prf (F) \ stb(F)| ≤ k. We use coherentk to denote the respective class of AFs.

We denote by solkprf the class of all AFs F such that |prf (F)| ≤ k.

While the following theorem gives a negative result for coherentk it gives a positive result for solkprf which guides us to complexity-sensitive procedures.

Theorem 1.

• Skeptprf for AFs in coherentk is ΠP2 -hard under randomized reductions; hardness holds even for k = 1.
• For AFs F ∈ solkprf , Skeptprf is in PNP.

4 Complexity-Sensitive Procedures

In this section we describe a complexity-sensitive decision procedure for skeptical acceptance under preferred semantics. Our procedure is based on the observations in Theorem 1. As a result, the procedure is complexity-sensitive w.r.t. the number of preferred extensions in the given framework.

The general framework implemented by our procedure exploits NP-oracles, and uses oracle calls to decide NPdecidable relaxations of the input instance by over- and/or under-approximating the acceptance conditions of the problem at hand. The relaxation is iteratively strengthened based on the answers provided by the oracle calls. More specifically, at the beginning of the procedure, the candidate extensions are the NP-decidable admissible sets (or, alternatively, complete extensions). We refer to the semantics that characterizes the initial candidate extensions as the chosen base semantics. Starting from the initial candidate extensions, the remaining set of candidate extensions is then non-trivially reduced in an iterative fashion based on the results returned by the previous oracle calls.

Our procedure incorporates an additional shortcut. It utilizes the following observation: in coherent AFs an argument a is skeptically accepted iff a is not attacked by a preferred extension. In general, one has to drop the "if" direction. However, it holds that an argument is skeptically accepted only if a is not attacked by a preferred extension. The latter is equivalent to a not being attacked by an admissible set or a complete extension, which can be checked with one NP-oracle call.

Our complexity-sensitive procedure for deciding skeptical acceptance of an argument w.r.t. preferred semantics is presented as Algorithm 1, Skeptprf (F, α). First, the procedure applies the just explained shortcut. If this does not result in

Algorithm 1 Skeptprf (F, α)

Require: AF F = (A, R), α ∈ A, σ ∈ {adm, com} Ensure: accepts iff α is skeptically accepted in F w.r.t. prf 1: E ← ∅ 2: if ORA (∃E ∈ σ(F) : E attacking α) then 3: reject 4: end if 5: while E ← ORA(∃E∈σ(F):α̸∈E, ∄E′ ∈E :E⊆E′ ) do 6: while E′ ←ORA (∃E′ ∈ σ(F) : E ⊂ E′ ) do 7: E ←E′ 8: end while 9: if α ̸∈ E then 10: reject 11: else 12: E ← E ∪ {E} 13: end if 14: end while 15: accept

a decision for the input instance, the algorithm iteratively traverses the search space of the base semantics σ.

The outer while loop in line 5 computes an admissible set or complete extension E excluding α and ensuring that E is not a subset of an already visited preferred extension that is in E. If such an E is found it is iteratively extended in the inner while loop until a subset maximal σ extension is found, which is a preferred extension. If α ̸∈ E we can reject skeptical acceptance of α in F , and otherwise add E to E and repeat the search process.

Notice that in the algorithm we use the oracle function ORA not only to get yes/no answers for NP-queries, but also to obtain certain extensions. This does not fully match with the formal notion of an NP-oracle, which only returns yes or no, but to a functional variant of it. However, ORA can be easily implemented by a linear number of calls to a classical NP-oracle. In our implementation, shortly discussed next, we employ SAT-solvers that directly provide satisfying assignments corresponding to extensions.

Example 2. Let us illustrate the behavior of Algorithm 1 for the AF from Example 1. The AF has two preferred extensions {a, c} and {a, d} with a being the only skeptically accepted argument. First, we test b for skeptical acceptance with Algorithm 1 and base semantics adm. Then, already in line 2 of the algorithm we obtain an admissible set attacking b, e.g. {a, c}, and thus reject skeptical acceptance of b. Now consider the argument a and base semantics com. As a is not attacked the shortcut in line 2 does not apply. Since there is no E ∈ com(F) s.t. a /∈ E we immediately exit the outer while loop in line 5 and conclude skeptical acceptance of a. Considering argument c, we find out via the shortcut that there is a complete extension attacking this argument, namely {a, d} and thus reject skeptical acceptance of c.

Empirical Evaluation We implemented our complexitysensitive decision procedures in the system CEGARTIX 2 . A preliminary analysis revealed a performance boost compared to ASPARTIX [Egly et al., 2010], a state-of-the-art system for abstract argumentation based on answer-set programming. We further investigated the choice of the base semantics. Complete semantics outperformed admissible semantics on some instances, but overall yielded similar results. The full analysis, including also a comparison of different underlying SAT-solvers, can be found in [Dvoˇr´ak et al., 2014].

5 Discussion

In this work, we developed a novel method for solving hard problems in the area of argumentation in a "complexitysensitive" way. Our prototype implementation CEGARTIX employs SAT-solvers as underlying inference engines. Experiments show that CEGARTIX significantly outperforms existing systems developed for hard argumentation problems (i.e. problems under the preferred, semi-stable, or stage semantics). The fundamental aspects of our approach are generic, allowing in principle to exploit as the underlying NP-oracle systems developed for other reasoning problems such as CSP or ASP, or even native argumentation systems for "easier" semantics such as the stable or complete semantics. In that way, our approach can be seen as a hybrid variant of many current systems for argumentation that are either reduction-based (building a single call to an oracle), or dedicated, i.e. constructing an algorithm from scratch (see also [Charwat et al., 2015] for a survey on many approaches to implement abstract argumentation semantics).

Our promising experimental results have been complemented by Cerutti et al. [2014a] who utilized similar iterative SAT techniques as CEGARTIX to enumerate all preferred extensions of an AF in their high-performance system ArgSemSat. ArgSemSat was further augmented in subsequent work [Cerutti et al., 2014b] via a computation along the strongly connected components of the given AF such that only a partial framework has to be evaluated in a SAT call. Furthermore, the iterative scheme was also utilized for extended argumentation frameworks (EAFs) [Modgil, 2009] in an ASP approach by [Dvoˇr´ak et al., 2015].

Building necessary ground for the complexity-sensitive approach, we also presented an extensive complexity theoretic analysis, providing new results for fragments of argumentation frameworks, as well as distance-based complexity analysis, complementing results from [Dvoˇr´ak et al., 2012a]. Recently, de Haan and Szeider [2014] introduced novel parameterized complexity classes related to our complexity-sensitive approaches. These classes either show the applicability of certain NP oracle based algorithms for problems "beyond NP", or give evidence that such algorithms are not possible.

For future work, the experimental results suggest to apply our approach to further formalisms extending the Dung-style frameworks such as abstract dialectical frameworks (ADFs) [Brewka et al., 2013]. ADFs are an appealing target formalism, since they generalize other proposals such as bipolar frameworks [Amgoud et al., 2008] and EAFs. In the opposite direction, one could consider further fragments of Dung-style frameworks. For preferred semantics, an interesting class are AFs having a bound number of odd cycles; the complexity of evaluating such AFs is currently open. Finally, it would be interesting to relate our complexity-sensitive approaches to the new classes developed by de Haan and Szeider [2014].

2 Available at www.dbai.tuwien.ac.at/research/project/ argumentation/cegartix/.

Acknowledgments

This work has been funded by the Austrian Science Fund (FWF) through projects I1102, Y698, and P25518-N23, and by Academy of Finland through grants 251170, 276412, and 284591.