Quantitative Reasoning and Structural Complexity for Claim-Centric Argumentation

1 Introduction

Argumentation is a formalism for nonmonotonic reasoning [Atkinson et al., 2017; Rago et al., 2018; Baroni et al., 2018] and a crucial aspect of communication in our everyday life. The theory of argumentation deals with conflicting information by generating and comparing arguments. Moreover, different directions of argumentation have been perused with applications in artificial intelligence [Amgoud and Prade, 2009; Maher, 2016; Rago et al., 2018].

Dung's framework [Dung, 1995] models arguments as abstract entities where the internal structure of an argument is hidden. In this setting, an argumentation framework (AF) is presented by a directed graph where nodes are arguments and arcs depict the attack relationship between arguments. The semantics of AFs is described in terms of sets of arguments that can be simultaneously accepted with respect to a given framework. These sets of arguments are then called extensions of a framework. The credulous (skeptical) reasoning problems for AF ask whether an argument belongs to some (every) extension of a framework under the given semantics. Dung's framework is nowadays acknowledged as the core reasoning mechanism for argumentation, even though it hides all the details of how an argument is constructed. Moreover, AFs do not answer the consequence once a set of arguments has been accepted under a given semantics. To answer this question, it is desirable to explore the structure of an argument. An argument consists of a claim and a support for this claim, e.g., the logic-based approach [Besnard and Hunter, 2008]). In this direction, Dung's framework can be expanded by reinterpreting the set of accepted arguments in terms of their claims.

Claim-augmented argumentation (CAF) introduced by Dvor´ak and Woltran (2020) expands AFs. A CAF extends an AF by assigning a claim to each argument. The semantics for CAFs is defined in terms of the set of claims corresponding to the accepted arguments in an AF. Furthermore, for specific semantics requiring subset maximality, one can either take maximal sets of accepted arguments and then retrieve their claims or already consider maximal sets in terms of accepted claims, for other ideas, see [Dvor´ak et al., 2020]. This leads to two variants of semantics: inherited and claim-based.

The computational complexity of claim-augmented argumentation has been studied for different problems under inherited semantics [Dvor´ak and Woltran, 2020] and claim-based semantics [Dvor´ak et al., 2021]. The main complexity theoretic aspects of CAF include that the verification problem has a higher complexity in many cases than its AF-counterpart. Furthermore, Dvor´ak and Woltran (2020) explored the complexity of reasoning problems for specific sub-classes of frameworks and provided fixed-parameter tractability results. Regarding the parameter treewidth, the authors considered the underlying AF as a graph representation, with the associated claims being irrelevant. Moreover, they also explored another graph representation, namely the incidence graph but only for a subclass of the framework (known as the well-formed CAFs). In this work, we focus on admissible, stable, preferred, and complete semantics and thereby explore the complexity of reasoning problems in CAF under the parameter treewidth. We suitably model claims of an argument to appear in the representation.

A level of justification for claims. In this work, we explore another dimension for the accepted claims, namely the level of justification for a claim and a set of claims, respectively. The concept is based on the fact that contradictory arguments can still agree on their claim(s). So, a claim can be accepted irrespective of which argument for this claim is in the extension.

Example 1. Let Ai = (ϕi, c) be arguments for the claim c with different supports, support for claim c is the minimal consistent set ϕ s.t. ϕ |= c): ϕ1 := (x ∧ y) ∧ (¬x ∨ c) and ϕ2 := (¬x ∧ z) ∧ (¬z ∨ c). So, A1 and A2 are mutually inconsistent, attack each other, although both entail claim c.

Credulous reasoning talks about one extension that covers the given claims while skeptical reasoning requires that every extension covers them. These two problems can thus be seen as the diametral scenarios on the reasoning yardstick. However, the extreme case of skeptical reasoning is almost never applicable and credulous reasoning oftentimes does not give any information about preferences. Indeed, a level of justification can be obtained by utilizing quantitative measures on extensions supporting particular claims. This can then be used to implement preferences among claims. Consequently, more subtle reasoning modes are required providing further support for claim acceptance in diverse situations and real-world scenarios.

Example 2. Consider an upcoming election with two candidates A and B (see Fig. 1) where participants are seen as arguments. Arguments w, x, y (resp., z) support candidate A (B) while some arguments also attack those favoring the opponent. For instance, the support of x could be in favor of COVID preventions, while the support of z might entail that the pandemic is over. Furthermore, the support of w could assert that the people should be self-responsible. Arguments w, x are conflicting but both support candidate A (election programs are not always consistent). The admissible extensions of this framework include ∅, {w}, {x}, {z}, {w, y}, {w, z} and the corresponding sets of claims include ∅, {A}, {A}, {B}, {A}, {A,B}. Each candidate is credulously accepted and no candidate is skeptically accepted. Nevertheless, A has higher preference than B as witnessed by the number of extensions with claim A.

Clearly, a more fine-grained, justification-based reasoning is particularly relevant for CAFs. In the end, reasoning should not solely depend on the arguments or motivations favoring claims, but on the actual outcomes (or claims) themselves.

In general, reasoning problems in argumentation frameworks are often of high worst-case complexity [Dunne and Bench-Capon, 2002; Dvoˇr´ak and Woltran, 2010; Dvoˇr´ak, 2012]. To circumvent resulting intractabilities, the toolkit of parameterized complexity has been successfully utilized [Dvoˇr´ak et al., 2012; Fichte et al., 2019; Lampis et al., 2018]. One of the most generally applicable and well-studied structural invariances is the parameter treewidth [Robertson and Seymour, 1986]. Indeed, particularly for argumentation, there has been a long line of theoretical research focussing on how to exploit treewidth [Brochenin et al., 2018; Charwat et al., 2015; Alviano, 2018; Atserias et al., 2011;

#cnt

Figure 2: Probabilities prob of a framework (see Def. 8) are more finegrained than the classical reasoning modes credulous and skeptical reasoning, which we can easily simulate by counting the number of extensions (#cnt).

prob ≥ 1

prob ∈ [0, 1]

Bacchus et al., 2003]. There are also several works on practical evaluations, e.g., [Dvor´ak et al., 2022; Eiter et al., 2021]. Especially for counting, treewidth established itself as the state-of-the-art [Lagniez et al., 2021; Fichte et al., 2021a].

It is well known that there exists a connection between treewidth and quantified Boolean formulas (QBF) [Pan and Vardi, 2006; Fichte et al., 2020] which is a generic framework in the area of computational complexity [Wrathall, 1976]. In the last decade, research on QBF has provided efficient problem solving techniques resulting in powerful QBF-solvers [Shukla et al., 2019]. The demand of QBFconstructions vastly increases [Shaik and van de Pol, 2022; Jung et al., 2022; Hossain and Laroussinie, 2021] that is why we utilize this target formalism for designing first encodings for CAFs. Accordingly, this allows us to establish new complexity results for CAFs parameterized by treewidth, which we render tight under reasonable complexity assumptions.

Contributions. In more details, we establish the following.

1. We introduce quantitative reasoning that allows finegrained modes between credulous and skeptical reasoning (see Fig. 2). We show why this is particularly useful for CAFs. Our quantitative reasoning approach is also motivated by its "qualitative"-counterpart, namely the statement justifications, which has also been explored (see the related work section of our paper).
2. We present a novel graph structure for CAF that allows a suitable depiction of claims. Structuring these constructions, yields a treewidth-aware reduction from reasoning problems on CAFs to validity of QBFs. Table 1 gives an overview of the results.
3. Utilizing these treewidth-aware encodings, we establish tight runtime bounds for treewidth that cannot be improved under reasonable complexity assumptions.

Related Work. Probabilistic argumentation [Hunter and Thimm, 2017; Fazzinga et al., 2015; Alfano et al., 2020] focuses on weighting arguments with probabilities. This is orthogonal to our setting. Our focus is on the (conditional) probability of an event, similar to the one in Bayesian world. This term is sometimes also called plausibility. Fichte et al. [2022a] studied this topic for answer set programming. One could easily combine these two settings and get probabilistic quantitative reasoning. The ranking-based semantics [Bonzon et al., 2018] focuses on what are called preferences. The known research on the justification status of arguments [Wu and Caminada, 2010; Baroni et al., 2016; Baroni and Riveret, 2019] explores the different levels of acceptance or rejection of arguments. The goal is achieved via the labelling semantics for argumentation frameworks. Furthermore, Baroni et al. (2016) also emphasized statement justification as a topic of independent interest. Nevertheless, their approach explores the status of an argument (or statement) in different extensions, that is, what are the different acceptance labels of an argument. Moreover, the authors explicitly rule out the role played by the cardinality of a label-set for arguments. In this work, our interest is mainly (as the name suggests) the quantitative aspect of the claim justification. The subtle difference between the justification reasoning for arguments versus for claims was noticed by Prakken and Vreeswijk (2002, Example 25) and also discussed recently by Sanjay Modgil (2018, Def. 2.18). Decomposition guided reductions have been studied for abstract argumentation [Fichte et al., 2021b].

2 Preliminaries

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

Quantified Boolean Formulas. Let ℓ be a positive integer, which we call (quantifier) rank later, and ⊤ and ⊥ be the constant always evaluating to 1 and 0, respectively. For a Boolean formula F, we abbreviate by var(F) the variables occurring in F and write F(X1, . . . ,Xl) to indicate that X1, . . . , Xl ⊆ var(F). A quantified Boolean formula ϕ (in prenex normal form), qBf for short, is an expression of the form ϕ = Q1X1.Q2X2. · · · QℓXℓ.F(X1, . . . , Xℓ), where for 1 ≤ i ≤ ℓ, we have Qi ∈ {∀, ∃} and Qi ̸= Qi+1, the Xi are disjoint, non-empty sets of Boolean variables, and F is a Boolean formula. We let matrix(ϕ) := F and we say that ϕ is closed if var(matrix(F)) = ⋃i∈ℓ Xi. We evaluate ϕ by ∃x.ϕ ≡ ϕ[x ↦→ 1] ∨ ϕ[x ↦→ 0] and ∀x.ϕ ≡ ϕ[x ↦→ 1]∧ϕ[x ↦→ 0] for a variable x. W.l.o.g. we assume that matrix(ϕ) = ψCNF ∧ψDNF, where ψCNF is in CNF (disjunction of conjunctions of literals) and ψDNF is in DNF (conjunction of disjunctions of literals). Then, depending on Qℓ, either ψCNF or ψCNF is optional, more precisely, ψCNF might be ⊤, if Qℓ = ∀, and ψDNF is allowed to be ⊤, otherwise. The problem ℓ-QBF asks, given a closed qBf ϕ = ∃X1.ϕ′ of rank ℓ, whether ϕ ≡ 1 holds. The problem #ℓ-QBF asks, given a closed qBf ∃X1.ϕ of rank ℓ, to count assignments α to X1 such that ϕ[α] ≡ 1. For brevity, we sometimes omit ℓ.

Tree Decompositions and Treewidth. For a rooted (directed) tree T = (N, A) with root root(T) and a node t ∈ N, we let children(t) be the set of all nodes t′ , which have an edge (t, t′ ) ∈ A. Let G = (V, E) be a graph. A tree decomposition (TD) of a graph G is a pair T = (T, χ), where T is a rooted tree, and χ is a mapping that assigns to each node t of T a set χ(t) ⊆ V , called a bag, such that:

Then, define width(T ) :=maxt of T |χ(t)|-1. The treewidth tw(G) of G is the minimum width(T ) over all tree decompositions T of G. Observe that for every vertex v ∈ V , there is a unique node t∗ with v ∈ χ(t∗ ) such that either t∗ = root(T) or there is a node t of T with children(t) = {t∗ } and v /∈ χ(t). We refer to the node t∗ by last(v). For arbitrary but fixed w ≥ 1, it is feasible in linear time to decide if a graph has treewidth at most w and, if so, to compute a TD of width w [Bodlaender, 1996]. In this work, we assume only TDs (T, χ), where for every node t of T , we have that |children(t)| ≤ 2. Such a TD can be obtained from any TD in linear time without increasing the width [Bodlaender and Koster, 2008].

Treewidth and qBfs. For a given qBf ϕ with matrix(ϕ) = ψCNF ∧ ψDNF, we define the primal graph Gϕ := Gmatrix(ϕ), whose vertices are var(matrix(ϕ)). Two vertices of Gϕ are adjoined by an edge, whenever the corresponding variables share a clause or term of ψCNF or ψDNF, respectively.

Let tower(i, p) be tower(i-1, 2p ) if i > 0 and p otherwise. Further, we assume that poly(n) is any polynomial for given positive integer n. The following result is known for QBF.

Proposition 3 (Chen, 2004). For any arbitrary qBf ϕ of quantifier rank ℓ > 0, the problem ℓ-QBF can be solved in time tower(ℓ,O(tw(Gφ))) · poly(|var(ϕ)|).

Assuming the exponential time hypothesis (ETH) [Impagliazzo et al., 2001], one cannot significantly improve this runtime. The ETH implies that SAT = 1-QBF can not be decided in time better than 2o(|var(φ)|) for a formula φ.

Proposition 4 (Fichte et al., 2020). Under ETH, for any arbitrary qBf φ of quantifier rank ℓ > 0, problem ℓ-QBF cannot be solved in time tower(ℓ, o(tw(Gφ))) · poly(|var(φ)|).

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, a pair of arguments representing direct attacks of arguments. 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 admissible. Then, 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) stable in F if every a ∈ A \ E is attacked by some a′ ∈ E. For a semantics σ ∈ {cf, adm, comp, pref, stab}, we write σ(F) for the set of all extensions of semantics σ in F.

Let F = (A, R) be an AF. Then, problem σ 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.

TDs for AFs. Consider for AF F = (A,R) the primal graph GF , where we simply drop the direction of every edge, i.e., GF := (A,R′ ) where R′ := { {u, v} | (u, v) ∈ R }. For any TD T = (T, χ) of GF and any node t of T , we let Rt := R∩ { (a, b) | a, b ∈ χ(t) } be the bag attacks of t.

Let F = (A, R) be an AF and T = (T, χ) be a TD of GF . Stable Extensions. Stable extensions can be computed via DG reduction to SAT. For each argument a ∈ A, a variable ea determines whether a is in the extension or not. This gives rise to extension variables E := { ea | ea ∈ A }. Moreover, the formula confR(E) := ∧(a,b)∈R(¬ea ∨¬eb), ensures conflict-freeness and already preserves the treewidth. Towards a DG reduction, let dta be auxiliary variables for every node t of T and argument a ∈ A to indicate whether a is attacked ("defeated") by b ∈ χ(t) of the extension. This leads to defeated variables Vd := {dta | a ∈ A, t in T} and DG reduction Rstab(F, T ) := ∃E, Vd.confR(E) ∧ φstab(E, Vd) where CNF φstab(E, Vd) comprises Formulas (1) and (2):

Decomposition-Guided Reductions for AFs. Inspired by related work [Fichte et al., 2021b], a decomposition-guided (DG) reduction R is a function that takes both a problem instance I and a TD T = (T, χ) of GI, and returns a qBf φ. The way a DG reduction is constructed, it has to yield a TD T ′ = (T, χ′ ) of Gφ. So, the idea of such a DG reduction is to construct φ from a TD node's point of view. Thereby, for each node t of T, the constructed bag χ′ (t) functionally depends on the original bag χ(t), but also on the constructed bags χ′ (t1), . . . , χ′ (to) of its child nodes {t1, . . . , to} = children(t). This gives rise to a function f that takes a TD node t, its bag χ(t) and a set χ′ (children(t)) = { χ′ (ti) | ti ∈ children(t) } of constructed bags for the child nodes of t. Then, since the width(T ) is bounded by O(maxt of T (|χ(t)|)), also the treewidth of the resulting qBf is at most O(maxt of T {|f(t, χ(t), χ′ (children(t))|}).

Admissible Extensions. Towards a DG reduction, auxiliary variables of the form na for every argument a ∈ A indicate whether a never attacks an argument in the extension. These no-attacking variables N := {na | a ∈ A} are used to define Radm(F, T ) := ∃E, Vd,N.confR(E)∧φadm(E,D,N), where φadm(E, Vd, N) consists of Formulas (1), and (3)-(6):

¬na ∨ ¬dlast(a)

for every a ∈ A (6)

As above, this reduction linearly preserves the (tree)width. Reductions for further semantics can be constructed similarly. For σ ∈ {stab, adm, comp, pref}, its DG reduction is given by Rσ .

Claim-Centric Argumentation. We formalize CAFs next.

Definition 5. A claim-augmented framework (CAF) CF := (A, R, cl) consists of an AF (A, R) and a function cl : A → C assigning claims to each argument in A, where C is a set of claims. Extend cl to sets by cl(E) := { cl(a) | a∈E }.

Semantics for CAF. Following [Dvor´ak andWoltran, 2020], we define the inherited (i-semantics) for CAFs.

Definition 6. Let CF = (A,R, cl) be a CAF where F = (A, R) denotes the underlying AF, and σ be an AF-semantics. Then we define i-σ semantics as σc(CF) := {cl(E) | E ∈ σ(F)}. Moreover, for a set S of claims, we call E ∈ σ(F) with cl(E) := S as a σc-realization of S in CF.

In this work, we focus on reasoning problems in claimcentric argumentation. Given a CAF CF = (A,R, cl), let the primal graph GCF := G(A,R). Further, the problem i-σ asks whether σc(CF) ̸= ∅. The problem i-cσ (resp., i-sσ) for inherited semantics asks whether a given claim c is in some (all) claim sets S ∈ σc(CF). For a given set S ⊆ C of claims, the verification problem i-vσ asks if S ∈ σc(CF).

3 Quantitative Claim-Based Reasoning

The two dominant reasoning modes in abstract argumentation are called credulous and skeptical reasoning, as defined in the previous section. While these classical forms of reasoning are well-established and useful in many cases, oftentimes one wants to have a more precise mode of reasoning that is located between both extreme cases. Indeed, credulous reasoning is rather easy to fulfill, as having already one extension over some entity of choice (argument or claim) satisfies its conditions; so, many entities will be credulously accepted. On the other hand, skeptical reasoning is overly skeptical, since having an entity in every extension is very hard to satisfy.

In order to mitigate these issues, we propose an intermediate reasoning mode that is more fine-grained and naturally adheres to quantitative (probabilistic) aspects of argumentation. Accordingly, instead of asking whether an entity of interest is in some or all extensions, a natural generalization is to ask whether the entity is in the vast majority (e.g., 70% or 80%, of the extensions). This way, one can still draw reasonable consequences from quantitative reasoning modes, without satisfying skeptical reasoning. Clearly, depending on the use case, quantitative reasoning could also be applied to query arguments in a minority of (e.g., 10%) the extensions.

Quantitative reasoning is formalized below, thereby conceptually relying on extension counting [Fichte et al., 2019] as its core. Observe that counting does not imply extension enumeration. Indeed, though state-of-the-art systems are capable of counting extensions one can probably not enumerate efficiently (e.g., exceeding the number of atoms in the universe) [Lagniez et al., 2021; Fichte et al., 2021a].

Definition 7 (Claim-Based Counting). Let CF = (A,R, cl) be a CAF, C be the set of claims and σ be a semantics. Moreover, let D be a claim assertion, i.e., a set of literals over C. Problem #cntσ(CF,D) counts extensions E fulfilling D, defined as D ∩ C ⊆ cl(E) ("cover claims') and { c | ¬c ∈ D } ∩ cl(E) = ∅ ("prevent disregarded claims").

For a set D of claim assertions, we denote by cl(D) the set of claims appearing in D. That is, cl(D) = {c | c ∈ C ∩ D} ∪ {c | c ∈ C, ¬c ∈ D}. Notice that the special case of D=∅, i.e., the problem #cntσ(CF, ∅) amounts to plain extension counting. This problem can be used to reason about the probability of a set of claims being covered by an arbitrary extension, yielding quantitative reasoning under claims.

Definition 8 (Probability of Claim Fulfillment). Let CF = (A, R, cl) be a CAF, C be the set of claims, σ be a semantics, and D be a claim assertion over C. The probability of D being fulfilled, is defined as probσ(CF,D) := #cntσ (CF,D) #cntσ (CF,∅) .

These counting-based definitions now allow us to reason about the degree of fulfilling claim assertions, which results in quantitative reasoning. This degree of fulfillment can then be used for accepting claim assertions depending on whether its probability exceeds a certain threshold.

Example 9. Reconsider the CAF in Example 2. The admissible extensions of this framework include ∅, {w}, {x}, {z}, {w, y}, {w, z} and the corresponding admissible sets of claims are ∅, {A}, {A}, {B}, {A}, {A, B}. Then A has higher preference than B: precisely, probadm(CF, {A}) = 46 , while probadm(CF, {B}) = 26 . Also for preferred semantics this preference holds, since probpref (CF, {A}) = 1 and probpref (CF, {B}) = 13 .

3.1 DGReductions for Quantitative Reasoning

Now, we proceed towards DG reductions for computing the probability of claim fulfillment for a fixed-size set D of claim assertions. We do this by presenting modifications to the reductions from Section 2 since CAFs generalize AFs. Note that it is known that credulous (i-cσ) and skeptical reasoning (i-sσ) are both FPT [Dvor´ak and Woltran, 2020] when parameterized by treewidth of the primal graph of AFs. After proving that both of these problems are subcases of quantitative reasoning, we improve known FPT-results by providing DG reductions that allow us to prove tight runtime bounds.

To this end, let CF = (A,R, cl) be a CAF, T = (T, χ) be a TD of GCF , and let E := {ea | a ∈ A} denote the extension variables as before. Then for each claim c ∈ D ∩ C the formula cov(c,E) := ∨a∈A,cl(a)=c ea guarantees that at least one argument a with cl(a) = c is in the extension. Similarly, for each d ∈ C such that ¬d ∈ D the formula ¬cov(d,E) guarantees that no argument a with cl(a) = d is in the extension. Clearly, cov(c,E) does not preserve the treewidth since different arguments can have claim c. To preserve the treewidth linearly, we split cov(c, E) considering the TD T . We use variables of the form xtc for each claim c over D and every node t of T to indicate whether the claim c is covered by some argument a in the extension. This leads to claim variables XD := {xtc | t in T, c ∈ cl(D)}. Finally, let φcl(E, XD) be the CNF consisting of Formulas (7)-(9):

Intuitively, Formulas (7) guide the information regarding a claim c along the TD and the Formula (8) (resp., (9)) ensures that some (no) argument with the claim c is in the extension.

Claim-based counting for a fixed set D and semantics σ ∈ {stab, adm, comp, pref} can be solved by appending formula φcl(E, XD) to each Rσ, resulting in DG reduction Rcb σ . Then, the probability probσ(CF,D) of fulfilling D can be obtained by computing #cntσ(CF,D) and #cntσ(CF, ∅). Correctness of the resulting DG reductions is shown below.

Theorem 10 (Correctness). Let CF = (A,R, cl) be a CAF, D be a set of claim assertions, and T = (T, χ) be a TD of GCF . Then, DG reduction Rcb σ (CF, T ) for σ ∈ {stab, adm, comp, pref} is correct, i.e., #cntσ(CF,D) on CF coincides with #SAT (#2-QBF) on ψσ = Rcb σ (CF, T ).

The presented DG reductions yield the following results.

Theorem 11 (TW-Awareness). Let CF = (A,R, cl) be a CAF, D be a set of claim assertions of constant size r, and T = (T, χ) be a TD of GCF of width k. Then, the DG reduction Rcb σ (CF, T ) for σ ∈ {stab, adm, comp, pref} constructs a qBf ψσ s.t. tw(Gmatrix(ψσ)) ∈ O(k).

The following theorems provide the running time bounds for solving the reasoning problems.

Theorem 12 (Runtime UB). Let CF = (A,R, cl) be a CAF and D be a set of claim assertions of constant size r. Then, for σ ∈ {stab, adm, comp} (resp., pref), the problem #cntσ(CF,D) (#cntpref(CF,D)) can be solved in time 2O(k) · poly(|A|) (tower(2,O(k)) · poly(|A|)).

Interestingly, it is not expected that one can significantly improve (decrease) the treewidth in these DG reductions. The result follows because of the following theorem together with the fact that CAF expands AF.

Theorem 13 (Runtime LB). Let CF = (A,R, cl) be a CAF and D be a set of claim assertions. Then, for σ ∈ {stab, adm, comp} (resp., pref) the problem #cntσ(CF, D) (#cntpref (CF,D)) can not be solved in time 2o(k) · poly(|A|) (tower(2, o(k)) · poly(|A|)), where k = tw(GCF)).

Theorem 14 (TW-LB). Let CF = (A,R, cl) be a CAF, D be a set of claim assertions, and T be a TD of GCF of width k. Under ETH, DG reduction Rcb σ (CF, T ) for σ ∈ {stab, adm, comp, pref} cannot be significantly improved, i.e., there is no reduction R′ from #cntσ(CF,D) (resp., #cntpref(CF,D)) to #SAT (#2-QBF) yielding a qBf ψ in time 2o(k) · poly(|A|) (tower(2, o(k)) · poly(|A|)) with tw(Gmatrix(ψ)) ∈ o(k).

Notice that the problems i-cσ and i-sσ are simply the corner cases of quantitative reasoning. Indeed, for a semantics σ, a given claim c is credulously (skeptically) accepted using inherited semantics, i.e., c ∈ i-cσ(CF) (c ∈ i-sσ(CF)) iff #cntσ(CF, {c}) ≥ 1 (#cntσ(CF, {¬c}) = 0). Moreover, #cntσ(CF, {c}) computes the number of extensions that cover the claim c (i.e., #i-cσ).

Corollary 15. Let σ ∈ {stab, adm, comp, pref}. Then, the runtime bounds for problems i-sσ, i-cσ and #i-cσ as specified in Table 1 hold.

Finally, for the claim-based extension existence (i-σ) the FPT-results and precise runtimes utilizing treewidth are established via the following corollary.

Corollary 16. Let σ ∈ {stab, adm, comp, pref}. Then, the runtime bounds for i-σ as specified in Table 1 hold.

Next, we present an example for a DG reduction.

Example 17 (DG reduction). Let T be the TD (with set of bags {1, 2} and root(T) = 1) as presented in Figure 3 (1) and (2). To achieve a DG reduction, first observe the following sets: E = {ew, ex, ey, ez}, Vd = {d1w , d1x , d2x , d2y , d2z } and XD = {x1A, x2A} (for the claim D = {A}). Then the reduction Rcb stab (CF, T ) yields ∃E, Vd,X.Φ where Φ is the conjunction of following formulas.

The stable extension {x} covers A and yields a sat. assignment α for Φ, where α(ℓ) = 1 for ℓ ∈ {ex, dtw , duy , duz , xtA} and α(ℓ) = 0 otherwise. Two further stable extensions of CF {w, y} and {w, z} also yield sat. assignments for Φ.

4 AClaim-based Graph for Tractability

Recall that the results in Sect. 3 concern a claim assertion set of fixed size. For a set D of arbitrary size, the presented DG reductions do not linearly preserve the treewidth as witnessed by Formulas (8) and (9). In other words, the given assertions can only be verified at the root node of the given TD as there is no way of associating claims to the arguments otherwise. For extension verification (i-vσ), the treewidth of the primal graph is insufficient for tractability [Dvor´ak andWoltran, 2020].

To mitigate these shortcomings, we present an extended primal graph for CAFs modeling the structure of claim functions explicitly, which then yields further tractability results.

Definition 18 (Extended Primal Graph). Let CF = (A,R, cl) be a CAF with cl(A) = C. Then, the extended primal graph G eCF := (V,E) of CF is defined as: V := A ∪ C, E := {{a, b} | (a, b) ∈ R} ∪ {{a, c} | cl(a) = c}.

In other words, we expand the primal graph of an AF to capture the claim-centric focus via simply connecting arguments to their claims. The representation of claims allows us to relate a set of claims with their arguments and vice versa.

Example 19 (G eCF ). The CAF from Example 2 admits the extended primal graph as depicted in Figure 4 (Left).

There exists the notion of incidence graph for a subclass well-formed (arguments with the same claims attack the same arguments) of CAFs [Dvor´ak and Woltran, 2020]. Given a well-formed CF = (A,R, cl) with cl(A) = C, its incidence graph is defined as Gi := (A∪C,Ei), where Ei := { {a, cl(a)} | a ∈ A } ∪ { {c, a} | (b, a) ∈ R, cl(b) = c }. We argue that the incidence graph when extended from wellformed CAFs to the general case is not a suitable candidate for representing claims. Indeed, such a graph results in information loss regarding attacks between arguments.

Example 20. Consider the two CAFs and their (proposed) incidence graph as depicted in Figure 4. Then, both frameworks have the same incidence graph although the attack (y, x) only appears in one of them.

Furthermore, as the following example illustrates, a dense CAF may result in an incidence graph with low treewidth.

Example 21. Let CF be the CAF as depicted in Fig. 3 (3) and (4). Clearly, CF can be dense, but its (proposed) incidence graph is already a tree and therefore of treewidth 1.

We move on towards DG reductions based on extended primal graphs (denoted as G eCF for a given CF). Here, we reuse the notation from before and also the formulas where applicable. Associate the set of accepted claims with the accepted arguments. Let CF = (A, R, cl) be a CAF with C = cl(A) and T = (T, χ) be a TD of G eCF . Let E := {ea | a ∈ A} and X′ := {xc | c ∈ C} denote the extension and claim variables, respectively. Then, we let act(E,X′ ) := ∧c∈C (xc ↔ cov(c,E)), where cov(c,E) := ∨a∈A,cl(a)=c ea as before. Intuitively, the formula act(E,X′ ) states that an extension E activates a set X′ of claim variables and vice versa. Notice that the formula act(E,X′ ) does not preserve the treewidth and we split it in the same way as the formula cov(c, E).

To split act(E,X′ ), we let X := {xtc | c ∈ C, t in T} denote the activation variables, and define φact(E, X) by:

Form. (10) guide the acceptance status of each claim along the decomposition. These are the same as Form. (7), but written for each claim c ∈ C. Then, claim-based counting for D and semantics σ ∈ {stab, adm, comp, pref} can be solved by appending φact(E,X) as well as Form. (8), (9) to each Rσ, resulting in DG reduction Re-cb σ . Having established DG reductions for linking claims and arguments, we can strengthen results from Sect. 3.1 to arbitrary sets of claim assertions.

4.1 Quantitative Reasoning for ClaimAssertions

We prove that treewidth of the extended primal graph of a CAF allows for FPT-algorithm for evaluating the probability of claim fulfilment for an arbitrary set D of claim assertions. Correctness is established similarly to Theorem 10.

Theorem 22 (Correctness). Let CF = (A, R, cl) be a CAF, D be a set of claim assertions, and T = (T, χ) be a TD of G eCF . Then, DG reduction Re-cb σ (CF, T ) for σ ∈ {stab, adm, comp, pref} is correct, i.e., #cntσ(CF,D) on CF coincides with #SAT (#2-QBF) on ψσ = Re-cb σ (CF, T ).

The presented DG reductions yield the following results.

Theorem 23 (TW-Awareness). Let CF = (A,R, cl) be a CAF, D be a set of claim assertions and T = (T, χ) be a TD of G eCF of width k. Then, the DG reduction Re-cb σ (CF, T ) for σ ∈ {stab, adm, comp, pref} constructs a qBf ψσ s.t. tw(Gmatrix(ψσ)) ∈ O(k).

Proof (Sketch). We construct a TD T ′ = (T, χ′ ) of Gψσ in same way as in proof of Theorem 11. The only difference now is the presence of the formula φact. Recall that the graph G eCF allows edges {a, c} for each a ∈ A with cl(a) = c. As evident from Formulas (10), the variables xt′ c are only added for the children bags with c ∈ χt′ . We present the proof for stab, the argument for other semantics follows the same lines. For every node t of T, we let χ′ (t) := χ(t) ∪ {ea, xtc , dta | a ∈ At, c ∈ Ct} ∪ {xt′ c , dt′ a | a ∈ At ∩At′ , c ∈ Ct ∩Ct′ , t′ ∈ children(t)}, where At := χ(t) ∩ A and Ct := χ(t) ∩ C. Since |children(t)| ≤ 2, we have that |χ′ (t)| ≤ 5 · |χ(t)|.

Now, we provide the runtime bounds for the problems.

Theorem 24 (Runtime UB). Let CF = (A,R, cl) be a CAF and D be a set of claim assertions. Then, for σ ∈ {stab, adm, comp} (resp., pref), the problem #cntσ(CF, D) (#cntpref(CF,D)) can be solved in time 2O(k) · poly(|A|) (tower(2,O(k)) · poly(|A|)).

Before proving the lower bounds for #cntσ(CF,D) for a set D of claim assertions, we connect the verification problem with quantitative reasoning. Clearly, verification (i-vσ) can be seen as a subcase of the quantitative reasoning. Let S ⊆ C be a set of claims, then we let D := {c | c ∈ S}∪{¬c | c ∈ C, c ̸∈ S}. Then, for each σ ∈ {stab, adm, comp, pref}: S ∈ i-vσ iff #cntσ(CF,D) > 0. Moreover, the DG reductions for quantitative reasoning also yield results for counting the extensions of a CF covering the given set S (i.e., #cntσ(CF, D)). The next theorem establishes runtime lower bounds for i-vσ implying the similar bounds for #cntσ(CF,D).

Theorem 25 (i-vσ LB). Let CF = (A,R, cl) be a CAF and σ ∈ {stab, adm, comp} (resp., pref). Then the problem i-vσ

can not be solved in time 2o(k) · poly(|A|) (tower(2, o(k)) · poly(|A|)), where k = tw(GCF ).

Proof (Sketch). We establish reductions from 3SAT (resp., spref ) to i-vσ that linearly preserve the treewidth. Then, i-vσ (resp., i-vpref ) can be solved in time 2o(k) · poly(|A|) (tower(2, o(k)) · poly(|A|)), where k = tw(GCF ) iff 3SAT (spref ) can be solved in time 2o(k) · poly(|A|) (tower(2, o(k)) · poly(|A|)), which is a contradiction to known results.

Theorem 26 (Runtime LB). Let CF = (A,R, cl) be a CAF and D be a set of claim assertions. Then, for σ ∈ {stab, adm, comp} (resp., pref) the problem #cntσ(CF, D) (#cntpref (CF,D)) can not be solved in time 2o(k) · poly(|A|) (tower(2, o(k)) · poly(|A|)), where k = tw(G eCF ).

Again, it is not expected that one can significantly improve (decrease) the treewidth in these DG reductions.

Theorem 27 (TW-LB). Let CF = (A,R, cl) be a CAF, D be a set of claim assertions and T be a TD of G eCF of width k. Under ETH, the DG reduction Re-cb σ (CF, T ) for σ ∈ {stab, adm, comp, pref} cannot be significantly improved, i.e., there is no reduction R′ from#cntσ(CF,D) (#cntpref(CF,D)) to#SAT (#2-QBF) yielding a qBf ψ in time 2o(k) · poly(|A|) (tower(2, o(k)) · poly(|A|)) with tw(Gψ) ∈ o(k).

The corollary establishes the tight runtime bounds for i-vσ. Corollary 28. Let σ ∈ {stab, adm, comp, pref}. Then, the runtime bounds for problems i-vσ as specified in Table 1 hold.

5 Conclusion

We introduce a quantitative mode of reasoning in claim-centric argumentation for CAFs that allows for precise reasoning between the purely binary credulous and skeptical reasoning problems. We provide precise computational bounds for the structural restriction treewidth, which is crucial in the quantitative world when considering effects in practical solving. We establish these results by the concept of DG reductions from CAFs under various semantics to SAT/2-QBF. Interestingly, for claim assertions of constant size, the runtime bounds for probσ(CF,D) match those for skeptical reasoning. However, for arbitrary claim assertions, the treewidth of the primal graph for CAFs does not suffice, but the treewidth of the extended primal graph does.

As future work, studying further semantics such as semiSt and stag and Claim-level semantics [Dvor´ak et al., 2021] provide interesting questions. We also believe that investigating stricter parameters, for which recently results on QBFs have been obtained [Fichte et al., 2023a], might be of theoretical interest. Since counting and conditional probabilities are relevant for navigating in search spaces [Fichte et al., 2022b], it could be interesting to use our measures here to provide capacities to navigate within extensions of CAFs. Finally, we believe that utilizing DG reductions in a practical setting could be interesting due to the practical effect of treewidth on counting [Hecher, 2022; Fichte et al., 2023b; Dewoprabowo et al., 2022].

Acknowledgements

Authors are stated in alphabetical order. The work was supported by ELLIIT funded by the Swedish government, by the Austrian Science Fund (FWF) grants J4656, P32830, and Y1329, Society for Research Funding Lower Austria (GFF) grant ExzF-0004, Vienna Science and Technology Fund (WWTF) grants ICT19-060 and ICT19-065, by the European Union's Horizon Europe research and innovation programme within project ENEXA (101070305), and the German Research Organisation (DFG) project ME4279/3-1 (511769688).