On Cycles, Attackers and Supporters --- A Contribution to The Investigation of Dynamics in Abstract Argumentation

1 Introduction

Abstract argumentation as defined by Dung in his seminal paper [Dung, 1995] is by now a major research area in knowledge representation and reasoning. Around the beginning of the 2010s several problems regarding dynamics of abstract argumentation have been addressed in the literature [Boella et al., 2009; Cayrol et al., 2010; Bisquert et al., 2011; Liao et al., 2011]. Within argumentation dynamics, a major strand of research is concerned with the so-called enforcing problem dealing with the question of how to modify a given AF such that a desired set of arguments becomes an extension [Baumann and Brewka, 2010; Baumann, 2012;

Doutre and Mailly, 2018; Wallner, 2020; Wallner et al., 2017]. In this paper we continue another line of research, namely the formal study of syntactic manipulations preserving the acceptability status of former extensions and/or single arguments. Consider the following example.

Example 1.1 (Preserving acceptability). The graph below represents two AFs F and Fx, s.t. x and its associated attacks are contained in F but not in Fx. The two sets E1 = {a, b1} and E2 = {a, b2} are so-called preferred extensions of F (cf. background section). It is interesting to see that these sets semantically survive if we syntactically remove x. Note that x attacks both extensions. Moreover, deleting b, which also questions both sets would result in the same monotonic behavior. We will see that this is no coincidence since this kind of acceptability preserving can be shown formally.

In the second main part we consider how to infer syntactical information from semantical information. This line of research was already initiated by Dung. For instance, it is well-known that if a finite AF possesses no stable extension, then it has to contain an odd-cycle. We will strengthen this result in by presenting a first characterization of this issue. Further results are in the following spirit: If the number of stable extensions changes (semantical information) if moving from F to Fx, then there has to be a cycle in F (existence of cycles), s.t. x possesses a path to it (existence of a path).

The paper is organized as follows:

• We provide the formal background in Section 2.
• We investigate the impact of removing (Section 3) and adding (Section 4) arguments on the given AF.
• In Section 5, we focus on syntactical information that can be inferred about the AF at hand.

Throughout the paper we distinguish semantics based on admissibility and naivity [van der Torre and Vesic, 2018], with a special focus on the former. In the last part of the paper we briefly discuss and compare our results and present pointers for future work. Due to the limited space we present particularly interesting proofs only.

2 Formal Background

Syntax. We fix a non-finite background set U. An argumentation framework (AF) [Dung, 1995] is just a directed graph F = (A,R) with a set of arguments A ⊆ U and the attack relation R ⊆ A × A. If not stated otherwise we assume any AF to be finite and we use F for the set of all these graphs. If (a, b) ∈ R we say that a attacks b as well as a attacks (the set) E given that b ∈ E ⊆ A. This situation is denoted as a → b or a → E, respectively. The meaning of E → a is analogous.

We frequently use the so-called range of a set E defined as E⊕ = E ∪ E+ where E+ = {a ∈ A | E attacks a}. We also let E- = {a ∈ A | a attacks E}. The E-reduct of F is the AF F E = (E∗ , R ∩ (E∗ × E∗ )) where E∗ = A \ E⊕. This means, F E is the subframework of F obtained by removing the range of E. For an argument x, we use Fx for the induced AF without x, i.e. Fx = (A \ {x}, R ∩ (A \ {x} × A \ {x})).

A sequence a0, a1, . . . , an with ai → ai+1 for 0 ≤ i < n and ai ̸= aj for 0 ≤ i < j < n is called a path. If n is odd, then it is an attack path, otherwise we call it support path. If additionally an = a0 we call the path a cycle. A cycle is odd if |{a0, a1, . . . , an}| is odd, otherwise even. We say a purely attacks (purely supports) b if each path from a to b is an attack (support) path. Moreover, we say a is controversial w.r.t. b if there are both attack and support paths from a to b. We mention that it is intended that by the above definitions an argument a with no path at all to b is both a pure supporter and a pure attacker of it, but not controversial.

Semantics. A semantics is a function σ : F → 22U with F = (A, R) ↦→ σ(F) ⊆ 2A. This means, a semantics returns a set of subsets of A, so-called σ-extensions. We say that an argument a ∈ A is credulously accepted if a ∈ ⋃ σ(F). Similarly, a is considered as skeptically accepted if |σ(F)| ≥ 1 and a ∈ ⋂ σ(F). In case of uniquely defined semantics, i.e. |σ(F)| = 1 for any F we may simply speak of accepted arguments as both notions coincide.

In this paper we consider so-called naive, stage, admissible, complete, preferred, grounded and stable semantics (abbr. na, stg, ad, co, pr, gr, stb) [Dung, 1995; Verheij, 1996]. All mentioned semantics satisfy conflict-freeness. A set E ⊆ A is conflict-free in F (for short, E ∈ cf (F)) iff for no a, b ∈ E, a → b. For the present paper it will be convenient to utilize the so-called characteristic function ΓF : For E ⊆ A we have ΓF (E) = {a ∈ A | E defends a}. A set E defends a if any attacker of a is attacked by some argument of E.

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

1. E ∈ na(F) iff E is ⊆-maximal in cf (F),
2. E ∈ stg(F) iff E ∈ na(F) and E⊕ is ⊆-maximal in {I ⊕ | I ∈ na(F)},
3. E ∈ ad(F) iff E ⊆ ΓF (E),
4. E ∈ co(F) iff E = ΓF (E),
5. E ∈ pr(F) iff E is ⊆-maximal in co(F),
6. E ∈ gr(F) iff E = ⋃i∈N ΓF (∅),
7. E ∈ stb(F) iff E attacks any a ∈ A \ E.

3 Acceptability and Removal of Arguments

In this section we investigate the impact of removing arguments from a given AF F on the acceptability status of former extensions or single arguments.

3.1 Preserving Extensions

Let us start with the following question:

Given some E ∈ σ(F ), under which conditions can

E ∈ σ(Fx) be guaranteed?

Admissibility-based Semantics

Our first results is regarding admissible and stable extensions. On the one hand, they are quite different: Stable extensions are among the most restricted ones in the literature, while admissibility is such a basic concept that a whole family of semantics exists on top of the admissibility requirement. However, they have something essential in common: Both require E to be conflict-free and that E+ is sufficiently large. This common ground yields the following result.

Proposition 3.1. Given an AF F , a semantics σ ∈ {ad, stb} and E ∈ σ(F). If x /∈ E, then E ∈ σ(Fx).

Does the above assertion conveys to complete, preferred and grounded semantics? The following example provides us with a negative answer.

Example 3.2. Let F be as depicted below.

We have gr(F) = co(F) = pr(F) = {∅} and obviously x /∈ ∅. The fact gr(Fx) = co(Fx) = pr(Fx) = {{a}} proves that the empty set does not survive changing F to Fx.

However, if we require that "x is an immediate attacker of E" we obtain the persistence of E again. Note that this condition is indeed a strengthening of "not being contained in E" since the latter is implied by the conflict-freeness of the considered semantics.

Theorem 3.3. Given an AF F , σ ∈ {ad , stb, co, pr , gr} and E ∈ σ(F). If x →E, then E ∈ σ(Fx).

Naivity-based Semantics.

We start by stating the counterpart to Proposition 3.1 in case of naive semantics.

Proposition 3.4. Let F be an AF. If E ∈ na(F) and x /∈ E, then E ∈ na(Fx).

For stage semantics these assumptions are too weak as the following example shows.

Example 3.5. Consider the following AF F:

We have stg(F) = {{a}, {b}} since the ranges {a}⊕ and {b}⊕ are incomparable, but stg(Fx) = {{b}}.

Indeed, we require stronger assumptions for stage semantics. The intuitive reason is that we mainly take the range of E into consideration and only check conflict-freeness of the extension itself. Hence if we make sure that removing x does not undermine E⊕, then E survives the transition to Fx.

Proposition 3.6. Let F be an AF. If E ∈ stg(F) and x /∈ E⊕, then E ∈ stg(Fx).

The reader is presumably not surprised about the fact that we did not make any assumption about incoming attacks (cf. Propositions 3.4 and 3.6). The intuitive reason is that naivitybased semantics do not tend to take incoming attacks seriously.

3.2 Credulous Acceptance

Let us now focus on acceptability of single arguments, rather than whole extensions. More concisely:

Given some credulously accepted argument a in F , under which conditions is a still accepted in Fx?

From an intuitive point of view, a support path from x to a should be beneficial for the acceptance of a whereas an attack path should be harmful. This means, deleting benificial paths may cause non-acceptance and deleting harmful ones should not change the former acceptance as already proven for direct attackers in Theorem 3.3.

Admissibility-based Semantics

We start with showing that there is no analogy to Theorem 3.3 in case of pure attackers because they themselves could be part of a given extension E. Remember that for pure attackers each path to arguments in the set has to be odd.

Example 3.7. We find E = {x, f, a} ∈ pr (F ). Moreover, x purely attacks E.

However, obviously E /∈ pr(Fx) since x is not even contained in Fx. Please observe that a and f are still credulously accepted in Fx since {c, f, a} ∈ pr(Fx).

The last observation can be formally proven for several admissible-based semantics. This means, although whole extensions do not necessarily survive we may at least ensure credulous acceptance.

Proposition 3.8. Given an AF F, σ ∈ {ad, co, pr} as well as two arguments a ∈ ⋃ σ(F) and x ̸= a. If x purely attacks a, then a ∈ ⋃ σ(Fx).

Proof. It suffices to show the assertion for admissible sets since ⋃ ad(G) = ⋃ pr(G) = ⋃ co(G) for any AF G.

Given F = (A,R) and let a ∈ E′ ∈ ad(F). If x /∈ E′ , then Proposition 3.1 ensures the credulous acceptance of a in Fx since E′ ∈ ad(Fx). Consider now x ∈ E′ . We inductively construct a set E ⊆ E′ with E ∈ ad(Fx) and a ∈ E. We set:

• E0 = {a},
• S0 = {d ∈ A \ E+ 0 | d →E0} and
• E1 = (S0 ∩E′ ) \ E0

Note that since E′ is admissible in F we always find arguments in E′ counter-attacking all arguments in S0. This means, E0 ˙∪E1 defends a. In general, assume we are given an integer n as well as E0, . . . , En. We proceed as follows:

• Sn = {d ∈ A \ (E0 ˙∪ . . . ˙∪En)+ | d →En}
• En+1 = (Sn ∩E′ ) \ En.

This way we obtain a sequence E1, . . . , En+1 of pairwise disjoint sets. We show that for each n

1. each argument in En+1 possesses a support path to a,
2. ii) E0 ˙∪ . . . ˙∪En+1 defends En, and

(base case) i) We have E0 = {a}. ii) E0 ∪ E1 = S0 ∩E′ defends E0 since E′ is admissible. iii) Since S0 ⊆ (E0∪E1)+, S1 ∩ S0 = ∅ by construction.

For the inductive step let the assertion be true for some integer n.

i) If En+1 is empty, we are done. Otherwise let e ∈ En+1. Then e attacks some s ∈ Sn which in turn attacks some e′ ∈ En. Since e′ possesses some support path to a and all sets are disjoint, we found our support path from e to a.

• ii) Due to admissibility of E′ we have Sn+1 ∩ E′ = Sn+1 and from En+2 = (Sn+1 ∩ E′ ) \ En+1 we hence infer that E1 ˙∪ . . . ˙∪En+2 defends En+1.

iii) Hence the set Sn+1 of attackers of En+1 not occurring in the range of E1 ˙∪ . . . ˙∪En+1 must be disjoint with Si, 0 ≤ i ≤ n.

This finishes our induction. Since x is a pure attacker of a we conclude x /∈ En for each n. We thus have for each integer n that 0) ⋃ni=1 Ei ⊆ E′ ∈ cf (F), 1) x /∈ ⋃ni=1 Ei, and 2) ⋃ni=1 Ei defends En-1. Due to finiteness, ⋃i∈N Ei is an admissible extension of F containing a, but not x.

Observe that the proof above is constructive. This means, it shows how to obtain a witnessing set for credulous acceptance as illustrated in the following example.

Example 3.9. In Example 3.7, a ∈ {x, f, a} ∈ pr(F). Obviously, x purely attacks a, a ∈ ⋃ ad(F) and x ̸= a. So we find E0 = {a}, E+ 0 = ∅ as well as S0 = {b}. Since S0 = {c, f} we get E1 = (S0 ∩ {x, f, a}) \ E0 = {f}. Observe that the only attacker of E1 is e and moreover, e ∈ (E0 ˙∪E1)+ = {a, f}+ = {e, b}. This means we get S1 = {b ∈ A \ (E0 ˙∪E1)+ | b →E1} = ∅ and E2 = ∅, too. The procedure stops and outputs E0 ˙∪E1 = {a, f} and we verify that a ∈ {a, f} ∈ ad(Fx) as required.

The attentive reader may have noted that so far, the case of grounded semantics is still missing. 1 Indeed, an analogous result can be shown here, but the proof needs to be adjusted since credulous acceptance for σ = gr is more restrictive than in the previous cases.

Proposition 3.10. Given an AF F as well as a ∈ ⋃ gr(F) and x ̸= a. If x purely attacks a, then a ∈ ⋃ gr(Fx).

1 Proposition 3.10 can also be inferred from [Cayrol et al., 2010, Proposition 7]. However, we noted a sneaky error in the proof, which is about the existence of attack paths: If x is a pure attacker of a and y has support paths to a, then - although counter-intuitive at first glance - x is not necessarily a pure attacker of y. We thus decided to give a novel proof.

Proof. Let G be the grounded extension of F. If x /∈ G, then the claim follows since we obtain ΓiF (∅) ⊆ ΓiFx (∅) for each integer i ≥ 1.

If x ∈ G, we consider the procedure from the proof of Proposition 3.8. This way, we obtain an admissible extension E of F with a ∈ E and x /∈ E. Since E ⊆ G and by definition of the grounded extension, E can be traced back to unattacked arguments, i.e. there is a sequence E0, . . . , En s.t. i) E = E0 ˙∪ . . . ˙∪En, ii) E0 is unattacked in F, and iii) Ei-1 defends Ei for each 1 ≤ i ≤ n. One can verify that these properties also hold in Fx and hence, E ⊆ Gx for the grounded extension Gx of Fx.

Combining all results leads to the following final theorem regarding pure attackers.

Theorem 3.11. Given an AF F , σ ∈ {ad , co, pr , gr} as well as two arguments a ∈ ⋃ σ(F) and x ̸= a. If x purely attacks a, then a ∈ ⋃ σ(Fx).

This theorem in turn helps us to obtain the analogous result for pure supporters.

Theorem 3.12. Given an AF F , σ ∈ {ad , co, pr , gr} as well as two arguments a /∈ ⋃ σ(F) and x ̸= a. If x purely supports a, then a /∈ ⋃ σ(Fx).

Naivity-based Semantics

We start with mentioning that neither Theorem 3.11, nor Theorem 3.12 hold for stable semantics. This means, the deletion of pure attackers or pure supporters of an argument may indeed negate its former credulous acceptance or non-acceptance. The following example illustrates this assertion for pure attackers.

Example 3.13. Let F be as depicted below. We have that stb(F ) = {{a, x}, {b, e, x}} and x is a pure attacker of a.

However, stb(Fx) = {{b, d}} showing that a is not credulously accepted anymore.

For stable semantics, it suffices to assume that a attacks x: Proposition 3.14. Given an AF F as well as a ∈ ⋃ stb(F) and x ̸= a. If a → x, then a ∈ ⋃ stb(Fx).

For naive semantics, we find that a is accepted in Fx whenever x and a are different. As for stb this does not depend on the kind of paths from x to a in F .

Proposition 3.15. Given an AF F as well as two arguments x ̸= a. If a ∈ ⋃ na(F), then a ∈ ⋃ na(Fx).

We also present some first result concerned with stage semantics. The assumptions we make are rather restrictive and closely related to Proposition 3.6. The reason is that it is hard to predict the structure of stg(F) after removing a certain argument. Finding milder conditions ensuring an analogous result is left for future work.

Proposition 3.16. Given an AF F and two arguments a and x. If there is some E ∈ stg(F) with a ∈ E and x /∈ E⊕, then a ∈ ⋃ σ(Fx).

4 Acceptability and Addition of Arguments

4.1 Preserving Extensions

In the following we consider a subclass of normal expansions [Baumann and Brewka, 2010], so-called x-expansions firstly introduced in [Cayrol et al., 2010]. The former adds new arguments and attacks to F, but does not introduce novel attacks within F. The latter is a special case of normal expansions, where only one argument x is added to F .

Definition 4.1. The AF G = (B, S) is a x-expansion of an AF F = (A, R) whenever i) B = A ˙∪ {x} and ii) if (a, b) ∈ S\R, then a = x or b = x.

Example 4.2. Consider the x-expansion G of F. We have ad(F) = {∅, {c}, {c, a}}. Hence, x does not attack any admissible set.

We observe that any admissible set survives since we obtain ad (G) = {∅, {c}, {c, a}, {x}, {x, c}, {x, c, a}}.

The following proposition shows that the above observation holds in general.

Proposition 4.3. Let G be an x-expansion of F = (A,R) and E ∈ ad(F). If x ̸→E, then E ∈ ad(G).

Example 4.2 reveals that the above assertion is not true for the remaining semantics. Indeed, {c, a} is stable, preferred, complete and grounded in F, but not in G. Apart from grounded semantics we may state that the extension E survives if E attacks x.

Proposition 4.4. Let G be an x-expansion of F, E ∈ σ(F) with σ ∈ {ad, co, pr, stb}. If E → x, then E ∈ σ(G).

This does not suffice for the grounded extension since x may ensure that G does not contain any unattacked arguments.

Example 4.5. The following AFs exemplify Proposition 4.4. However, for grounded semantics we have gr(F) = {{c, a}} and gr (G) = {∅}.

In fact, in order to ensure that the grounded extension survives the x-expansion we have to combine the requirements of Propositions 4.3, 4.4.

Proposition 4.6. Let G be an x-expansion of F = (A,R) and E ∈ gr(F). If x ̸→E and E → x, then E ∈ gr(G).

Let us now turn to naivity-based semantics. If we have neither x → E nor E → x for some E ∈ cf (F ), then E∪{x} is conflict-free as well. Hence in this case E cannot be naive in the x-expansion G. Otherwise, we obtain the following:

Proposition 4.7. Let G be an x-expansion of F = (A,R) and E ∈ na(F). If x →E or E → x, then E ∈ na(G).

For stage semantics it might happen that F possesses no stable extension at all, and stb(G) = stg(G) = {x}. Hence it is clear that an analogous result for stage semantics can only be inferred under quite restrictive conditions; for example whenever x cannot be in any extension itself.

Proposition 4.8. Let G be an x-expansion of F = (A,R) and E ∈ stg(F). If E → x and x → x, then E ∈ stg(G).

Again, finding milder conditions ensuring an analogous result is left for future work.

4.2 Credulous Acceptance

In this section we will strongly benefit from previous results and show that the credulous (non-)acceptance of arguments is intimately linked to the addition of pure attackers and pure supporters. The decisive point is that by definition of an xexpansion G of F we have Gx = F .

Theorem 4.9. Given an AF F = (A,R) and a semantics σ ∈ {ad, co, pr , gr}. Let a ∈ A with a /∈ ⋃ σ(F). If G is an x-expansion of F , s.t. x purely attacks a, then a /∈ ⋃ σ(G).

Theorem 4.10. Given an AF F = (A,R) and a semantics σ ∈ {ad, co, pr , gr}. Let a ∈ A with a ∈ ⋃ σ(F). If G is an x-expansion of F , s.t. x purely supports a, then a ∈ ⋃ σ(G).

Regarding naivity-based semantics, the case σ = na is based on the observation that any argument occurs in a naive extension iff it is no self-attacker.

Proposition 4.11. Given an AF F = (A, R) and an argument a ∈ A with a ∈ ⋃ na(F). If G is an x-expansion of F , then a ∈ ⋃ na(G).

Considering stage semantics, we require quite strong assumptions as it was the case in Proposition 4.6.

Proposition 4.12. Given an AF F = (A, R) and a ∈ A with a ∈ ⋃ stg(F). If G is an x-expansion of F with a → x and x → x, then a ∈ ⋃ stg(G).

5 On Cycles, Circuits and Infinite Sequences

This section is dedicated to cycles in AFs.

5.1 Revisiting and Strengthening Former Results

In the argumentation community the following two results are widely known as well as frequently used in proofs.

Proposition 5.1. Any odd-cycle-free F possesses at least one stable extension.

Proposition 5.2. Any acyclic F has exactly one complete extension which is grounded, preferred and stable.

However, inspecting the seminal paper [Dung, 1995] reveals that neither of those assertions was presented by Dung. Even worse, both propositions are wrong if not restricted properly. For instance, Example 5.4 presents an acyclic (hence oddcycle free) AF which does not possess any stable extension [Baumann and Spanring, 2015, Example 2]. Dung formulated Proposition 5.1 with "limited controversial" instead of "oddcycle-free" [Dung, 1995, Corollary 36] and Proposition 5.2 with "well-founded" instead of "acyclic" [Dung, 1995, Theorem 30]. Both concepts are actually closer to the definition of a so-called circuit than the one of a cycle. The former generalizes the concept of a cycle by tolerating the repetition of vertices (not only the first/last vertex).

Definition 5.3. An AF F is well-founded if there is no infinite sequence a0, a1, . . . with ai+1 → ai for each i ≥ 1; F is limited controversial if there exists no infinite sequence a0, a1, . . . s.t. ai+1 is controversial wrt. ai for each i ≥ 1.

Example 5.4. Consider the following infinite AF F.

The AF is not well-founded since it possesses an infinite attack sequence, namely a0, a1, . . .. It is not limited controversial, either, because of the sequence a0, a2, a4 . . .: We have that a2n+2 is controversial to a2n witnessed by the support path a2n+2, a2n+1, a2n and the attack path a2n+2, a2n.

The following two Lemmata justify Propositions 5.1 and 5.2 as they allow to translate Dungs original versions into the usually quoted ones in the realm of finiteness.

Lemma 5.5. Let F be a finite AF. The following statements are equivalent: i) There is no cycle in F, ii) there is no circuit in F, iii) there is no even circuit in F, iv) F is well-founded.

Lemma 5.6. Let F be a finite AF. The following statements are equivalent: i) There is no odd cycle in F, ii) there is no odd circuit in F, iii) F is limited controversial.

We want to emphasize that Lemmata 5.5 and 5.6 do not hold for infinite AFs. Hence infinite AFs with no stable extension do not necessarily contain odd cycles. Indeed, the AF from Example 5.4 is acyclic, yet not limited controversial.

Dung's controversiality notion is rarely used and most papers in the literature focus on finite AFs anyway. In this regard Dung's proof seems unnecessarily complicated and we hence decided to provide a concise proof tailored for finite AFs only. The recently introduced modularization property plays the key role in this proof and underlines again its important role in the foundations of abstract argumentation [Baumann et al., 2020a]. Besides this, our proof relies on the notion of directionality [Baroni and Giacomin, 2007] showing nicely how we can benefit from former foundational research here.

Proof of Proposition 5.1. The punchline is at follows: We show that if F is odd-cycle free, then it contains a non-empty admissible set. We may then argue as follows: There is a preferred extension E ∈ pr(F). Assume that E is not stable in F. Thus, F E is non-empty. Now, since the reduct contains a non-empty admissible extension E′ , then E ∪ E′ ∈ ad(F) by [Baumann et al., 2020a, Proposition 3.4], contradiction.

We have thus left to prove the existence of such a non-empty admissible extension. This is equivalent to the existence of a non-empty complete one. Due to the directionality principle [Baroni and Giacomin, 2007, Section 3.3 and Table 1], it suffices to proof the claim for an AF F forming an SCC. Consider a circuit C = (a1, . . . , an) through all arguments in A and let E = ⋃ a2n-1. Trivially, E⊕ = A. Moreover, if E was conflicting we would immediately obtain an odd sub-circuit, yielding a contradiction via Lemma 5.6. Hence, E ∈ stb(F) ⊆ co(F) concluding the proof.

The following theorem sharpens Dung's result regarding the existence of stable extensions as it presents the very first characterization of this issue. This means, we provide a sufficient and necessary condition for the existence of a stable extension. For notational convenience we use OC(F) = {{a0, a1 . . . , an} | a0, a1, . . . , an is an odd-cycle in F}.

Theorem 5.7. Given a finite AF F . stb(F) ̸= ∅ if and only if ∃E ∈ ad(F) s.t. E+ ∩ C ̸= ∅ for each C ∈ OC(F).

Proof. (⇒) If E ∈ stb(F), then E⊕ ∩ C ̸= ∅ by definition for any C ∈ OC(F). Moreover, by the definition of a cycle, E⊕ ∩ C ̸= ∅ implies E+ ∩ C ̸= ∅.

(⇐) Let E ∈ ad(F ) with E+ ∩ C ̸= ∅ for each odd cycle C. Now the reduct F E is odd-cycle free. There is thus a stable extension E′ ∈ stb (F E ) due to Proposition 5.1. Since each stable extension is trivially admissible, E ∪ E′ ∈ ad(F) due to [Baumann et al., 2020a, Proposition 3.4]. However, by assumption (E ∪E′ )⊕ = A and hence E ∪E′ ∈ stb(F ).

We want to emphasize that the "⇐"-direction in Theorem 5.7 is the crucial one as it provides a sufficient condition for the existence of a stable extension. Roughly speaking, if we find an admissible extension which is capable of disrupting all odd cycles in F , then the AF possesses stable extensions.

5.2 Derivable Syntactical Implications

As recalled in the previous section, oftentimes semantical properties yield syntactical conditions a given AF must satisfy. In this section we return to our initial setting and investigate derivable connections between F and Fx. More specifically we address the following issue:

Given some connection between |σ(F)| and |σ(Fx)|, which connections between x and cycles occurring in F can be guaranteed?

Most of the presented results utilize the following observation as important cornerstone (see also [Dunne and Bench-Capon, 2001, Theorem 8] and [Dvoˇr´ak, 2012, Proposition 15]).

Lemma 5.8. Let σ ∈ {co, pr , stb} and E, E′ ∈ co(F). Then E ̸= E′ iff there is an argument a contained in an even cycle with a ∈ E and a /∈ E′ .

We proceed with the main results of this section. Most of them utilize analogous proof techniques, with suitable adjustments tailored for the given situation. We thus decided to demonstrate the technique only once and omit the remaining proofs due to space restrictions.

Theorem 5.9. Let σ ∈ {co, pr}. Let F be an AF with |σ(Fx)| ̸= |σ(F)|. Then there is some path from x to an even cycle in F .

Proof. Let σ = co (the other case is similar). Assume there is no such path. We show |co(Fx)| = |co(F)|.

Given Ex ∈ co(Fx), let us consider the whole AF F. We let P ⊆ A be the arguments s.t. there is a path from a to P. We let C be the arguments contained in an even cycle. By assumption, all even cycles in F are contained in A\P . Since there is no path from P to any argument in A\P , Ex∩(A\P) is admissible in F by the directionality principle [Baroni and Giacomin, 2007]. Hence there is some complete extension E of F with Ex ∩ (A \ P) ⊆ E. Now E and Ex coincide on all arguments occurring in an even cycle. Since this uniquely determines E ∈ co(F) (see Lemma 5.8) this induces a oneto-one mapping co(Fx) → co(F ) by letting Ex ↦→ E; we get |σ(Fx)| ≤ |σ(F)|. Starting the same line of reasoning with E ∈ co(F) yields |σ(F)| ≤ |σ(Fx)|.

While even cycles provide alternatives, odd ones oftentimes constrain the set of extensions. The following theorem formalizes that a connection to an odd cycle can be found, whenever x is responsible for rendering σ(F) trivial.

Theorem 5.10. If ad(F) = {∅} as well as ad(Fx) ̸= {∅}, then there is some path from an odd cycle to x in F .

Observe that these results transfer to σ ∈ {co, pr} since ad(F) = {∅} iff this is the case for σ ∈ {co, pr}.

Finally, stable extensions are quite sensitive to odd cycles as indicated by Proposition 5.1. The following can thus only guarantee the existence of any cycle, not necessarily even.

Theorem 5.11. Let F be an AF with |stb(Fx)| ̸= |stb(F)|. Then there is some path from x to a cycle in F .

However, the result regarding degenerated AFs transfers to stb. Note that we move from ad(F) = {∅} to stb(F) = ∅.

Theorem5.12. If stb(F) = ∅ as well as stb(Fx) ̸= {∅}, then there is some path from x to an odd cycle in F .

6 Summary and RelatedWork

In this paper, we systematically analyzed the impact of adding or removing attackers or supporters to the acceptance status of certain arguments in a given AF. In particular the part about adding arguments is closely related to [Cayrol et al., 2010]. However, our investigation covers significantly more semantics as only grounded and preferred extensions are formally studied in [Cayrol et al., 2010, Section 4]. The presented results concerning removal of arguments are similar to those shown in [Amgoud and Vesic, 2020] (see also [Bisquert et al., 2011; Baumann and Ulbricht, 2019]). Our investigation is less general in the sense that fewer cases are considered (only credulous acceptance vs. no credulous acceptance), but more general in the sense that pure attackers are considered in contrast to immediate attackers only. It is hence an interesting future direction to study more cases of acceptance and rejection as done in [Amgoud and Vesic, 2020]. Some of our results from Section 3 are comparable to [Alfano et al., 2017]. It presents a similar investigation in the realm of labeling-based semantics. It will be future work to compare these results in a comprehensive fashion. One of the central insights Sections 3 and 4 provide is the confirmation of the intuition that admissibility-based semantics tend to be sensible to the length of paths. In particular, it is essential whether it is even or odd. The same does not hold for naivity-based semantics confirmed by several formal results and provided counterexamples. Recently, so-called weak admissibility [Baumann et al., 2020b] has been introduced. Weak admissibility establishes a third line of semantics beside admissibility-based and naivity-based ones. It would thus be exciting to see how the results from this paper transfer to these newly introduced semantics.

Acknowledgements

This work was supported by the German Research Foundation (DFG, BA 6170/2-1) and the German Federal Ministry of Education and Research (BMBF, 01/S18026A-F) by funding the competence center for Big Data and AI "ScaDS.AI" Dresden/Leipzig.