Facets in Argumentation: A Formal Approach to Argument Significance

1 Introduction

Abstract argumentation [Dung, 1995; Bench-Capon and Dunne, 2007] is a formalism for modeling and evaluating arguments and its reasoning problems has many applications in artificial intelligence (AI) [Amgoud and Prade, 2009; Rago et al., 2018]. The semantics is based on sets of arguments that satisfy certain conditions regarding the relationship among them, such as being stable or admissible [Dung, 1995]. Such sets of arguments are then called extensions of a framework and various practical solvers for decision and reasoning tasks [Egly et al., 2008; Niskanen and J¨arvisalo, 2020; Thimm et al., 2021; Alviano, 2021] compete biannually in the ICCMA competition [Thimm et al., 2024].

Qualitative reasoning problems such as finding an extension or deciding credulous or skeptical acceptance are reasonably fast to compute [Dvoˇr´ak, 2012] but have limitations. Namely, these two reasoning modes represent extremes on the reasoning spectrum, as they provide no insight into preferences among arguments for further analysis. As a result, enumeration, counting, and fine-grained quantitative reasoning modes have been studied and computationally classified [Fichte et al., 2023a; Fichte et al., 2024] enabling probabilistic reasoning over arguments. While enumeration is well suited when the total number of extensions is small, some argumentation semantics easily result in a vast number of extensions. However, users might still want to investigate the space of possible extensions in more detail. Possible examples are restricting or diversifying extensions, identifying resilient arguments or sanity checks, evaluating outcomes in argumentation frameworks generated by LLMs, or gaining insights into specific frameworks through explanations.

In all such scenarios evaluating the significance for individual arguments in a framework is central. In existing proposals, computing the significance for arguments relied on quantitative measures over extensions containing certain arguments or supporting particular claims. These notions rely on counting all extensions containing a particular argument (or claim), which is computationally expensive [Fichte et al., 2024]. Example 1 illustrates difficulties when comparing significance of certain arguments in the overall world of extensions.

Example 1. Consider the argumentation framework F, depicted in Figure 1, illustrating the choice between a sweet or savory breakfast, that is between maple syrup and burrito. Intuitively, if one prefers a savory flavor, they would not choose maple syrup; likewise, sweet attacks burrito. One does not go to taco bell expecting maple syrup, nor are small portions typical at taco bell. While it is possible to make burritos at home, doing so requires buying expensive ingredients. Making a small portion or going to taco bell avoids this.

The stable extensions of F are: {w,m, p}, {s, b, p} and In this paper, we propose a combination of credulously and skeptically accepted arguments, which ask whether a given argument belongs to some extension (credulous) but not all extensions (skeptical). We call arguments that are credulously but not skeptically accepted facets. Facets quantify the uncertainty of arguments in extensions, providing a measure of their indeterminacy within the framework. They can be utilized to evaluate the significance of specific arguments. Example 2 provides a brief intuition.

{s, b, t}. Now it is not immediate to compare the significance of accepting/rejecting certain arguments to each other.

Example 2. We return to the argumentation framework F from Example 1. Six of the seven arguments are facets under stable semantics, with only e being a non-facet, indicating a substantial degree of uncertainty.

Assume we aim to compare the relative significance of an argument. Consider the extensions of F rejecting (not containing) the argument "sweet". There are two such stable extensions {s, b, p} and {s, b, t}. Therefore, rejecting the argument w leaves us with two facets p and t. In contrast, consider the extensions accepting (containing) the argument "sweet". This results in one stable extension {w, m, p} and hence no facets. Accepting the argument w eliminates any uncertainty, whereas rejecting w does not. Consequently, we consider accepting "sweet" to be more significant than rejecting "sweet".

While the computational complexity of credulous and skeptical reasoning is well studied [Dvoˇr´ak, 2012], we ask for the concrete complexity of facets and whether counting facets provides a theoretical benefit over projected counting and projected enumerating extensions.

Contributions. In more details, we establish the following.

1. We introduce facets to abstract argumentation as a reasoning tool for significance and filtering extensions in a directed way. By this, we fill a gap in the literature between quantitative and qualitative reasoning.
2. We present a comprehensive complexity analysis for various qualitative and quantitative problems involving facets. Table 1 provides an overview on our results.
3. Finally, we present experiments that demonstrate the feasibility of our framework. We evaluate our implementation on instances of the ICCMA competition.

RelatedWork. The computational complexity in abstract argumentation is well understood for decision problems [Dunne and Bench-Capon, 2002; Dvoˇr´ak and Woltran, 2010; Dvoˇr´ak, 2012], parameterized complexity involving treewidth [Fichte et al., 2021a], for (projected) counting [Fichte et al., 2024] as well as for fine-grained reasoning based on counting [Fichte et al., 2023a]. The decision complexity ranges from P to ΣP 2 for credulous reasoning, and from P to ΠP2 for skeptical reasoning. The complexity of counting extensions ranges between #P and # · coNP depending on the semantics. In theory, we know that PH ⊆ P#·P [Toda, 1991] where ⋃k∈N ∆Pk = PH and NP ⊆ ∆P2 = P NP [Stockmeyer, 1976]. This renders counting extensions theoretically significantly harder. Approximate counting is in fact easier, i.e., approx-#·P ⊆ BPP NP ⊆ ΣP3 [Lautemann, 1983;

Table 1: Overview of our complexity results for the semantics σ1 ∈ {conf, naiv}, σ2 ∈ {adm, stab, comp}, and σ3 ∈ {pref, semiSt, stag}. All results depict completeness except for P-cases or when stated o/w. ISFACETσ asks whether a given argument is a facet; FACETS·k σ asks whether there are at least (≥ k), at most (≤ k), or exactly (= k) facets. Sσ[F, ℓ] asks what the significance of approving (ℓ = a) or disapproving (ℓ = ¯a) of a σ-facet a in AF F is. Superscripts behind the complexity classes refer to Remark (R) and Theorem (T), with the proof. "∈ ∆Pi " slightly abuses notation meaning that it can be computed by a deterministic polynomial-time Turing machine with access to a ΣPi-1 oracle.

Sipser, 1983; Stockmeyer, 1983], but turns out to be still harder than counting facets. Facets were initially proposed for answer-set programming (ASP) by Alrabbaa et al. [2018] as a tool to navigate large solution spaces. Their computational complexity has been systematically classified [Rusovac et al., 2024]. ASP is a popular problem solving paradigm to model and solve hard combinatorial problems in form of a logic program that expresses constraints [Gebser et al., 2012]. Plausibility reasoning has been developed for ASP based on full counting [Fichte et al., 2022a]. Dachselt et al. [2022] developed a tool to navigate argumentation frameworks using ASP-facets. Note that ASP-navigation is based on forbidding or enforcing atoms in programs via integrity constraints. In contrast, argumentation facets enable approving or disapproving arguments, while not necessarily removing the extensions entirely leading to a natural notion of significance of an argument (see Section 4). Finally, our complexity analysis (Table 1) indicates a computational gain for reasoning with facets compared to separately asking credulous/skeptical reasoning in each case (see e.g., [Dvor´ak and Dunne, 2017]). Facets have recently also been applied to planning [Speck et al., 2025].

Proofs of statements marked with (⋆) can be found in [Fichte et al., 2025].

2 Preliminaries

We assume familiarity with computational complexity [Pippenger, 1997], graph theory [Bondy and Murty, 2008], and Boolean logic [Biere et al., 2021].

Complexity Classes. We use standard notation for basic complexity classes and for example write P (NP) for the class of decision problems solvable in (non-deterministic) polynomial time. Additionally, we let coNP be the class of decision problems whose complement is in NP, and let DP be the class of decision problems representable as the intersection of a problem in NP and a problem in coNP. On top, we use more classes from the polynomial hierarchy [Stockmeyer and Meyer, 1973; Stockmeyer, 1976; Wrathall, 1976], ∆P0 := ΠP0 := ΣP0 := P and ∆Pi := PΣPi-1 ,

ΣPi := NPΣPi-1 , and ΠPi := coNPΣPi-1 for i > 0 where C D is the class C of decision problems augmented by an oracle for some complete problem in class D. Recall that PH := ⋃i∈N ∆Pi [Stockmeyer, 1976]. The canonical NP-complete problem is the Boolean satisfiability problem for formulas in conjunctive normal form (CNF), i.e., given φ := ∧mi=1 Ci where each Ci is a clause, decide whether φ admits at least one satisfying assignment. For coNP the corresponding problem is simply to check unsatisfiability, and for DP to check whether φ is satisfiable and ψ unsatisfiable for a given pair of formulas (φ, ψ) (the SAT-UNSAT problem). The complexity class DPk is defined as DPk := {L1 ∩L2 | L1 ∈ ΣPk ,L2 ∈ ΠPk }, DP=DP1 [Lohrey and Rosowski, 2023]. For ΠP2 we may e.g. consider the evaluation problem for a quantified Boolean formula of the form ∀X∃Y.φ where X and Y are two disjoint sets of variables and φ a formula in CNF over X and Y . For ΣP 2 the problem is instead to check that ∀X∃Y.φ is false.

Abstract Argumentation. We use Dung's argumentation framework (1995) and consider only non-empty and finite sets of arguments A. An (argumentation) framework (AF) is a directed graph F = (A,R), where A is a set of arguments and R ⊆ A×A, consisting of pairs of arguments representing direct attacks between them. An argument a ∈ E, is called defended by E in F if for every (a′ , a) ∈ R, there exists a′′ ∈ E such that (a′′ , a′ ) ∈ R. The family defF (E) is defined by defF (E) := { a | a ∈ A, a is defended by E in F }. In abstract argumentation, one strives for computing so-called extensions, which are subsets E ⊆ A of the arguments that have certain properties. The set E of arguments is called conflict-free in E if (E × E) ∩ R = ∅; E is admissible in F if (1) E is conflict-free in F , and (2) every a ∈ E is defended by E in F. Let E+ R := E ∪ {a | (b, a) ∈ R, b ∈ E } and E be conflict-free. Then, E is (1) naive in F if no E′ ⊃ E exists that is conflict-free in F, and (2) stage in F if there is no conflict-free set E′ ⊆ A in F with E+ R ⊊ (E′ )+R . An admissible set E is (1) complete in F if defF (E) = E; (2) preferred in F, if no E′ ⊃ E exists that is admissible in F; (3) semi-stable in F if no admissible set E′ ⊆ A in F with E+ R ⊊ (E′ )+R exists; and (4) stable in F if every a ∈ A \ E is attacked by some a′ ∈ E. For a semantics σ ∈ {conf, naiv, adm, comp, stab, pref, semiSt, stag}, we write σ(F) for the set of all extensions of semantics σ in F . Let F = (A, R) be an AF. Then, the problem EXISTσ asks if σ(F) ̸= ∅. The problems cσ and sσ question for a∈A, whether a is in some E ∈ σ(F) ("credulously accepted") or every E ∈ σ(F) ("skeptically accepted"), respectively. We let Cσ (resp., Sσ) denote the set of all credulously (skeptically) accepted arguments under semantics σ.

3 Facet Reasoning

Central reasoning problems in argumentation include deciding whether an argument is credulously (or skeptically) accepted. In the following, we will see how the problem of deciding facets can be seen as a generalization of these two modes.

We begin by defining reasoning problems pertaining to facets in argumentation. Intuitively, a σ-facet is an argument which is accepted in some, but not all σ-extensions for the considered semantics σ. Formally, given a semantics σ, then an argument a is a σ-facet if a ∈ Cσ \ Sσ. Given an AF F and semantics σ, then Fσ(F) denotes the set of all σ-facets in F In this work, we consider the following reasoning problems parameterized by a semantics σ.

• The problem ISFACETσ asks, given an AF F = (A,R) and an argument a ∈ A, is a a σ-facet in F?
• The problems FACETS=k σ , FACETS≥k σ and FACETS≤k σ has an integer k as an additional input, and ask whether an input F = (A,R) has exactly, at least, or at most k σ-facets, respectively.

We continue by analyzing the complexity of these problems, beginning with ISFACETσ in Section 3.1, FACETS≥k σ and FACETS≤k σ in Section 3.2, and complete the study with FACETS=k σ in Section 3.3.

3.1 Complexity of Deciding Facets

Regarding the complexity classification, for conflict-free and naive semantics, the problem ISFACET is rather straightforward to classify. To see this, for conf, each argument not attacking itself is a facet (provided there are at least two such arguments in the AF), and for naiv, one additionally has to remove each argument not in conflict with any other argument since it can not be a facet.

For the remaining semantics, we get hardness by observing that ISFACETσ is as hard as the credulous reasoning (cσ) for each considered semantics σ.

Proof. We provide a polynomial time many-one reduction from cσ to ISFACETσ for each semantics σ as follows. Let F = (A,R) be an AF, and a ∈ A be an argument. Our reduction yields an AF F ′ where we duplicate the argument a which has all the incoming and outgoing attacks similar to a ∈ A. Precisely, F ′ = (A′ , R′ ) is as follows:

• A′ := A∪ {a′ } for a fresh a′ ̸∈ A,
• R′ := R ∪ {(a, a′ ), (a′ , a)} ∪ {(a′ , x) | (a, x) ∈ R} ∪ {(x, a′ ) | (x, a) ∈ R}.

Then, for any semantics σ, the argument a is credulously accepted under σ in F iff a is a facet under σ in F ′ . Indeed, let a be credulously accepted, then there is a σ-extension E ⊆ A such that a ∈ E. Since a defends itself against a′ in F ′ , we have that a is also credulously accepted in F ′ as the other attacks remain the same. Finally, a can not be in all σ-extensions E in F ′ , as E \ {a} ∪ {a′ } is also a σ-extension. Therefore the claim follows.

We specifically obtain the following characterization.

Theorem 5. ISFACETσ is NP-complete for σ ∈ {adm, comp, stab} and ΣP 2 -complete for σ ∈ {semiSt, stag}.

Proof. The hardness in each case follows due to Lemma 4 and the complexity for credulous reasoning under corresponding semantics.

The membership follows, since one can guess two σextensions for an input F, one containing the argument in the question, and another without it. The verification (of σ-extensions) requires (1) polynomial time for σ ∈ {adm, comp, stab}, and (2) coNP-oracle for σ ∈ {semiSt, stag}. This establishes the membership results.

The following observation is necessary to establish the hardness proof in Theorem 7. Let Φ = ∀X∃Y.φ be a QBF instance, where φ := ∧ni=1 Ci is a CNF. If φ is not satisfiable, the formula Φ can not be true. Whereas, the problem to check whether φ is satisfiable, is NP-complete. Given Φ, one can construct a new formula Φ′ = ∀X′∃Y.φ′ such that φ′ is satisfiable and Φ is true iff Φ′ is true. To this aim, we let X′ = X ∪ {z} for a fresh variable z ̸∈ X ∪ Y . Then φ′ := ∧C∈φ(¬z ∨ C). Notice that Φ[z ↦→ 0] is trivially true whereas Φ[z ↦→ 1] is true iff Φ is true. Consequently, we have the following observation.

Remark 6. Given a QBF instance Φ = ∀X∃Y.φ, where φ is a CNF. One can assume w.l.o.g. that φ is satisfiable.

Next, we establish that ISFACETpref is ΣP 2 -complete. Notice that this case is not covered by Theorem 5 as the credulous reasoning for preferred semantics (cpref ) is only NP-complete.

Proof. The membership follows since one can guess two preferred extensions for an input F, one containing the argument in the question, and another without it. The verification of pref-extensions requires an NP-oracle. This establishes the mentioned membership results.

For hardness, we utilize the following reduction proving ΠP2 -hardness of skeptical acceptance with preferred semantics [Dvor´ak and Dunne, 2017, Reduction 3.7]. Given a QBF Φ = ∀Y ∃Z.φ where φ := ∧mi=1 Ci is a CNF-formula with clauses Ci over variables X = Y ∪ Z. We construct an AF FΦ = (A, R), where A = {φ, ¯ φ} ∪ {C1, . . . ,Cm} ∪X ∪ ¯X. The relation R includes the following attacks:

Then, it holds that there is a preferred extension in FΦ not containing the argument φ iff the formula Φ is false. Furthermore, we have that φ is satisfiable. Therefore, there exists a preferred extension S containing φ. Namely, S corresponds to a satisfying assignment θ for φ as S = {φ, ℓ | ℓ ∈ X ∪ ¯X, θ(ℓ) = 1}. As a result, φ is a pref-facet iff there is a preferred extension S′ with φ ̸∈ S′ iff the formula Φ is false. This results in ΣP 2 -hardness.

3.2 Atleast/Atmost k Facets Complexity

We begin by proving that for conflict-free and naive semantics, one can count all the facets in polynomial time.

Proof. For conf, the AF F has at least k facets if F contains at least k non self-conflicting arguments (without self-attacks). For naiv, one additionally has to remove arguments (N) not in conflict with any other argument since those can not be a facet. Thus, F has at least k naiv-facets if F \ N contains at least k non self-conflicting arguments, where N includes those arguments not participating in any attack.

The following reduction is essential for proving Lemma 10 which we utilize later in achieving certain lower bounds.

Definition 9 ([Dvor´ak and Dunne, 2017]). Let φ := ∧mi=1 Ci, be a CNF-formula where each Ci is a clause. Consider the AF Fφ = (A, R) constructed as follows:

We call Fφ the argumentation framework of φ generated via the standard translation.

It is known that φ is satisfiable iff the argument φ is credulously accepted in Fφ under semantics σ ∈ {adm, comp, stab}. We next prove the following intermediate lemma. Essentially, the standard translation allows us to characterize exactly the number of facets in Fφ based on whether the formula φ is satisfiable or not.

Lemma 10 (⋆). Let φ be a CNF-formula involving m clauses and n variables. Moreover, let Fφ be the AF of φ as depicted in Definition 9 and let k = 2n +m+ 1. Then the following statements are true for every σ ∈ {adm, comp, stab}.

1. φ is satisfiable iff Fφ admits exactly k σ-facets.

2. φ is not satisfiable iff Fφ admits exactly k - 1 σ-facets.

We continue with FACETS≥k σ and prove that it is either NP-complete or ΣP 2 -complete depending on the choice of σ.

Proof. For membership, we guess k distinct arguments {a1, . . . , ak}, and simultaneously 2k σ-extensions P1, . . . , Pk,N1, . . . ,Nk such that: ai ∈ Pi and ai ̸∈ Ni. The verification that each S ∈ {Pi,Ni | i ≤ k} is a σ-extension can be done in polynomial time. Then, F has at least k σ-facets iff each argument in {ai | i ≤ k} is a σ-facet.

For hardness, we utilize Lemma 10. Indeed, φ is satisfiable iff the AF Fφ has at least k facets where k = 2n +m+ 1 for the formula φ with n variables and m clauses.

Proof. For membership, we guess k distinct arguments {a1, . . . , ak}, and simultaneously 2k σ-extensions P1, . . . , Pk,N1, . . . ,Nk such that: ai ∈ Pi and ai ̸∈ Ni. The verification that each S ∈ {Pi,Ni | i ≤ k} is a σ-extension can be done via an NP-oracle. Then, F has at least k σ-facets iff each argument in {ai | i ≤ k} is a σ-facet. This yields membership in NP NP (equivalently, ΣP 2 ).

For hardness, we reduce from ISFACETσ for σ ∈ {pref, semiSt, stag}. To this aim, let F = (A,R) be an AF and a ∈ A be an argument in the question. Assume that |A| = n. We let n - 1 additional copies of a and consider the set Ca = {a1, . . . , an} of arguments where a1 = a and ai ̸∈ A are fresh arguments for i ≥ 2. Then, we construct the AF F ′ = (A′ ,R′ ) where A′ = A ∪ Ca. The relation R′ consists of R and additionally the following attacks: {(ai, x) | (a, x) ∈ R, i ≤ n} ∪ {(x, ai) | (x, a) ∈ R, i ≤ n}. That is, F ′ simply copies the argument a together with all its incoming and outgoing attacks for each of the n - 1 fresh arguments.

We first prove that for a conflict-free (resp., admissible) set S in F, adding arguments from Ca to S does not change its conflict-freeness (admissibility) in F ′ as long as S contains a.

Claim 13. A set S ⊆ A containing a is conflict-free (resp., admissible) in F iff S ∪Ca is conflict-free (admissible) in F ′ .

Proof of Claim 13. We prove the case for conflict-freeness, the case for admissible semantics follows analogously. If S is not conflict-free in F then S is also not conflict-free in F ′ since R ⊆ R′ .

Conversely, suppose S is conflict-free in F. Suppose to the contrary, there exists x, y ∈ S ∪ Ca such that (x, y) ∈ R′ . Recall that Ca is conflict-free in F ′ by definition and S is conflict-free in F ′ \ Ca. Then, it must be the case that x ∈ S and y ∈ Ca (or vise versa). But this leads to a contradiction to the conflict-freeness of S since a ∈ S and (x, ai) ∈ R′ iff (x, a) ∈ R. Analogous case holds if x ∈ Ca and y ∈ S. Thus S ∪Ca is conflict-free in F ′ .

Claim 14. The argument a is a σ-facet in F iff each argument ai ∈ Ca is a σ-facet in F ′ for each σ ∈ {pref, semiSt, stag}.

Proof of Claim 14. Claim Proof. Suppose a is a σ-facet in F . Then, there are σ-extensions S1, S2 in F such that a ∈ S1 and a ̸∈ S2. Then, we prove that each argument in Ca belongs to some, but not all σ-extensions of F ′ . Notice first that S1 is not a σ-extension in F ′ for any σ ∈ {pref, semiSt, stag}. This holds due to the arguments in Ca. Indeed, if S1 is a σextension in F , then S1 ∪ {x | x ∈ Ca} is a counter-example to S1 being σ-set in F ′ due to Claim 13.

SomeE: S1 ∪ Ca is a σ-extension containing each ai ∈ Ca (again, due to Claim 13).

NotAllE: We prove that S2 is a σ-extension in F ′ and ai ̸∈ S2 for each ai ∈ Ca. We prove the claim for preferred semantics, other cases can be proven analogously. Since S2 is a subset maximal admissible set in F and a ̸∈ S2, either S2 ∪ {a} is not conflict-free, or not admissible in F. Consequently, either S2 ∪ {ai} is not conflict-free, or not admissible (by Claim 13). Since A′ \ A = Ca, this proves that S2 is a preferred set in F ′ . Similar arguments (with Claim 13) yield results for the remaining two semantics. As a result, each ai ∈ Ca is a σ-facet since ai ̸∈ S2 for each ai ∈ Ca.

Conversely, suppose a is not a σ-facet in F. If a is not in contained in any σ-extension of F , then no argument from Ca can be in any σ-extension of F ′ (using the same argument as in SomeE). Hence, no argument ai ∈ Ca is a σ-facet in F ′ . Similarly, if a belongs to every σ-extension of F , once again we have that every ai ∈ Ca is contained in every σ-extension in F ′ (due to NotAllE). This results once again in no argument ai ∈ Ca being a σ-facet in F ′ .

We next observe that the argument a is a σ-facet in F iff the AF F ′ admits at least n σ-facets for each σ ∈

{pref, semiSt, stag}. Indeed, a is a σ-facet in F iff each ai ∈ Ca is also a facet in F ′ due to Claim 14. Thus resulting in at least n facets in F ′ . In contrast, if a is not a facet in F then no argument in ai ∈ Ca is a facet. Hence F ′ has at most n - 1 facets.

It is worth remarking that the reduction from ISFACETσ to FACETS≥k σ presented in the proof of Theorem 12 does not work for admissible semantics. This holds since the converse direction of Claim 14 'if a is not a facet in F then no argument ai ∈ Ca is a facet in F ′ ' is no longer true. Suppose a is not a facet. Assume further that a belongs to all admissible sets and there is at least one such set. Now, take any admissible set S in F . Clearly, a ∈ S, however, S \ {a}∪{ai} is admissible in F ′ and does not contain a. This results in every ai ∈ Ca being adm-facet in F ′ . Consequently, a is not an admissible-facet in F although each of its copy in F ′ is an admissible-facet. Moreover, F ′ also admits at least n - 1 adm-facets in this case, thus violating the proof from Theorem 12.

Theorem 15 (⋆). FACETS≤k σ is coNP-c., σ ∈ {adm, stab, comp}, whereas ΠP2 -c., σ ∈ {pref, semiSt, stag}.

3.3 Exact k Facets

Perhaps unsurprisingly, FACETS=k also turns out to be easy for conflict-free and naive semantics.

Theorem 16 (⋆). FACETS=k σ is in P for σ ∈ {conf, naiv}.

For σ ∈ {adm, stab, comp} the problem FACETS=k σ turns out to be more interesting since it is complete for the comparably esoteric class DP.

Theorem 17. FACETS=k σ is DP-c., σ ∈ {adm, stab, comp}.

Proof. The membership follows directly from FACETS≥k σ (Thm. 11) and FACETS≤k σ (Thm. 15).

For hardness, we reduce from SAT-UNSAT. To this aim, we utilize Lemma 10 for an instance (φ, ψ) of SAT-UNSAT. We assume w.l.o.g. that φ and ψ do not share variables. Then, φ is satisfiable and ψ is not satisfiable iff the AF Fφ has k1 facets and Fψ has k2 -1 facets, where Fi is the corresponding AF for i ∈ {φ, ψ} with ki arguments. However, there is a small technical issue as the AF Fφ ∪ Fψ can not distinguish the failure of the satisfaction of φ from that of ψ. Therefore, we can not simply take the union Fφ ∪ Fψ and let the number of facets be k1 + k2 - 1. Nevertheless, we duplicate the argument φ in Fφ to yield the pair φ, φ′ . Then Fφ includes the additional attacks (φ, φ′ ), (φ′ , φ) as well as (C, φ′ ) for each C ∈ φ. The resulting AF Fφ has k1 + 1 arguments and φ is satisfiable iff Fφ has k1 + 1 facets. Note that the newly added argument φ′ is a σ-facet iff φ is σ-facet for each σ ∈ {adm, comp, stab}. Then, the theorem follows since (φ, ψ) is a positive instance of SAT-UNSAT iff φ is satisfiable and ψ is not satisfiable iff Fφ ∪ Fψ has exactly (k1 + k2) σ-facets for σ ∈ {adm, comp, stab}.

We conclude our complexity analysis by stating the nontight bounds for FACETS=k σ for the remaining semantics.

Theorem 18 (⋆). FACETS=k σ is in DP2 for σ ∈ {pref, semiSt, stag}.

4 Significance

Our notion of significance adopts a decision-driven perspective. We define significance of arguments in terms of the influence of a decision to eliminate the degree of freedom (on choices of remaining arguments). While counting approaches assess the plausibility of arguments in terms of their likelihood of being accepted, we measure how much the acceptance of an argument decreases freedom (or increases the significance of the decision). Intuitively, a higher significance score indicates that a specific decision does have a huge influence on the remaining facets. Furthermore, the number of facets directly measures the amount of uncertainty in extensions. Consider an argument a (as an opinion or a view point) and denote by ¯a the complement/negation of a. E.g., an argument is approved (a) versus not approved (¯a). Then, a facet ℓ ∈ {a, ¯a} can be seen as the uncertainty regarding a, since a can either be included in, or be excluded from certain extensions. We next introduce the notion of approving and disapproving an argument. Let F = (A,R) be an AF, and σ be a semantics. Recall that σ(F) denotes the collection of σ-extensions in F. Moreover, Cσ (resp., Sσ) denotes the collection of credulously (skeptically) accepted arguments in F under semantics σ. For an argument a, we let σa (F) denote the σ-extensions in F approving the argument a. Precisely, we define σa (F) = {E ∈ σ(F) | a ∈ E}. Moreover, σ¯a (F) = {E ∈ σ(F) | a ̸∈ E} represents the σ-extensions in F disapproving a. Now, let Caσ (resp., Saσ ) be the arguments in some (all) E ∈ σa (F). Finally, F a σ (F) denotes the σ-facets by considering only extensions in σa (F) (i.e., Caσ \ Saσ ).

For an argument a ∈ A and ℓ ∈ {a, ¯a}, we denote ¯ ℓ = ¯a if ℓ = a and ¯ ℓ = a for ℓ = ¯a. We say that ℓ is approved iff ¯ ℓ is disapproved. Approving a facet ℓ ∈ {a, ¯a} reduces the uncertainty regarding the remaining arguments in A by restricting the extensions space to sets (not) containing a. Further, approving ℓ can render a facet argument b ∈ A non-facet. This holds since, either (C1) b ∈ E for each E ∈ σℓ (F) but b ̸∈ E for each E ∈ σ(F), or (C2) b ̸∈ E for any E ∈ σℓ (F) but b ∈ E for some E ∈ σ(F). Intuitively, we say that the uncertainty of such an argument b has been resolved by approving ℓ. Further, we say that approving ℓ results in the approval of b in the case of (C1), and disapproval of b if (C2) is the case.

Notice that approving (or disapproving) an argument results in fewer facets for every semantics σ. That is, the (dis)approval of any argument can not generate new facets. Intuitively, we have less uncertainty than before after we (dis)approve certain arguments. Precisely, we have the following lemma.

Lemma 19. For any argument a ∈ A and semantics σ, F a σ (F ) ⊆ Fσ(F ).

Let σ be a semantics, a ∈ A be a σ-facet and ℓ ∈ {a, ¯a}. The observation that "ℓ reduces the uncertainty among remaining arguments" leads to the notion of significance of ℓ under semantics σ. For an AF F , we define:

Intuitively, approving an argument a is less significant if many uncertain arguments (facets) remain in F a σ (F). Similarly, disapproving a (and thus approving ¯a) is less significant if many facets remain in F ¯a σ (F ).

Example 20 (Arguments Significance). Reconsider the AF F from Example 1 with stable extensions stab(F) = {{w, m, p}, {s, b, p}, {s, b, t}}. While Example 2 gave an intuition of significance, Table 2 presents precise values for each argument. As outlined, the argument w has score 1, and is thus more significant than ¯w (score 2/3). The argument e not being a stab-facet is excluded for significance reasoning.

4.1 Computing Significance for Arguments

Let F = (A,R) be an AF, σ be a semantics and a ∈ A be an argument. Observe that the computation of Sσ[F, ℓ] (Equation 1) requires counting facets in Fσ(F) and F ℓσ (F). We argue that one can count the number of σ-facets in a framework F = (A, R) without having to enumerate or count all σ-extensions explicitly. In fact, Fσ(F) can be computed by asking ISFACETσ for each argument a ∈ A, which requires |A|-many queries. Moreover, one can also count the exact facets in F ℓσ (F) without having to explicitly identify all σℓ - extensions. Observe that F ℓσ (F) corresponds to the result of remaining facets after approving ℓ.

Theorem 21. Let σ be a semantics and F = (A,R) be an AF. For every a ∈ A and ℓ ∈ {a, ¯a} the sets Fσ(F) and F ℓσ (F) can be computed by a deterministic polynomial-time Turing machine with access to

• an NP oracle for σ ∈ {adm, comp, stab}.
• a ΣP2 oracle, for σ ∈ {pref, semiSt, stag}.

Proof. Given an AF F = (A, R), semantics σ and argument a ∈ A. To compute Fσ(F), we consider the following procedure. For each b ∈ A:

1. Guess two sets E1, E2 ⊆ A,
2. Check that b ∈ E1, b ̸∈ E2,
3. Check that Ei ∈ σ(F),
4. Answer "Yes" if each check is passed in Step 2 - 3.

This procedure is repeated polynomially-many times (precisely |A|-many times). As a post-processing, count the number of arguments b ∈ A, for which Step-4 answers "Yes". The 2nd step requires non-determinstic guesses, whereas the 3rd step needs (1) P for σ ∈ {adm, comp, stab} and (2) coNP, for σ ∈ {pref, semiSt, stag}. Step-4 is again a final postprocessing. As a result, the procedure overall runs in the mentioned runtime for corresponding semantics. That is, P-time with an NP oracle for σ ∈ {adm, comp, stab} and ΣP 2 -oracle, for σ ∈ {pref, semiSt, stag}.

To compute F ℓσ (F), we additionally include the following check to the Step-2 in the above procedure.

This does not increase runtime, and completes the proof.

Observe that one can not expect to lower the runtime in Theorem 21 (e.g., to NP in the case of σ ∈ {adm, comp, stab}). Intuitively, although each step (Step 1 - 4 in the proof of Theorem 21) requires NP-time, the final post-processing needs counting the number of arguments for which each check is passed. In fact, this would contradict Theorem 17 (unless NP = DP) since one can count all facets in an AF and determine whether this number equals k.

5 Implementation and Experiments

Implementation We implemented counting of extensions and facets for various semantics into our tool called frame (Facets for Reasoning and Analyzing Meaningful Extensions). We build on the Aspartix system, an ASP-based argumentation system for Dung style abstract argumentation and extensions thereof [Egly et al., 2008]. We employ Aspartix's ASP encoding and take the ASP solver clingo version 5.7.1 [Gebser et al., 2012] to compute credulous and skeptical consequences and take set differences. We leverage ASP as the solvers have native support for enumerating consequences without exhaustive enumeration of all answersets [Alviano et al., 2023; Gebser et al., 2009].

Design and Expectations. We ran our experiments on a Ubuntu 11.4.0 Linux 5.15 computer with an eight core Intel i7-14700 CPU 1.5 GHz machine with 64GB of RAM. Each run is executed exclusively on the system. To illustrate that we can count facets on practical instances and obtain insights over counting, we take the admissible, stable semantics, and semistable semantics over instances from the 3rd International Competition on Computational Models of Argumentation (ICCMA'19) [Bistarelli et al., 2019]. This gives us 326 different argumentation frameworks of varying sizes in the range of 0 to 10.000 arguments with an average of 800.3 arguments and a median of 160.0 arguments. We take admissible, stable, and semi-stable semantics as representative from each different level of hardness (see Table 1). We take the 2019 competition as instances are of reasonable size, runtime, number for the scope of this experiment, and we can use input instances without further modification. We limit the runtime on each instance to 60 seconds for sustainability reasons, as differences become visible already with the limitation, and as a user might not want to wait long when investigating search spaces. We collect the number of extensions and facets and measure the solver runtime. We have the following expectations: (i) computing facets is faster than enumerating extensions, (ii) facets are still accessible when the number of extensions is very high and enumeration takes longer runtime, (iii) even when there are many extensions, there are reasonably small number of facets.

Observations and Summary. Table 3 presents a survey of our results. Details on the evaluation are available in the supplemental data. We see that the number of admissible extensions can be larger than 106 and clingo fails to enumerate all extensions (⋆ ) if the number of extensions is very high. For the admissible extensions, we observe that even if the number of extensions is quite high, the number of facets remains reasonably small making it interesting to diversify extensions, or investigate more details about those arguments, which still allow flexibility. The observations confirm our expectations for the admissible semantics. However, we gain only limited insights for the semantics stab and semiSt. Here the number of extensions is fairly low and the solver either manages to enumerate all extensions, or already fails to solve one.

6 Conclusion

We defined a new perspective on exploring significance of arguments in extensions of an abstract argumentation framework. We present a comprehensive complexity analysis. We establish that the complexity of deciding whether the number of facets is exactly k ranges between P and DP2, including tight lower bounds for most cases (see Table 1). While our primary focus lies on establishing a comprehensive complexity picture, our implementation allows computing the number of facets practically building on top of existing solvers.

For future work, we plan to investigate techniques whether significance originating from facets can be extended to arguments depending on each other and notions of fairness in argumentation frameworks. We also believe that the missing case for σ ∈ {pref, semiSt, stag} remains interesting to study. We expect that the problem is also hard, as the decision problems for at least and at most are ΣP 2 - and ΠP2 - complete. From a practical perspective, we believe that it would be interesting to integrate facet-based reasoning and significance computation into modern SAT-based argumentation solvers. Moreover, investigating facets for other formalisms such abductive reasoning [Mahmood et al., 2020] or default logic [Fichte et al., 2022b] seems interesting as well as closing the gap to the topic of inconsistencies [Fichte et al., 2021b; Fichte et al., 2023b].

Acknowledgments

The work has received funding from the Austrian Science Fund (FWF), grants J 4656 and P 32830, the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation), grants TRR 318/1 2021 - 438445824 and ME 4279/3-1 (511769688), the European Union's Horizon Europe research and innovation programme within project ENEXA (101070305), the Society for Research Funding in Lower Austria (GFF, Gesellschaft f¨ur Forschungsf¨orderung N ¨O), grant ExzF-0004, the Swedish research council under grant VR-2022-03214, as well as the Vienna Science and Technology Fund (WWTF), grant ICT19065, and by the Ministry of Culture and Science of North Rhine-Westphalia (MKW NRW) within project WHALE (LFN 1-04) funded under the Lamarr Fellow Network programme, and ELLIIT funded by the Swedish government.

Part of the research was carried out while Hecher was visiting the Simons Institute for the Theory of Computing at UC Berkeley.

Johannes and Yasir appreciate valuable discussions with Lydia Bl ¨umel and Matthias Thimm (Fern Universit¨at in Hagen) on an alternative proof to Theorem 21.