# preferred_reasoning_in_aba_by_cyclebreaking__5823ba07.pdf

Preferred Reasoning in ABA by Cycle-Breaking

Kiet Ngyuen Anh1 , Markus Ulbricht2

Sca DS.AI Dresden/Leipzig, Leipzig University

1kietnguyen2023@hotmail.com 2mulbricht@informatik.uni-leipzig.de

We develop a fixed-parameter tractable (FPT) algorithm for skeptical preferred reasoning in assumption-based argumentation (ABA). To this end we make use of so-called backdoors, i.e., sets of assumptions that need to be evaluated s.t. the remaining ABA framework (ABAF) belongs to a computationally beneficial sub-class. In order to identify such target classes, we employ a suitable notion of a dependency graph of an ABAF. We show that these graphs can be constructed in polynomial time and that one can efficiently check sufficient properties ensuring that reasoning in the underlying ABAF is tractable. After establishing the theoretical foundations, we test our implementation against the ASPfor ABA solver which convincingly won the ABA track of the ICCMA 23 competition. As it turns out, our algorithm outperforms ASPfor ABA on instances with small backdoor sizes.

1 Introduction Computational models of argumentation [Baroni et al., 2018] play a central role in non-monotonic reasoning and have a wide range of applications in various fields such as law and healthcare [Atkinson et al., 2017]. A well-known computational model of argumentation are so-called abstract argumentation frameworks, introduced by Dung [Dung, 1995]. In this work, Dung formalizes that a debate can be represented and evaluated by viewing arguments as atomic entities and attacks as a relation between them. This way, the discussion is represented as a directed graph F = (A, R) where A is a set of arguments and R A A the attack relation. To study an AF in the field of formal argumentation, the notion of semantics was introduced, mapping an AF to sets of jointly acceptable arguments [Baroni et al., 2011]. Several aspects of AFs have been studied extensively in the literature, e.g. enforcing arguments [Wallner et al., 2017; Niskanen et al., 2018], belief revision [Falappa et al., 2009; Haret et al., 2018], repairing a semantical collapse [Baumann and Ulbricht, 2019], or the role of formal argumentation for explainability in AI [Cyras et al., 2021]. Since an AF F = (A, R) can be interpreted as a directed graph, researchers make use of graph-theoretical properties

in order to study computationally beneficial argumentation scenarios. For instance, the theoretical computational complexity has not only been studied extensively for AFs in general [Dvor ak and Dunne, 2018], but also for sub-classes like e.g. i) AFs without odd-length cycles (odd-cycle free AFs), ii) AFs without even-length cycles (no-even AFs), iii) AFs without any cycle whatsoever (acyclic AFs). Moreover, means to compute models of F step-wise have been studied [Baroni et al., 2005; Baumann, 2011; Baumann et al., 2020]. Another line of research is concerned with so-called fixed-parameter tractability (FPT) for reasoning problems in AFs [Dunne, 2007; Dvor ak et al., 2012b; Dvor ak et al., 2022a] or e.g. probabilistic AFs [Liao et al., 2018]. The idea is to identify a suitable parameter s.t. a given intractable problem becomes tractable whenever the parameter does not exceed a certain bound. In [Dvor ak et al., 2012a] the notion of backdoors has been considered: e.g. an acyclic backdoor is a set of argument s.t. their removal from the graph results in an acyclic AF. The authors show that, if the size of the smallest acyclic backdoor is bounded, then many important reasoning problems for AFs become tractable [Dvor ak et al., 2012a], i.e., these problems are FPT. This procedure has recently also been lifted to argumentation frameworks with collective attacks (SETAFs) [Dvor ak et al., 2022b]. One key aspect in the argumentation pipeline is the use of structured argumentation formalisms [Besnard et al., 2014], which are employed to outline formal argumentative workflows from building blocks. Prominent approaches include assumption-based argumentation (ABA) [Bondarenko et al., 1997], ASPIC+ [Modgil and Prakken, 2013], defeasible logic programming De LP [Garc ıa and Simari, 2004], and deductive argumentation [Besnard and Hunter, 2008]. The reasoning process within these formalisms typically involves creating argument structures and identifying conflicts among them in a systematic manner from rule-based knowledge bases. The resulting arguments and conflicts can be captured by constructing a suitable AF. This AF can be utilized to determine the acceptability of arguments and draw conclusions based on the original knowledge bases. In this paper, we focus on ABA as it is one of the key structured argumentation formalisms [ ˇCyras et al., 2018]. While the theoretical computational complexity of reasoning in ABA has also been investigated [Dvor ak and Dunne, 2018] and solvers have been designed [Lehtonen et al., 2021;

Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence (IJCAI-24)

Lehtonen et al., 2023], the study of FPT algorithms is not yet as extensive as in the case of AFs (one exception is a recent dynamic programming approach based on a bounded treewidth [Popescu and Wallner, 2023]). Since an ABA knowledge base is a rule-based system and no graph, means to identify suitable sub-classes as in the case of AFs are not immediate. Consequently, finding a notion of a no-even or acyclic backdoor in ABA is a more involved endeavor. In this paper, we approach this issue by identifying a suitable dependency graph for ABA which entails the properties we desire; for instance, we show that if there is no cycle in this graph, then reasoning in the corresponding ABA framework is tractable (a result similar to acyclic AFs). Building upon this cycle notion, we devise and implement an FPT-algorithm for skeptical preferred reasoning in ABA. Along the way, we establish several required theoretical results, which are interesting on their own, independent of our FPT procedure. Our main contributions can be summarized as follows.

We study ABA classes induced by a polynomial-time computable dependency graph. Section 3

We show how to perform computations in ABA in a modular way. Section 4

We design and implement a backdoor algorithm for skeptical preferred reasoning in ABA. Section 5

The source code for our algorithm can be found online1.

2 Background

Abstract Argumentation. An argumentation framework (AF) [Dung, 1995] is a directed graph F = (A, R) where A represents a set of arguments and R A A models attacks between them. For two arguments x, y A, if (x, y) R we say that x attacks y. We let E+ = {x A | E attacks x} for a set E A. A set E A is conflict-free in F iff for no x, y E, (x, y) R; E defends an argument x if E attacks each attacker of x. A conflict-free set E is admissible in F (E ad(F)) iff it defends all its elements. A semantics is a function with F 7 σ(F) 2A. This means, given an AF F = (A, R) a semantics returns a set of subsets of A. These subsets are called σ-extensions. In this paper we consider socalled complete, grounded, preferred, and stable semantics (abbr. co, gr, pr, stb).

Definition 2.1. Let F = (A, R) be an AF and E ad(F).

E co(F) iff E contains all arguments it defends;

E gr(F) iff E is -minimal in co(F);

E pr(F) iff E is -maximal in co(F);

E stb(F) iff E+ = A \ E.

Assumption-based Argumentation. We assume a deductive system (L, R), where L is a formal language, i.e., a set of sentences, and R is a set of inference rules over L. A rule r R has the form a0 a1, . . . , an with ai L. We denote the head of r by head(r) = a0 and the (possibly empty) body of r with body(r) = {a1, . . . , an}.

1https://github.com/kiet Github User/ ABA-Backdoor-Implementation

Definition 2.2. An ABAF is a tuple D = (L, R, A, ), where (L, R) is a deductive system, A L a set of assumptions, and a partial contrary function : A L. Note that we allow for assumptions without any contrary since is partial. This does not make any conceptual difference, but is more convenient for our purpose. Assumption 2.3. In this work, we focus on ABA frameworks which are flat, i.e., for each rule r R, head(r) / A (no assumption can be derived), and finite, i.e., L, R, A are finite; moreover, we assume L to be a set of atoms. We say that a sentence p L is derivable from assumptions S A and rules R R, denoted by S R p, if there is a finite rooted labeled tree T such that the root is labeled with p, the set of labels for the leaves of T is equal to S or S { }, and for every inner node v of T there is a rule r R such that v is labelled with head(r), the number of successors of v is |body(r)| and every successor of v is labelled with a distinct a body(r) or if body(r) = By Th D(S) = {p L | S S : S R p} we denote the set of all conclusions derivable from an assumption set S in D. Observe that S Th D(S) as a A is derivable from {a} a. For S A, let S = {a | a S}; moreover, for a derivation S p we write asms(S p) = S and for a set E of derivations we let asms(E) = S x E asms(x). Also, we often write S R p simply as S p. A set S A attacks a set T A, if for some a T we have that a Th D(S). A set S is conflict-free, denoted S cf (D), if it does not attack itself; it is admissible, denoted S ad(D), if S is conflict-free and S defends itself, i.e., for each set T A, we have that if T attacks S, then S attacks T as well. With a little notational abuse we say S attacks a if S attacks the singleton {a}. We next recall grounded, complete, preferred, and stable ABA semantics (abbr. gr, co, pr, stb). Definition 2.4. Let D = (L, R, A, ) be an ABAF. Further, let S A be admissible in D. S co(D) iff S contains all assumptions it defends; S gr(D) iff S is -minimal in co(D); S pr(D) iff S is -maximal in co(D); S stb(D) iff S attacks each {x} A \ S. We say that an assumption a A is credulously accepted (skeptically accepted) wrt. a semantics σ in an ABAF D iff a S σ(D) (iff σ(D) = and a T σ(D)). In this case, we write a credσ(D) resp. a skepσ(D). An ABAF induces an AF as follows. Definition 2.5. The associated AF FD = (A, R) of an ABAF D = (L, R, A, ) is given by A = {S p | S A, p L} and attack relation (S p, S p ) R iff p S . ABA and AFs are closely related (see [ ˇCyras et al., 2018]). Proposition 2.6. Given an ABAF D = (L, R, A, ), its corresponding AF FD and a semantics σ {gr, co, pr, stb}. If E σ(FD) then asms(E) σ(D); if S σ(D) then {S p | S S, R R : S R p} σ(FD). Since it suffices to instantiate only finitely many arguments (see e.g. [Lehtonen et al., 2023]) we assume that the AF corresponding to some ABA D is finite, if not stated otherwise.

Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence (IJCAI-24)

3 ABA Classes In the context of AFs, several graph classes have been studied in the literature with corresponding computational benefits [Dvor ak and Dunne, 2018]. For instance, AFs without any even-length cycle (also called no-even AFs) have exactly one complete extension (which, in this case, can be computed in polynomial time). However, since ABA is a rule-based system, designing such algorithms in terms of suitable graph-classes is not immediate. A natural starting point would be to utilize Proposition 2.6 in order to obtain the desired properties from the instantiated AF FD. Indeed, the following observation is a direct corollary of known ABA properties. Fact 3.1. Let D = (L, R, A, ) be an ABAF. If FD is odd-cycle free, then pr(D) = stb(D); even-cycle free, then gr(D) = co(D) = pr(D); acyclic, then gr(D) = co(D) = pr(D) = stb(D). This result is, however, impractical as it requires computing the (possibly exponential) argumentation graph FD. In this section, we seek to analyze a given ABAF D in a similar way, but thereby avoid computing FD.

3.1 ABA Dependency Graphs A natural way to extract a graph from ABA is the notion of a dependency graph. Such graphs have been constructed in e.g. [Craven and Toni, 2016], but we need to differ from this notion to obtain a graph that is suitable for our purpose. Our notion of dependency graphs is inspired by similar concepts for logic programming [Apt and Bol, 1994, Definition 2.2] and the more recent ABA dependency graph [Rapberger et al., 2022]; we require, however, a different path notion. The idea is that the graph captures the dependencies between atoms, i.e., there is an edge from p to q whenever there is some rule with p in the body and q in its head. In addition, we draw an edge from a to a for each assumption a A to account for attacks. Definition 3.2. The dependency graph GD = (V, E, l) for a given ABA D = (L, R, A, ) is an edge-labelled graph with V = L is the set of vertices, there is an edge e = (s, t) E iff i) there is some r R with s body(r) and head(r) = t, in this case l(e) = +; or ii) t A and t = s, in this case, l(e) = . Recall that our goal is to obtain a result in the spirit of Fact 3.1 in terms of the dependency graph GD. The question is thus how to define paths and cycles in GD. Since the labeled edges account for attacks in the ABAF, it makes senses to define the length of a path by the number of labeled edges. However, there is some technical issue we need to take consideration, as illustrated in the following. Example 3.3. Let D = (L, R, A, ) be the ABAF with A = {a, b}, L = A {ac, bc}, the expected contraries, i.e., a = ac as well as b = bc, and the following rules R:

r1 : bc a r2 : bc b r3 : ac bc Then the dependency graph GD is given as follows (we highlight the assumptions in the graph to enhance readability).

We can construct a path form a to b, namely a, bc, b, but then we cannot continue this path to turn it into a cycle a, bc, b, bc, ac, a since this sequence visits bc twice. However, ABA is tailored to investigate the interaction of assumptions and ordinary atoms are mere intermediate steps in derivations. We would thus expect GD to contain an even-cycle. The problem in the previous example was that visiting bc twice prevented us from constructing an even-cycle from a to b and back. This can be circumvented by allowing to visit ordinary atoms multiple times. We thus define paths and their length in dependency graphs as follows. Definition 3.4. Let D = (L, R, A, ) be an ABAF and GD = (V, E, l) its dependency graph. A weak path is a sequence p1, ..., pn with n 1, pi V , and (pi, pi+1) E for each i < n and pi = pj for i = j, whenever pi, pj A. If p1 = pn, then the weak path is a weak cycle. The length of a weak path is the number of labeled edges e = (pi, pi+1). Example 3.5. The dependency graph GD from Example 3.3 contains a weak odd-cycle b, bc, b of length 1 and a weak even-cycle b, bc, ac, a, bc, b of length 2. It is clear that, in contrast to FD, the dependency graph GD can be computed in polynomial time. This provides us with the desired computational advantage. Proposition 3.6. GD can be computed in polynomial time. Now we define the classes of ABAFs based on the cycle properties of the underlying dependency graph. Definition 3.7. Let D = (L, R, A, ) be an ABAF and GD = (V, E, l) its dependency graph. Then D is called acyclic iff GD contains no weak cycle of length n 1; odd-cycle free iff GD contains no odd-length weak cycle; even-cycle free iff GD contains no even-length weak cycle of length n 2. From now on we just say cycle instead of weak cycle .

3.2 Computational Properties The question arises whether or not cycles in GD are a weaker, stronger, or equivalent notion compared to cycles in FD. That is, can we lift Fact 3.1 to the underlying dependency graph? It turns out that under mild conditions, the dependency graph GD is capable of identifying the cycles we need. In fact, in a certain sense GD gives rise to an even a more efficient cycle notion since it detects fewer cycles, but induces all computational properties we seek. To see that not every cycle in FD induces a cycle in GD, we consider the following example. Example 3.8. Let D = (L, R, A, ) be an ABAF with A = {a, b, c, d, e}, L = A {ac | a A}, the expected contraries, and the following rules R: dc a. bc a. cc b. ac c. ec d. ac e. The reader may verify that the induced AF FD contains an even-cycle, where the dependency graph GD does not.

Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence (IJCAI-24)

Now let us head to the other direction, i.e., suppose we are given a cycle in GD. Here it might be the case that the cycle is due to atoms that can never be derived from any assumption. We exclude this case with the following notion. Definition 3.9. An ABAF D = (L, R, A, ) is called trim if L = Th D(A). In a trim ABAF, each atom p L can be derived and thus, each rule r R is applicable. Note that a simple unit propagation suffices to turn any ABAF into a trim one in polynomial time. Given a trim D, the following can be inferred. Proposition 3.10. If D is trim and there is a weak cycle of length n 1 in GD, then there is a cycle of length n in FD. Example 3.11. Recall Example 3.3. We depict the instantiated AF FD next to the dependency graph we already computed. In FD, xi stems from rule ri for each i {1, 2} and x31 and x32 are due to combining x1 and x2 with r3.

The even-length cycle a, bc, b, bc, ac, a in the dependency graph GD can be traced back to a entailing the contrary of b (via argument x1) and b entailing the contrary of a (via argument x32). Indeed, x1 and x32 form an even-cycle in FD. Putting together the previous observations shows that GD is more cautious in terms of cycles compared to FD. It is thus not clear whether this notion is strong enough for our purpose, i.e., whether Fact 3.1 can be lifted to ABAFs by means of these graphs. The following theorem answers this question affirmatively. Theorem 3.12. Let D = (L, R, A, ) be an ABAF. If D is odd-cycle free, then pr(D) = stb(D); even-cycle free, then gr(D) = co(D) = pr(D); acyclic, then gr(D) = co(D) = pr(D) = stb(D). Intuitively, even-cycles in GD induce the non-determinism underlying co, pr, and stb; odd-cycles are responsible for the potential collapse of stb as they serve as constraints for acceptability; and without any cycle whatsoever, many reasoning tasks coincide with the simple gr reasoning. As a final remark, we want to mention that our notion of cycles is in a certain sense independent of the tree derivations in a given ABAF: while the term acyclic in e.g. [Craven and Toni, 2016] is used to ensure that for each tree derivation S p, there is no cyclic dependency between atoms, our dependency graphs GD are not tailored to examine such dependencies. To illustrate this, we mention that even for acyclic ABAFs, there might be infinitely many tree-based arguments. Proposition 3.13. There is an acyclic ABAF D that gives rise to infinitely many tree-based arguments. To summarize, by inspecting GD we can anticipate the class to which D belongs, without computing FD. This is even the case for situations where FD might be large, while GD on the other hand always has at most |L| nodes.

4 Partial Evaluations in ABA We now have a target class of ABAFs for our backdoor algorithm: the idea is to guess the label of assumptions occurring in a cycle in D and then evaluate the remaining ABAF by propagating the labels. Doing so, however, requires us to have tools to partially evaluate a given ABAF. To this end we define the reduct as in the case for AFs [Baumann et al., 2022] to conveniently study our backdoor algorithm in Section 5.

4.1 The ABA Reduct First we define what we mean by the range S of a set S of assumptions. As in the case of AFs, S+ is the set of assumptions attacked by S and the range is their union, i.e., we let S = S S+. Definition 4.1. Let D = (L, R, A, ) be an ABAF. For S A we let S+ D = {a A | S attacks a} and call S D = S S+ D the range of S. Now given an ABAF D we define the reduct w.r.t. some set S of assumptions in the way that D is (partially) evaluated w.r.t. S. That is, we assume S to be true and thus evaluate S+ as false. Hence assumptions in S can be removed from rule bodies, whereas rules relying on assumptions in S+ can be deleted entirely. This amounts to the following notion. Definition 4.2. Let D = (L, R, A, ) be an ABAF. The Sreduct of D is the ABAF DS = (L , R , A , ) where L = L \ S D, A = A \ S D,

R = {head(r) body(r)\S | r R, body(r) S+ D = },

and for a A , a = a iff a L and UNDEFINED otherwise. Example 4.3. Consider the ABAF D = (L, R, A, ) with A = {a, b, c}, L = A {ac, bc, cc}, the expected contraries, and the following rules R:

r1 : bc a r2 : ac b r3 : ac c

Let S = {c}. In the reduct DS, c is set to true and since ac Th D(S), we set a to false. This yields the ABAF DS given as DS = ({b, ac, bc, cc}, R , {b}, ) with rules R = {r 2 = (ac b), r 3 = (ac )}. The only assumption is b.

4.2 The Modularization Property Our backdoor algorithm requires us to evaluate a given ABAF partially and then compute a single assumption set S. The technical underpinning we will develop to this end is inspired by the modularization property for AFs [Baumann et al., 2022]. In the previous Example 4.3, the assumption b is unattacked in the reduct DS since a is rendered false (and DS has been evaluated accordingly). Assuming that S = {c} is compatible with b in some formal sense, we would expect that b can be added to S in order to obtain a novel extension S {b}. Indeed, S {b} co(D) is true. In the context of AFs, the so-called modularization property has been introduced in order to capture such step-wise computations of extensions [Baumann et al., 2022]. Phrased within our setting, we obtain the following notion for ABAFs. Definition 4.4. A semantics σ satisfies the modularization property if for each ABAF D, it holds that S σ(D) and S σ(DS) implies S S σ(D).

Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence (IJCAI-24)

Example 4.5. Recall Example 4.3. We have that S = {c} ad(D) and S = {b} ad(DS). Moreover, S S ad(D) so the requirements for ad to satisfy modularization are satisfied for this ABAF. It turns out that this observation is no coincidence. In fact, like for AFs, all considered semantics satisfy modularization. Proposition 4.6. Each semantics σ {ad, co, pr, gr, stb} satisfies modularization. For ad and co semantics, we can even show some kind of inverse statement, in the following sense. Proposition 4.7. Let D = (L, R, A, ) be an ABAF and let σ {ad, co}. If S = S S with S S = and S σ(D) as well as S σ(D), then S σ(DS ). Example 4.8. Recall Example 4.3. We have that S = {b, c} ad(D). Since S = {c} ad(D) we can be certain that {b} ad(DS ). Combining Propositions 4.6 and 4.7 yields the following characterizations of the standard ABA semantics. Theorem 4.9. Let D = (L, R, A, ) be an ABAF, S cf (D) and DS = (L , R , A , ) the reduct. It holds that S stb(D) iff DS = (L , R , , ), S ad(D) iff T attacks S in D implies T \ S A , S pr(D) iff S ad(D) und S ad(DS) = , and S co(D) iff S ad(D) und no assumption in DS is unattacked. As a final remark in this section, we recall the characterization [Baumann and Ulbricht, 2021b, Theorem 5.7] for the existence of a stable extension: There is a stable extension E stb(F) iff there is some admissible extension E ad(F) s.t. E attacks each odd-cycle in F. This translates to ABA in the following way. Theorem 4.10. Let D = (L, R, A, ) be a trim ABAF. Then stb(D) = iff there is some S ad(D) s.t. each assumption a occurring in an odd-cycle in GD satisfies a S .

5 Breaking Cycles: A Backdoor Algorithm We are ready to design our backdoor algorithm. Our idea is inspired by the recent work on backdoor algorithms for SETAFs [Dvor ak et al., 2022b] which are similar in spirit to ABA [K onig et al., 2022]. We will guess a set B of assumptions in such a way that after their acceptance status is evaluated, the remaining ABAF is acyclic. Since acyclic ABAFs only have a unique complete extension, we can propagate the effect of this evaluation through the framework. We then have to check whether this propagation is compatible with our initial guess (implying we found an extension) or not (implying we have to backtrack). We consider the following example to illustrate this idea. Example 5.1. Let D = (L, R, A, ) be the ABAF with A = {a, b, c, d, e}, L = A {x, y, w, z, m, n}, contraries a = y, b = x, c = m, d = w, e = n, and rules R: x a. y a. z b. w z. w w. m b. x c. m e. m m. n c. The dependency graph is given as follows.

From the dependency graph we can extract that e.g. removing b and e renders the ABAF even-cycle free. That is, if we fix the labels of these two assumptions, then the non-determinism is removed from D. Consequently, the remaining labels follow by propagating the effect of guessing b and e. Suppose e.g. we set b and e to true. Then, by applying the given rules, z is entailed and thus w as well which is the contrary of d; hence it follows that d is defeated. Moreover, from e we entail m which means c is rendered defeated as well. Since c is the only attacker of e (by entailing n), we obtain that {b, e} indeed defends e. Nonetheless, {b, e} does not induce an admissible extension since the attack from a against b (by entailing x) cannot be defended. We thus have to correct the status of b and remove it from our extension again. This, however, has no effect on d and we find the admissible extension E = {e}. The idea is thus to find a set of assumptions breaking all cycles in D (called a backdoor), guessing their acceptance status and then propagating the consequences of this guess. Due to our results from Theorem 3.12 we know that the nondeterminism is due to the even-cycles in GD and Section 4 provides us with convenient tools to partially evaluate D.

5.1 Theoretical Foundations Our procedure works by propagating labels on assumptions, denoting whether they are in an extension ( in ), attacked by the given extension ( out ), or neither ( undec ). To this end we need to formally introduce labels for ABA. We will only recall the necessary technical tools here; a comprehensive discussion of labeling-based semantics in ABA can be found in [Schulz and Toni, 2017]. Definition 5.2. Let D = (L, R, A, ) be an ABAF. A labeling is a mapping λ : A {IN, OUT, UNDEC}. We let IN(λ) = {a A | λ(a) = IN}, OUT(λ) = {a A | λ(a) = OUT}, UNDEC(λ) = {a A | λ(a) = UNDEC}, and DEF(λ) = IN(λ) OUT(λ) UNDEC(λ). A complete labeling is defined s.t. it corresponds to some complete extension in the expected way [Schulz and Toni, 2017, Theorem 4]. Definition 5.3. Let D = (L, R, A, ) be an ABAF. A labeling λ is called complete whenever: if a IN(λ), then for each set S A attacking a, it holds that S OUT(λ) = ; if a OUT(λ), then there is some S A attacking a with S IN(λ); if a UNDEC(λ), then i) for each set S A attacking a, it holds that some b S satisfies b / IN(λ) and ii) there is some S A attacking a s.t. S OUT(λ) = . A labeling λ is called preferred if there is no complete labeling λ s.t. IN(λ) IN(λ ).

Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence (IJCAI-24)

Since our backdoor algorithm is based on partially evaluating D, we require the notion of a partial labeling.

Definition 5.4. Let D = (L, R, A, ) be an ABAF. A partial labeling is a partial mapping λ : A {IN, OUT, UNDEC}.

Now we are ready to describe our procedure. Our first step will be to select a set B of assumptions in a way that GD belongs to a certain target class of graphs whenever the nodes corresponding to B are removed. For this we define the restriction of a dependency graph GD in the natural way.

Definition 5.5. Let D = (L, R, A, ) be an ABAF and GD = (V, E, l) its dependency graph. Then (GD) V \B= (V , E , l ) is given via V = V \ B, E = E (V V ), and l (e) = l(e) for each e E .

Now B is called a C-backdoor whenever (GD) V \B belongs to the class C of graphs, i.e., if removing B from GD turns it into a graph with the desired properties.

Definition 5.6. Let D = (L, R, A, ) be an ABAF and let C be a class of graphs. A set B A of assumptions is called a C-backdoor if (GD) V \B belongs to the class C of graphs.

By ACYCDG we denote the class of acyclic dependency graphs and by NOEVENDG the class of no-even ones.

Example 5.7. In Example 5.1, B = {b, e} is a NOEVENDGbackdoor since (GD) V \B does not contain any even-cycle. It is, however, not an ACYCDG-backdoor since it still contains the self-attacker a.

We are now ready to formalize how to treat the ABAF D after we guessed the labels on the backdoor B. Recall from Example 5.1 that we propagated the consequences of our guess. In general, we apply the following rules.

Definition 5.8. Let D = (L, R, A, ) be an ABAF and let λ be a partial labeling. We define λ via

1. set λ (a) = OUT if a Th D(IN(λ )) and

2. set λ (a) = IN if a / Th D(A \ OUT(λ )).

We denote the result of applying these rules to λ (i.e., for each a A \ DEF(λ)) until a fixed point is reached as PROPAGATEIO(D,λ). Then we define λ via

3. set λ (a) = UNDEC if λ (a) = IN and a Th D(A \ OUT(λ )) and

4. set λ (a) = UNDEC if λ (a) = OUT and a / Th D(IN(λ )).

We denote the result of applying these rules to λ (i.e., for each a IN(λ) OUT(λ)) until a fixed point is reached as PROPAGATEUNDEC(D,λ).

Intuitively, the first rule simply formalizes that an assumption a must be labelled out whenever its contrary can be entailed from the assumptions we already assume to be true (e.g. in Example 5.1 d being labelled OUT is a consequence of b being labelled IN). In the same vein, if the contrary of a can only be deduced from assumptions that are already labelled OUT, then a can surely be labelled IN. Then, rules 3. and 4. are necessary in case our guess on the backdoor assumptions is not consistent with the performed propagation (for instance, if we guess a to be true in Example 5.1 it will turn

out that this must be corrected as it attacks itself). Thus, rule 3. corrects labels from IN to UNDEC if necessary; and finally, rule 4. corrects wrongly labelled OUT assumptions. The induced procedure can be found in Algorithm 1. The following theorem formalizes that Algorithm 1 finds all

Algorithm 1 Computing Admissible Candidates Input: ABAF D = (L, R, A, ), NOEVENDG-backdoor B Output: admissible candidates of D: pref (D, B) 1: procedure GETADMISSIBLECANDIDATES(D,B) 2: pref (D, B) = 3: foreach I B do 4: let λ be a partial labeling 5: set λ(a) = IN for a I 6: set λ(a) = OUT for a B \ I 7: λ = PROPAGATEIO(D,λ) 8: set λ (a) = UNDEC for a A \ DEF(λ ) 9: λ = PROPAGATEUNDEC(D,λ ) 10: if IN(λ ) B == I then 11: pref (D, B) = pref (D, B) {IN(λ )} 12: end if 13: end for 14: return pref (D, B) 15: end procedure

preferred extensions of the input ABAF D. It also finds some complete sets which are not preferred, which is why pr (D, B) does not coincide with pr(D). Theorem 5.9. Let D = (L, R, A, ) be a trim ABAF and GD be its dependency graph. Let C {ACYCDG, NOEVENDG} and let B be a C-backdoor. For the output pr (D, B) of Algorithm 1 it holds that pr(D) pr (D, B). We now establish that this procedure is fixed-parameter tractable for ACYCDG-backdoors. First of all, the algorithm itself runs in time 2|B| O(p(n)) for some polynomial p, independent of whether B is a ACYCDG-backdoor or a NOEVENDG-backdoor. Proposition 5.10. Algorithm 1 runs in time 2k O(p(n)) where p is some polynomial, n is the size of the input ABAF, and k the size of the (ACYCDG/NOEVENDG)-backdoor B. In Algorithm 1, the backdoor B is given. Thus the question arises whether or not a backdoor can be computed efficiently. Due to our dependency graph results, this boils down to finding such backdoors in directed graphs. For NOEVENDGbackdoors the fastest known procedure requires time n O(k) [Dvor ak et al., 2012a] (where k is the backdoor size). For ACYCDG-backdoors, however, we find the following. Proposition 5.11. Let D be an ABAF, k be an integer, p be some polynomial and n be size of D. There is a function f s.t. we can find an ACYCDG-backdoor of size at most k in time f(k) p(n) or detect if no such backdoor exists. As a corollary, we obtain that skeptical reasoning for preferred semantics is fixed-parameter tractable in ABA w.r.t. the size of the smallest ACYCDG-backdoor of D. Corollary 5.12. Skeptical acceptance for σ {pr, stb} of a query assumption is fixed-parameter tractable w.r.t. the size of the smallest ACYCDG-backdoor of an ABAF.

Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence (IJCAI-24)

5.2 Empirical Evaluation We now discuss some computational shortcuts we utilize for our actual implementation. We first note that before delving into the cycles of our given ABAF, we can compute the grounded extension G of D as well as the reduct DG, and then remove unnecessary atoms and rules in order to make it trim. Soundness of this is a corollary of Proposition 4.6 and the fact that G E holds for each preferred extension E pr(D). Corollary 5.13. Let D be an ABAF and G gr(D). Then E pr(D) iff E \ G pr(DG). This way we can apply our algorithm to DG which admits smaller backdoors in general compared to D. We also consider two further shortcuts in Algorithm 1: First, if line 9 labels one of the assumptions in I as UNDEC, we can immediately skip the guess (due to line 10). Second, if line 9 does not correct any label in B to UNDEC, then we know that the propagation in line 7 must have been correct as well. So we always iterate through the backdoor B first and if no label is changed in line 9, we can immediately return the IN labeled assumptions. Setup. We implemented the backdoor approach in Python. We used the ASP-solver Clingo [Gebser et al., 2018] to compute a minimal ACYCDG-backdoor. Since we have to compute the deductive closure Th D(S) several times for different assumption sets S, we utilized the Glucose SATsolver [Audemard and Simon, 2018] based on Mini Sat [E en and S orensson, 2004]. This SAT-solver is accessed through the Py SAT library [Ignatiev et al., 2018]. Computations were done using resources of the Leipzig University Computing Center. There we used the Paul Cluster with a memory limit of 32GB ram and with the CPU: 2x AMD EPYC 7713 @ 2.0GHz - Turbo 3.7GHz (64 cores). As experimental data, 400 ABAFs from the ICCMA 2023 competition benchmark generator2 were used. The ABA track was won convincingly by the ASPfor ABA solver [Lehtonen et al., 2021] against which we evaluated our backdoor algorithm. As problem, we enumerated all preferred extensions for some arbitrary ABAF D. A timeout of 90s is used. Results. Our evaluation shows that, as expected, the performance of the backdoor algorithm is quite sensitive to the size of the smallest ACYCDG. We divided the instances into three groups, backdoor size between 0 and 5, between 6 and 10, and greater than 10. Most of the 400 instances (220) belong to the first group with small backdoor sizes in which the backdoor procedure outperforms the state-of-the-art ASPfor ABA solver (first row in Table 1). There are only few instances with backdoor size 5 10. Both algorithms are quite fast in these instances, but ASPfor ABA is better by a small margin (second row). For larger backdoor sizes, however, the ASPfor ABA solver is much better due to the large search space the backdoor algorithm has to handle here (last row).

6 Conclusion We developed and implemented an FPT-algorithm for enumerating preferred extensions in ABA. To this end we considered acyclic backdoors w.r.t. a suitable dependency graph

2https://iccma2023.github.io/benchmarks.html

Approach Av. Total Solved Instances

k 5 Backdoor 0.17 37.29 100% (220/220) ASPfor ABA 1.28 282.30 100% (220/220)

k [6, 10] Backdoor 0.17 4.08 100% (24/24) ASPfor ABA 0.06 1.46 100% (24/24)

11 k Backdoor 89.31 13932.87 1.28% (2/156) ASPfor ABA 22.40 3494.80 80.13% (125/156)

Table 1: Runtimes of our Algorithm 1 and ASPfor ABA in s

notion. The main theoretical observation for this algorithm is that preferred reasoning in ABAFs is fixed-parameter tractable w.r.t. the size of the smallest ACYCDG-backdoor. More broadly, our study shows that the dependency graph can be utilized to examine computational beneficial sub-classes of ABA, similar in spirit to AFs (see e.g. [Dvor ak and Dunne, 2018]). This is in contrast to common cycle notions for ABA focusing on tree derivations [Craven and Toni, 2016], but similar in spirit to logic programming dependency graphs [Apt and Bol, 1994]. Our empirical evaluation demonstrates that our procedure is competitive with state-of-the-art solvers up until an acyclic backdoor size of around 10, which is the case for a significant proportion of the ICCMA 23 instances. Exploiting graph-specific properties for incremental computations has also been done for AFs [Baroni et al., 2005; Baumann and Ulbricht, 2021a; Alfano et al., 2023; Liao, 2013; Liao, 2014]. For instance in [Liao, 2013; Liao, 2014] the AF is divided into sub-graphs in order to utilize the fact that these sub-graphs might fall into certain computationally beneficial fragments. Our modularization notion does not make explicit use of the topology of the dependency graph, but the backdoor algorithm could benefit from a similar decomposition of the knowledge base in order to exploit properties of its subsets. The dependency graph lays the foundation for such a procedure in the context of ABA. Similar in spirit to our work is [Alfano et al., 2021] in the context of defeasible logic programming. In order to analyze dynamic reasoning environments, a hypergraph is used to examine the dependency of literals within the given knowledge base. This work differs from ours as notions such as acyclic or no-even knowledge bases are not studied to gain a computational boost, because the focus is on (efficiency of) dynamic reasoning. Our work, however, is a potential first step towards pushing such an analysis into the realm of ABA. In future work, our theoretical analysis could be continued by considering further ABA classes and theoretical properties induced by dependency graphs. For instance, research for AFs based on the topology of the given argumentation graph can now be rigorously extended to ABA, e.g. the directionality principle [Baroni and Giacomin, 2007] or semantics based on strongly connected components SCCs [Baroni et al., 2005]. Since the backdoor size appears to be the bottleneck for our procedure, another natural avenue for future work consist in adjusting it to NOEVENDG-backdoors. Here, the main challenge will be finding the backdoor efficiently. Moreover, our approach could be generalized to non-flat ABAFs or other rule-based formalisms like ASPIC+ [Modgil and Prakken, 2013].

Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence (IJCAI-24)

Acknowledgements

This word was funded by the Federal Ministry of Education and Research of Germany and by S achsische Staatsministerium f ur Wissenschaft, Kultur und Tourismus in the programme Center of Excellence for AI-research Center for Scalable Data Analytics and Artificial Intelligence Dresden/Leipzig , project identification number: Sca DS.AI.

[Alfano et al., 2021] Gianvincenzo Alfano, Sergio Greco, Francesco Parisi, Gerardo I. Simari, and Guillermo Ricardo Simari. Incremental computation for structured argumentation over dynamic delp knowledge bases. Artif. Intell., 300:103553, 2021.

[Alfano et al., 2023] Gianvincenzo Alfano, Marco Calautti, Sergio Greco, Francesco Parisi, and Irina Trubitsyna. Explainable acceptance in probabilistic and incomplete abstract argumentation frameworks. Artif. Intell., 323:103967, 2023.

[Apt and Bol, 1994] Krzysztof R. Apt and Roland N. Bol. Logic programming and negation: A survey. J. Log. Program., 19/20:9 71, 1994.

[Atkinson et al., 2017] Katie Atkinson, Pietro Baroni, Massimiliano Giacomin, Anthony Hunter, Henry Prakken, Chris Reed, Guillermo Ricardo Simari, Matthias Thimm, and Serena Villata. Towards artificial argumentation. AI Magazine, 38(3):25 36, 2017.

[Audemard and Simon, 2018] Gilles Audemard and Laurent Simon. On the glucose sat solver. International Journal on Artificial Intelligence Tools, 27(01):1840001, 2018.

[Baroni and Giacomin, 2007] Pietro Baroni and Massimiliano Giacomin. On principle-based evaluation of extension-based argumentation semantics. Artif. Intell., 171:675 700, 2007.

[Baroni et al., 2005] Pietro Baroni, Massimiliano Giacomin, and Giovanni Guida. SCC-recursiveness: a general schema for argumentation semantics. Artif. Intell., 168(12):162 210, 2005.

[Baroni et al., 2011] Pietro Baroni, Martin Caminada, and Massimiliano Giacomin. An introduction to argumentation semantics. The Knowledge Engineering Review, 26:365 410, 2011.

[Baroni et al., 2018] Pietro Baroni, Dov Gabbay, Massimiliano Giacomin, and Leendert van der Torre, editors. Handbook of Formal Argumentation. College Publications, 2018.

[Baumann and Ulbricht, 2019] Ringo Baumann and Markus Ulbricht. If nothing is accepted - repairing argumentation frameworks. J. Artif. Intell. Res., 66:1099 1145, 2019.

[Baumann and Ulbricht, 2021a] Ringo Baumann and Markus Ulbricht. Choices and their consequences - explaining acceptable sets in abstract argumentation frameworks. In Proc. KR, pages 110 119, 2021.

[Baumann and Ulbricht, 2021b] Ringo Baumann and Markus Ulbricht. On cycles, attackers and supporters - A contribution to the investigation of dynamics in abstract argumentation. In Proc. IJCAI, pages 1780 1786. ijcai.org, 2021. [Baumann et al., 2020] Ringo Baumann, Gerhard Brewka, and Markus Ulbricht. Comparing Weak Admissibility Semantics to their Dung-style Counterparts Reduct, Modularization, and Strong Equivalence in Abstract Argumentation. In Proc. KR, pages 79 88, 9 2020. [Baumann et al., 2022] Ringo Baumann, Gerhard Brewka, and Markus Ulbricht. Shedding new light on the foundations of abstract argumentation: Modularization and weak admissibility. Artif. Intell., 310:103742, 2022. [Baumann, 2011] Ringo Baumann. Splitting an argumentation framework. In Proc. LPNMR, volume 6645 of Lecture Notes in Computer Science, pages 40 53. Springer, 2011. [Besnard and Hunter, 2008] Philippe Besnard and Anthony Hunter. Elements of Argumentation. MIT Press, 2008. [Besnard et al., 2014] Philippe Besnard, Alejandro Garcia, Anthony Hunter, Sanjay Modgil, Henry Prakken, Guillermo Simari, and Francesca Toni. Introduction to structured argumentation. Argument Comput., 5(1):1 4, 2014. [Bondarenko et al., 1997] Andrei Bondarenko, Phan Minh Dung, Robert A. Kowalski, and Francesca Toni. An abstract, argumentation-theoretic approach to default reasoning. Artif. Intell., 93:63 101, 1997. [Craven and Toni, 2016] Robert Craven and Francesca Toni. Argument graphs and assumption-based argumentation. Artif. Intell., 233:1 59, 2016. [ ˇCyras et al., 2018] Kristijonas ˇCyras, Xiuyi Fan, Claudia Schulz, and Francesca Toni. Assumption-based argumentation: Disputes, explanations, preferences. In Handbook of Formal Argumentation, chapter 7, pages 365 408. College Publications, 2018. [Cyras et al., 2021] Kristijonas Cyras, Antonio Rago, Emanuele Albini, Pietro Baroni, and Francesca Toni. Argumentative XAI: A survey. In Proc. IJCAI, pages 4392 4399. ijcai.org, 2021. [Dung, 1995] Phan Minh Dung. On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games. Artif. Intell., 77(2):321 357, 1995. [Dunne, 2007] Paul E. Dunne. Computational properties of argument systems satisfying graph-theoretic constraints. Artif. Intell., 171(10-15):701 729, 2007. [Dvor ak and Dunne, 2018] Wolfgang Dvor ak and Paul E. Dunne. Computational problems in formal argumentation and their complexity. In Handbook of Formal Argumentation. College Publications, February 2018. [Dvor ak et al., 2012a] Wolfgang Dvor ak, Sebastian Ordyniak, and Stefan Szeider. Augmenting tractable fragments of abstract argumentation. Artif. Intell., 186:157 173, 2012.

Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence (IJCAI-24)

[Dvor ak et al., 2012b] Wolfgang Dvor ak, Reinhard Pichler, and Stefan Woltran. Towards fixed-parameter tractable algorithms for abstract argumentation. Artif. Intell., 186:1 37, 2012.

[Dvor ak et al., 2022a] Wolfgang Dvor ak, Markus Hecher, Matthias K onig, Andr e Schidler, Stefan Szeider, and Stefan Woltran. Tractable abstract argumentation via backdoor-treewidth. In Proc. AAAI, pages 5608 5615. AAAI Press, 2022.

[Dvor ak et al., 2022b] Wolfgang Dvor ak, Matthias K onig, and Stefan Woltran. Deletion-backdoors for argumentation frameworks with collective attacks. In Proc. SAFA, volume 3236 of CEUR Workshop Proceedings, pages 98 110. CEUR-WS.org, 2022.

[E en and S orensson, 2004] Niklas E en and Niklas S orensson. An extensible sat-solver. In Theory and Applications of Satisfiability Testing, pages 502 518, Berlin, Heidelberg, 2004. Springer Berlin Heidelberg.

[Falappa et al., 2009] Marcelo Alejandro Falappa, Gabriele Kern-Isberner, and Guillermo Ricardo Simari. Belief revision and argumentation theory. In Argumentation in Artificial Intelligence, pages 341 360. 2009.

[Garc ıa and Simari, 2004] Alejandro Javier Garc ıa and Guillermo Ricardo Simari. Defeasible logic programming: An argumentative approach. Theory Pract. Log. Program., 4(1-2):95 138, 2004.

[Gebser et al., 2018] Martin Gebser, Roland Kaminski, Benjamin Kaufmann, and Torsten Schaub. Multi-shot asp solving with clingo, 2018.

[Haret et al., 2018] Adrian Haret, Johannes Peter Wallner, and Stefan Woltran. Two sides of the same coin: Belief revision and enforcing arguments. In Proc. IJCAI, pages 1854 1860, 2018.

[Ignatiev et al., 2018] Alexey Ignatiev, Antonio Morgado, and Joao Marques-Silva. Py SAT: A Python toolkit for prototyping with SAT oracles. In SAT, pages 428 437, 2018.

[K onig et al., 2022] Matthias K onig, Anna Rapberger, and Markus Ulbricht. Just a matter of perspective. In Proc. COMMA, volume 353 of Frontiers in Artificial Intelligence and Applications, pages 212 223. IOS Press, 2022.

[Lehtonen et al., 2021] Tuomo Lehtonen, Johannes Peter Wallner, and Matti J arvisalo. Harnessing incremental answer set solving for reasoning in assumption-based argumentation. Co RR, abs/2108.04192, 2021.

[Lehtonen et al., 2023] Tuomo Lehtonen, Anna Rapberger, Markus Ulbricht, and Johannes Peter Wallner. Argumentation frameworks induced by assumption-based argumentation: Relating size and complexity. In Proc. KR, pages 440 450, 2023.

[Liao et al., 2018] Beishui Liao, Kang Xu, and Huaxin Huang. Formulating semantics of probabilistic argumentation by characterizing subgraphs: theory and empirical results. J. Log. Comput., 28(2):305 335, 2018.

[Liao, 2013] Beishui Liao. Toward incremental computation of argumentation semantics: A decomposition-based approach. Ann. Math. Artif. Intell., 67(3-4):319 358, 2013. [Liao, 2014] Beishui Liao. Efficient Computation of Argumentation Semantics. Intelligent systems series. Academic Press, 2014. [Modgil and Prakken, 2013] Sanjay Modgil and Henry Prakken. A general account of argumentation with preferences. Artif. Intell., 195:361 397, 2013. [Niskanen et al., 2018] Andreas Niskanen, Johannes Peter Wallner, and Matti J arvisalo. Extension enforcement under grounded semantics in abstract argumentation. In Proc. KR, pages 178 183, 2018. [Popescu and Wallner, 2023] Andrei Popescu and Johannes Peter Wallner. Reasoning in assumption-based argumentation using tree-decompositions. In Proc. JELIA, volume 14281 of Lecture Notes in Computer Science, pages 192 208. Springer, 2023. [Rapberger et al., 2022] Anna Rapberger, Markus Ulbricht, and Johannes Peter Wallner. Argumentation frameworks induced by assumption-based argumentation: Relating size and complexity. In Proc. NMR, volume 3197 of CEUR Workshop Proceedings, pages 92 103. CEUR-WS.org, 2022. [Schulz and Toni, 2017] Claudia Schulz and Francesca Toni. Labellings for assumption-based and abstract argumentation. Int. J. Approx. Reason., 84:110 149, 2017. [Wallner et al., 2017] Johannes Peter Wallner, Andreas Niskanen, and Matti J arvisalo. Complexity results and algorithms for extension enforcement in abstract argumentation. J. Artif. Intell. Res., 60:1 40, 2017.

Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence (IJCAI-24)