Preferred Reasoning in ABA by Cycle-Breaking

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 DeLP [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;

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 online 1 .

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 ↦→ σ(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}.

1 https://github.com/kietGithubUser/ 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 ThD(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 ⊆ ThD(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) = ⋃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 ∈ ThD(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 ∈ ⋃ σ(D) (iff σ(D) ̸= ∅ and a ∈ ⋂ σ(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.

3 ABAClasses

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.

• 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 ABADependency 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:

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.

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 = ThD(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 trimD, 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 ABAReduct

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 ⊆ Awe 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 ,

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:

Let S = {c}. In the reduct DS , c is set to true and since ac ∈ ThD(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).

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.

Theorem4.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 ⋃ 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:

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(λ′ ).

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 ∈ ThD(IN(λ∗ )) and
2. set λ∗ (a) = IN if a /∈ ThD(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

1. set λ† (a) = UNDEC if λ† (a) = IN and a ∈ ThD(A \ OUT (λ† )) and
2. set λ† (a) = UNDEC if λ† (a) = OUT and a /∈ ThD(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).

Theorem5.9. Let D = (L,R,A, ) be a trimABAF 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 nO(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.

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).

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 ThD(S) several times for different assumption sets S, we utilized the Glucose SATsolver [Audemard and Simon, 2018] based on MiniSat [E´en and S¨orensson, 2004]. This SAT-solver is accessed through the PySAT 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 generator 2 were used. The ABA track was won convincingly by the ASPforABA 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 ASPforABA 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 ASPforABA is better by a small margin (second row). For larger backdoor sizes, however, the ASPforABA 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 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.

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

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].

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: ScaDS.AI.