Stability and Relevance in Incomplete
Argumentation Frameworks
Daphne ODEKERKEN a,b,1 , AnneMarie BORG a and Floris BEX a,ca Department of Information and Computing Sciences, Utrecht University
b National Police Lab AI, Netherlands Police
c Tilburg Institute for Law, Technology and Society, Tilburg University
ORCiD ID: Daphne Odekerken https://orcid.org/0000-0003-0285-0706, AnneMarie
Borg https://orcid.org/0000-0002-7204-6046, Floris Bex
https://orcid.org/0000-0002-5699-9656
Abstract. We explore the computational complexity of stability and relevance inincomplete argumentation frameworks (IAFs), abstract argumentation frameworks
that encode qualitative uncertainty by distinguishing between certain and uncertain
arguments and attacks. IAFs can be specified by, e.g., making uncertain arguments
or attacks certain; the justification status of arguments in an IAF is determined on
the basis of the certain arguments and attacks. An argument is stable if its justification status is the same in all specifications of the IAF. For arguments that are notstable in an IAF, the relevance problem is of interest: which uncertain arguments
or attacks should be investigated for the argument to become stable? We redefinestability and define relevance for IAFs and study their complexity.
Keywords. Incomplete argumentation frameworks, stability, relevance, complexity

1. Introduction
Computational argumentation is an important research field in artificial intelligence, concerning reasoning with incomplete or inconsistent information [1]. A central concept
are argumentation frameworks (AFs): a set of arguments and an attack relation between
them [2]. Given an AF and so-called semantics, one can determine extensions: sets of arguments that can collectively be considered to be acceptable. Based on these extensions,each argument has at least one justification status (in terms of e.g. labels like IN, OUT
and UNDEC). However, in practice, argumentation is a dynamic process in which not allarguments may be known in advance. Incomplete argumentation frameworks (IAFs) aredesigned to handle this dynamic process by extending AFs to allow for both certain anduncertain arguments and attacks [3,4,5,6]. In this paper, we study two problems in IAFs
and their complexity for various semantics: stability and relevance.
Detecting stability was initially introduced for the ASPIC+ framework in [7] andsubsequently studied for structured and abstract argumentation settings in [8,6]. Informally, an argument is stable if more information cannot change its justification status.
1 Corresponding Author; E-mail: d.odekerken@uu.nl

Stability detection has practical applications, for instance as a termination criterion forargumentative dialogue agents: in the agent architecture for inquiry proposed in [8], stability detection prevents the agent from asking unnecessary questions. In addition, [6]proposes an application of stability detection in negotiating agents, to recognise situations in which an agent should stop negotiating and accept its opponent’s offer.
For situations in which the argument of interest is not stable in the given IAF, anatural question would be: which uncertainties should we resolve in order to reach apoint where the argument is stable? In other words: which uncertain arguments or attacks
are still relevant for the justification status? Adding relevance to an inquiry/negotiation
process ensures that the questions that are asked contribute to reaching stability.
The contribution of this paper is the extensive study of both stability and relevancein the context of IAFs. Specifically, first we (re)define stability on IAFs, considering
not only IN, but also OUT and UNDEC justification statuses. This results in a more finegrained notion of stability than an earlier definition in [6]. Second, we present precise
complexity results for stability of all these justification statuses in grounded, complete,stable and preferred semantics, refining preliminary results in [6]. Third, we define a notion of relevance in the context of reaching stability in IAFs. Finally, we present preliminary complexity results for the introduced relevance detection problem.
The paper is structured as follows. In Section 2, we provide the necessary preliminaries. In Section 3, we study the complexity of identifying the justification status ofan argument and use these results in our complexity analysis of the stability problem.
We then introduce the relevance problem for IAFs in Section 4 and provide complexity
results. Related work is discussed in Section 5; we conclude in Section 6.

2. Preliminaries
In this section, we recall the most important notions from abstract argumentation andthe considered semantics [2] as well as incomplete argumentation frameworks [3,4,5,6]
and their specifications. Finally, we give a brief introduction to the polynomial hierarchy,
which is required for our complexity study.
2.1. Argumentation frameworks and semantics
An argumentation framework ⟨A, R⟩ (AF) consists of a finite set A of arguments and abinary attack relation R ⊆ A × A on them, where (A, B) ∈ R indicates that argument A
attacks argument B. The evaluation of arguments is done using the semantics of [2].
Definition 1 (Extension-based semantics). Let AF = ⟨A, R⟩ be an AF and S ⊆ A. Then:• S is conflict-free iff for each X,Y ∈ S : (X,Y ) ̸∈ R;• X ∈ A is acceptable with respect to S iff for each Y ∈ A such that (Y, X) ∈ R,
there is a Z ∈ S such that (Z,Y ) ∈ R;
• S is an admissible set iff S is conflict free and X ∈ S implies that X is acceptablewith respect to S;• S is a complete extension (CP) iff S is admissible and for each X: if X ∈ A is
acceptable with respect to S then X ∈ S;
• S is a preferred extension (PR) iff it is the set inclusion maximal admissible set;• S is the grounded extension (GR) iff it is the set inclusion minimal complete extension; and• S is a stable extension (ST) iff it is complete and attacks all the arguments in A \ S.
2.2. Incomplete argumentation frameworks
Incomplete argumentation frameworks (IAFs) are an extension to AFs, initially proposed
as partial AFs in [3] and later studied as IAFs in e.g. [4,5,6]. In an IAF, the set of arguments and attacks is split into two disjoint parts: a certain part (A and R) and an uncertain part (A? and R? ). For the uncertain elements, it is not known whether they are partof the argumentation framework or not. They may be added in the future, for example
because more information is acquired in an inquiry dialogue, or removed, for example
because after investigation, this element turned out not to be present in the given setting.
Definition 2 (Incomplete argumentation framework). An incomplete argumentation
framework is a tuple I = ⟨A, A? , R, R? ⟩, where A ∩ A? = 0,
/ R ∩ R? = 0/ and:• A is the set of certain arguments;• A? is the set of uncertain arguments;• R ⊆ (A ∪ A? ) × (A ∪ A? ) is the certain attack relation; and• R? ⊆ (A ∪ A? ) × (A ∪ A? ) is the uncertain attack relation.
An IAF can be specified by obtaining more information about the uncertain part.
Definition 3 (Specification). Given an IAF I = ⟨A, A? , R, R? ⟩, a specification is an IAF
I ′ = ⟨A′ , A?′ , R′ , R?′ ⟩, where:• A ⊆ A′ ⊆ A ∪ A? ;• R ⊆ R′ ⊆ R ∪ R? ;• A?′ ⊆ A? ;• R?′ ⊆ R? .
We denote all possible specifications for I by F(I). Note that A′ ∩ A?′ = 0/ and R′ ∩R?′ = 0/ because I ′ is an IAF.
Since the semantics of [2] are defined on AFs, we define the certain projection of an
IAF, which is an AF consisting of only the IAF’s certain arguments and attacks.
Definition 4 (Certain projection). Given an IAF I = ⟨A, A? , R, R? ⟩, the certain projection is the argumentation framework AF = ⟨A, R ∩ (A × A)⟩.
Note that our definition of specification is similar to the notion of completion used inrelated work on IAFs [4,5]. Intuitively, a completion is a certain projection of a specification and is therefore not suitable for keeping track of the uncertain elements. Since thedevelopment of uncertain elements is essential for defining and studying the relevanceproblem (see Section 4), we use the notion of specification rather than completion.
2.3. The polynomial hierarchy
The polynomial hierarchy [9] is a hierarchy of complexity classes above NP definedusing oracle machines, i.e. Turing machines that are allowed to call a subroutine (oracle),deciding some fixed problem in constant time. For a class of decision problems C and aclass X defined by resource bounds, X C denotes the class of problems decidable on a
Turing machine with a resource bound given by X and an oracle for a problem in C.
Based on these notions, the sets Σkp and Πkp are defined as follows: Σ0p = Π0p = ∆0p =pppp= CoNPΣk . The canonical complete problem for Σkp is k= NPΣk and Πk+1
P, Σk+1
QBF , which is the problem of deciding whether the quantified boolean formula with kalternating quantifiers, starting with an existential quantifier, is true for a formula Φ – forexample, deciding if ∃Xs.t. ∀Y : Φ[X,Y ] = True is Σ2p -complete. The complement of a
k-QBF problem, denoted by co-k- QBF, is complete for Πkp .

3. Justification status and stability
In order to define and study stability and relevance, we need a definition of justification
status. Given an AF ⟨A, R⟩, an argument A and a semantics σ , A’s justification status
can be determined by either considering all σ -extensions (sceptical) or at least one σ extension of the AF (credulous). In this context, an argument can be IN (part of all/someσ -extensions); OUT (attacked by all/some σ -extensions), or UNDEC (otherwise) [10].
Definition 5 (Argument justification status). Let AF = ⟨A, R⟩ be an argumentation
framework and σ some semantics in {GR, CP, PR, ST}. Let A be some argument in A.
• A is σ -sceptical-IN (resp. σ -credulous-IN) iff A belongs to each (resp. some) σ extension of AF;• A is σ -sceptical-OUT (resp. σ -credulous-OUT) iff for each (resp. some) σ extension S of AF, A is attacked by some argument in S;• A is σ -sceptical-UNDEC (resp. σ -credulous-UNDEC) iff for each (resp. some) σ extension of AF, A is not in S and not attacked by any argument in S.
The justification statuses that we consider in this paper are {GR, CP, PR, ST} ×{sceptical, credulous} × {IN, OUT, UNDEC}. Based on these justification statuses, we can
now define stability:
Definition 6 (Stability on IAFs). Given an IAF I = ⟨A, A? , R, R? ⟩, a certain argument
A ∈ A and some justification status j, A is stable- j w.r.t. I iff for each specification
I ′ = ⟨A′ , A?′ , R′ , R?′ ⟩ in F(I), A is j w.r.t. the certain projection of I ′ .
Note that whereas the sceptical stability variants are mutually exclusive, this does
not apply for the credulous stability variants, where an argument may have multiple
stability statuses at the same time. Consider the following example:
Example 1. Let I = ⟨A, A? , R, R? ⟩ be an incomplete argumentation framework with
/ R = {(A, B), (B, A)}; note that F(I) = {I}. Both A and B are
A = {A, B}, A? = R? = 0,
stable-CP-credulous-IN, stable-CP-credulous-OUT and stable-CP-credulous-UNDEC. For
σ ∈ {ST, PR}, both A and B are stable-σ -credulous-IN and stable-σ -credulous-OUT. On
the other hand, for semantics σ ∈ {CP, ST, PR}, A and B are not stable-σ -sceptical-IN,-OUT or -UNDEC.

An alternative definition of stability on IAFs has been proposed before in [6], but
this definition only takes the IN status of arguments into account. Since other justification statuses are not studied, it is not possible to distinguish for example situations inwhich the justification status of an argument is UNDEC in each certain projection fromsituations where the justification status is always either OUT or UNDEC. Our definitionof stability on IAFs is more fine-grained as it also includes OUT- and UNDEC-stability.
In addition, we will provide precise complexity results, refining preliminary complexity
bounds from [6].
We formulate the identification of justification and stability statuses as decision
problems:
j-JUSTIFICATION
Given:An argumentation framework ⟨A, R⟩ and an argument A ∈ A
Question: Does A’s justification status in ⟨A, R⟩ equal j?
j-STABILITY
Given:
An incomplete argumentation framework ⟨A, A? , R, R? ⟩, a justification
status j and an argument A ∈ A
Question: Does A’s stability status w.r.t. ⟨A, A? , R, R? ⟩ equal stable- j?
For some variants of the stability problem, we can directly use complexity resultsfrom earlier work, in particular the results on necessary sceptical and credulous acceptance presented in [5]. Specifically, for a given semantics σ ∈ {GR, CP, PR, ST}, an argument is stable-σ -sceptical-IN iff it is necessary sceptically accepted w.r.t. the corresponding IAF; similarly, the set of stable-σ -credulous-OUT arguments coincides with thenecessary credulously accepted arguments (see Section 5 for a discussion). See Table 1
for an overview of these results.
σc/s

statusJUSTIFICATIONSTABILITYSTcc

IN / OUT

NP-c [11,12]
Trivial (no)

Π2p -c [5]Trivial (no)ssIN / OUT

CoNP-c [11]CoNP-c [11] (Trivial (no))

CoNP-c (Π2p -c) [5]
CoNP-c (Trivial (no))

IN / OUT

CP

c
c
s

IN / OUT

NP-c [11,12]P-cP-c [2]

Π2p -c [5]CoNP-cCoNP-c [5]

CP

s

UNDEC

CoNP-cCoNP-cGR

IN / OUT

GR

c
c
s

IN / OUT

P-c [2]P-cP-c [2]

CoNP-c [5]CoNP-cCoNP-c [5]

GR

s

UNDEC

P-c

CoNP-cPRccs

IN / OUT

NP-c [11,12]
Σ 2p -cp
Π2 -c [13]

Π2p -c [5]Π 3p -c
Π2p -c [5]

ST
ST
ST
CP
CP

GR

PR
PR

UNDEC

UNDEC

UNDEC

UNDEC

UNDEC
IN / OUTRELEVANCE

NP-c
NP-c
NP-c

PR
s
UNDEC
CoNP-cCoNP-cTable 1. Overview of all complexity results related to this paper. If a reference is specified, this complexity
result is trivial from an earlier result in the literature. New results are printed bold; their proofs can be found in
the appendix. Results for ST-sceptical-existence justification and stability are given in parentheses.

The complexity of OUT-STABILITY has not been studied, but can be derived fromthe complexity of identifying IN-STABILITY by a reduction from the corresponding INJUSTIFICATION problems. In the following lemma, we show that these complexities are
the same for each of the semantics considered in this paper:2
Lemma 1. For any given σ ∈ {GR, CP, PR, ST} and c ∈ {sceptical, credulous}, the complexity of σ -c-OUT-STABILITY equals the complexity of σ -c-IN-STABILITY.
A similar result exists for IN-JUSTIFICATION and OUT-JUSTIFICATION. The resultsfor UNDEC-JUSTIFICATION can be found in Table 1 and the appendix. The complexityof UNDEC-STABILITY cannot be derived in a general way from e.g. IN-STABILITY: theapproach depends on the chosen semantics. We can however provide a general upperbound based on the complexity of UNDEC-JUSTIFICATION:
Proposition 1 (Upper bound j-STABILITY). Given an IAF I = ⟨A, A? , R, R? ⟩, a certain
argument A ∈ A and a justification status j, if the complexity of j-JUSTIFICATION in⟨A, R⟩ is C, the j-STABILITY problem given A and I is in CoNPC .
Proof. In a negative instance (I, A) of j-STABILITY, there is some I ′ ∈ F(I) such that
A is not j in the certain projection of I ′ . A polynomial-size certificate for this instancewould for example be a specification I ′ = ⟨A′ , 0,
/ R′ , 0⟩/ in F(I) such that A is not j in
AF′ = ⟨A′ , R′ ∩ (A′ × A′ )⟩. Verification that I ′ ∈ F(I) can be done in polynomial time;
the j-justification status check of A in AF′ is done by calling a C oracle.
Note that the complexity of identifying the stability or justification status for UN DEC statuses may be higher or lower than the complexity of identifying the IN or
OUT status. For example, for ST semantics the credulous JUSTIFICATION and STABIL ITY identification of the UNDEC status is trivial: under ST semantics arguments are either in the extension or attacked by the extension, but identifying the IN/OUT status is

NP (JUSTIFICATION) and even in Π2p (STABILITY). On the other hand, PR-credulousUNDEC - JUSTIFICATION is on a higher level in the polynomial hierarchy than PR credulous-IN-JUSTIFICATION: while PR-credulous-IN-JUSTIFICATION is in NP (sinceverification of a positive instance can be done in polynomial time, given an admissible set containing the argument as a certificate), PR-credulous-UNDEC-JUSTIFICATION
is Σ2p -hard as it can be reduced from 2-QBF.
For other semantics, the complexity of UNDEC-STABILITY does not differ from theIN - STABILITY complexity. This is for example the case for GR semantics and CP semantics for the sceptical justification status. In order to prove this, we next give a reduction
from UNSAT (co-1-QBF), which is based on the reduction from [5, Definition 14] andillustrated in the black part of Figure 1.
Definition 7 (Reduction). Let (φ , X) be an instance of 1-QBF or co-1-QBF and let φ =VWi ci , where ci = j α j for each clause ci in φ and α j are the literals over X that occur
in clause ci . We define the corresponding IAF for this instance as ⟨A, A? , R, 0⟩,/ where:• A = {xi , xi | xi ∈ X} ∪ {ci | ci ∈ φ } ∪ {φ , φ };• A? = {gi | xi ∈ X};
2 Proofs of omitted results in the remainder of the paper can be found in the online appendix https://www.
uu.nl/onderzoek/ai-labs/nationaal-politielab-ai/stability-relevance-iafs.

• R = {(gi , xi ) | xi ∈ X} ∪ {(xi , xi ) | xi ∈ X} ∪ {(xk , ci ) | xk ∈ ci } ∪ {(xk , ci ) | ¬xk ∈ci } ∪ {(ci , φ ) | ci ∈ φ } ∪ {(φ , φ ), (φ , φ )}.
g1
x1

g2
x1

g3
x2

x2

x3

c1
φ

x3

c2
φ

χ

χ

Figure 1. Visualisation of the IAF created for the clauses c1 = x1 ∨ ¬x2 and c2 = x2 ∨ ¬x3 using the reductionsof Definition 7, only the black parts of the figure and Definition 11, also including the gold/gray part. We use
this reduction for GR, CP and sceptical PR semantics.

The reduction is used in the proof of the following proposition.
Proposition 2. GR-sceptical-UNDEC-STABILITY, GR-credulous-UNDEC-STABILITY
and CP-credulous-UNDEC-STABILITY are CoNP-complete.
Proof sketch. Let (φ , X) be a co-1-QBF (UNSAT) instance and let I = ⟨A, A? , R, R? ⟩ be
the IAF according to Definition 7. As GR semantics results in a single extension, whichis the intersection of all CP extensions, the problems GR-sceptical-UNDEC-STABILITY,
GR -credulous- UNDEC - STABILITY and CP -credulous- UNDEC - STABILITY coincide. The
argument φ can only be stable-UNDEC if for each specification of I, the argument φ
is OUT, which can only be the case if there is at least one clause in φ such that thecorresponding argument for ci is IN. Thus the following items are equivalent:
1. (φ , X) is a positive UNSAT instance;
2. the argument for φ is stable-GR-sceptical-UNDEC in I;
3. the argument for φ is stable-GR-credulous-UNDEC in I;
4. the argument for φ is stable-CP-credulous-UNDEC in I.
CoNP-hardness from UNDEC-STABILITY follows from CoNP-hardness of UNSAT.
From Proposition 1 and the fact that the corresponding JUSTIFICATION problems are in
P, we conclude CoNP-completeness.
In the following proposition, we consider the sceptical variants of the UNDECSTABILITY under CP and PR semantics.

Proposition 3. CP-sceptical-UNDEC-STABILITY and PR-sceptical-UNDEC-STABILITY
are CoNP-complete.
Proof sketch. CP-sceptical-UNDEC-STABILITY and PR-sceptical-UNDEC-STABILITY arein CoNP, since negative instances (I, A) can be verified in polynomial time given a certificate (AF′ , S) such that I ′ ∈ F(I), AF′ is the certain projection of I ′ , A ∈ A and S is anadmissible set of AF′ containing either A itself or an argument attacking A. For hardness,note that the corresponding (CoNP-hard) JUSTIFICATION problems can be reduced tothese STABILITY problems, leaving the uncertain part empty.

Proposition 4 states that the PR-credulous-UNDEC-STABILITY problem is on thethird level of the polynomial hierarchy. For the proof, we refer to the appendix.
Proposition 4. PR-credulous-UNDEC-STABILITY is Π3p -complete.
Finally, we consider UNDEC-STABILITY under ST semantics. Recall from Definition 1 that for each ST extension S of an AF, each argument in AF is either in S or attacked
by some argument in S. Consequently, an argument can only be stable-ST-scepticalUNDEC if the AF has no ST extension. We use this property in the following proposition:
Proposition 5. ST-sceptical-UNDEC-STABILITY is CoNP-complete.
Proof sketch. The problem is in CoNP, as a no-instance (I, A) can be verified in polynomial time given a certificate (AF′ , S) such that I ′ ∈ F(I), AF′ is the certain projection of
I ′ and S is a ST extension of AF′ . If S is a ST extension then each argument in A is either in S or attacked by S; therefore no argument can be stable-ST-sceptical-UNDEC w.r.t.
I. For hardness, we can reduce from the CoNP-complete problem ST-sceptical-UNDECJUSTIFICATION .
This result for sceptical acceptance may feel counterintuitive. Therefore, we consider an alternative version of justification and stability (based on [14]) for ST semantics,
in which it is assumed that a ST extension exists.
Definition 8 (Sceptical-existent justification). Given an argumentation framework AF =⟨A, R⟩, argument A ∈ A and label LAB ∈ {IN, OUT, UNDEC}, A is ST-sceptical-existentLAB w.r.t. AF iff AF has at least one ST extension and A is ST-sceptical- LAB in AF.
As no AF has a ST extension S in which some argument is neither in S, nor attacked
by any argument in S, ST-sceptical-existent-UNDEC-STABILITY is False for all inputs.
The same holds for ST-credulous-UNDEC-STABILITY, so these problems are trivial:
Proposition 6. ST-credulous-UNDEC-STABILITY and ST-sceptical-existent-UNDECSTABILITY are trivial.

4. Relevance
For IAFs in which a given argument is not stable, a natural follow-up question would
be which uncertainties should be resolved in order to reach a point where the argument
is stable: these uncertainties are relevant to investigate in the given IAF. In this section,
we will define the problem of relevance and study its complexity. First, we give some
intuition on the notion of relevance in the context of stability in the following example.
Example 2. Let I = ⟨A, A? , R, R? ⟩ be the IAF illustrated in Figure 2, where only arguments A and C are certain and let j be GR-sceptical-IN; suppose that we want toknow if argument A is j-stable. A is not j-stable in I, but it will become j-stable ineach I ′ ∈ F(I) such that I ′ = ⟨A′ , A?′ , R′ , R?′ ⟩ and D ∈/ A′ ∪ A?′ or E ∈ A′ . Therefore,
it would be relevant to investigate if D can be removed from the uncertain arguments
and/or if E can be added to the certain arguments. Note that investigation of B does notcontribute towards a stable situation and therefore would not be relevant.

D

A
B

E

C

Figure 2. Visualisation of IAF ⟨A, A? , R, R? ⟩ used to illustrate the definition of relevance. In this figure,certain arguments in A are depicted as nodes with solid borders (i.e. A and C), while uncertain arguments in
A? have dashed borders (i.e. B, D and E). The arrows between them correspond to attacks in R.

Before proceeding to a formal definition of relevance that matches the intuitions in
the example above in Definition 10, we define the notion of minimal stable specifications.
Definition 9 (Minimal stable- j specification). Given an IAF I = ⟨A, A? , R, R? ⟩, a certain argument A ∈ A and a justification status j, a minimal stable- j specification for A
w.r.t. I is a specification I ′ in F(I) such that A is stable- j in I ′ and there is no specification I ′′ in F(I) such that A is stable- j in I ′′ , I ′′ ̸= I ′ and I ′ ∈ F(I ′′ ).
Intuitively, the minimal stable- j specification for A is a specification in which A isstable- j, while A would not be stable- j in any specification with more uncertain elements.
Example 3. Reconsider the IAF I = ⟨A, A? , R, R? ⟩ from Example 2:• There are two minimal stable-GR-sceptical-IN specifications for A w.r.t. I. Theseare ⟨{A,C, E}, {B, D}, R, R? ⟩ and ⟨{A,C}, {B, E}, R, R? ⟩;• There are three specifications for A w.r.t. I for which A becomes stable-GRsceptical-OUT: I1 = ⟨{A,C, D}, {B}, R, R? ⟩, I2 = ⟨{A,C, D}, 0,/ R, R? ⟩ and I3 =?
⟨{A, B,C, D}, 0,/ R, R ⟩. Only I1 is minimal, because both I2 and I3 are in F(I1 );• None of the specifications is minimal stable-GR-sceptical-UNDEC.
Using the notion of minimal stable- j specifications, we can now define j-RELEVANCE.
Definition 10 ( j-RELEVANCE). Given an IAF I = ⟨A, A? , R, R? ⟩, an argument A ∈ A,
an uncertain argument or attack U ∈ A? ∪ R? and a justification status j,• Addition of U is j-relevant for A w.r.t. I iff there is a minimal stable- j specification
I ′ = ⟨A′ , A?′ , R′ , R?′ ⟩ for A w.r.t. I such that U ∈ A′ ∪ R′ ; and• Removal of U is j-relevant for A w.r.t. I iff there is a minimal stable- j specification
I ′ = ⟨A′ , A?′ , R′ , R?′ ⟩ for A w.r.t. I such that U ∈/ A′ ∪ A?′ ∪ R′ ∪ R?′ .
In other words, addition of an uncertain element U is j-relevant if a minimal stable- j
specification can be reached by moving U from the certain to the uncertain part of the
IAF I; and removal of U is j-relevant if completely removing U from I, possibly in
combination with other actions, leads to a minimal stable- j specification.
Example 4. Recall from Example 3 that only I1 = ⟨{A,C, D}, {B}, R, R? ⟩ is a minimal
stable-GR-sceptical-OUT specification for A w.r.t. I. Therefore, only addition of D andremoval of E are GR-sceptical-OUT-relevant for A w.r.t. I.
Like for justification and stability status, we formulate the identification of jRELEVANCE as a decision problem:j-RELEVANCE of action a
Given:
An incomplete argumentation framework ⟨A, A? , R, R? ⟩, a justification
status j, an action a ∈ {addition, removal}, an argument A ∈ A and an
uncertain argument or attack U ∈ A? ∪ R? .
Question: Is a of U j-relevant for A w.r.t. ⟨A, A? , R, R? ⟩?
The following lemma, proven in the appendix, shows that the relevance of adding
or removing an uncertain element can be validated by checking the justification statusof the certain projections of two particular future specifications. This property will be
useful for proving an upper bound on j-RELEVANCE.
Lemma 2. Given an IAF I = ⟨A, A? , R, R? ⟩, a certain argument A ∈ A and a justification status j:
1. For each U ∈ A? , addition of U is j-relevant for A w.r.t. I iff there exists someI ′ = ⟨A′ , {U}, R′ , 0⟩
/ ∈ F(I) such that A is not j in the certain projection of I ′ ,while A is j in the certain projection of ⟨A′ ∪ {U}, 0,/ R′ , 0⟩.
/?
2. For each U ∈ R , addition of U is j-relevant for A w.r.t. I iff there exists someI ′ = ⟨A′ , 0,
/ R′ , {U}⟩ ∈ F(I) such that A is not j in the certain projection of I ′ ,while A is j in the certain projection of ⟨A′ , 0,
/ R′ ∪ {U}, 0⟩.
/?
3. For each U ∈ A , removal of U is j-relevant for A w.r.t. I iff there exists someI ′ = ⟨A′ , {U}, R′ , 0⟩
/ ∈ F(I) such that A is j in the certain projection of I ′ , while
A is not j in the certain projection of ⟨A′ ∪ {U}, 0,/ R′ , 0⟩.
/?
4. For each U ∈ R , removal of U is j-relevant for A w.r.t. I iff there exists someI ′ = ⟨A′ , {U}, R′ , 0⟩
/ ∈ F(I) such that A is j in the certain projection of I ′ , while
A is not j in the certain projection of ⟨A′ , 0,
/ R′ ∪ {U}, 0⟩.
/In the following proposition, we use the results from Lemma 2 to prove a general
upper bound on the complexity of j-RELEVANCE.
Proposition 7 (Upper bound j-RELEVANCE). Given an IAF I = ⟨A, A? , R, R? ⟩, a certain argument A ∈ A, an uncertain argument or attack U ∈ A? ∪ R? and a justification
status j, if the complexity of deciding j’s justification status in ⟨A, R⟩ is C, then an upperbound on the problem of deciding if addition and/or removal of U is j-relevant for A
w.r.t. I is NPC .
In order to prove a lower bound of j-RELEVANCE for GR and CP sceptical semantics,
we use the following reduction. This reduction is illustrated in Figure 1 in gold.
Definition
11 (Reduction
relevance). Let (φ , X) be an instance of 1-QBF or co-1-QBF
VW
let φ = i ci and ci = j α j for each clause ci in φ , where α j are the literals over X that
occur in clause ci . Let ⟨A, A? , R, 0⟩/ be the reduction from Definition 7 of this instance.
We define the corresponding IAF for this instance as ⟨A′ , A?′ , R′ , 0⟩,/ where A′ = A ∪?′?
′{χ}; A = A ∪ {χ}; and R = R ∪ {(χ, χ), (χ, φ )}.
Using the reduction above, we can now give tight complexity bounds for GR and CP
semantics for the sceptical justification status.
Proposition 8. GR-sceptical-IN-RELEVANCE, GR-credulous-IN-RELEVANCE and CPsceptical-IN-RELEVANCE are NP-complete.

Proof sketch. Given an instance of 1-QBF (SAT), let I be the IAF constructed according
to Definition 11 where Y = 0.
/ Addition of χ is GR-sceptical-IN-relevant for φ w.r.t. I iff
there is some I ′ ∈ F(I) such that φ is GR-sceptical-IN, having χ in its certain arguments
iff the SAT instance is True. NP-completeness follows from Proposition 8 and the factthat the corresponding JUSTIFICATION problems are in P.

5. Related work
The computational complexity of various problems defined on argumentation frameworks is well-studied; see [15] for an overview. Most studies only identify IN arguments
and do not distinguish other justification statuses; notable exceptions are [16] and [17],but neither of these works give complexity results for separate statuses, as we do.
Complexity studies on problems defined on IAFs emerged more recently. For example, variants of the verification problem on IAFs are studied in [4]. The problems of stability and relevance differ from the verification problem as they are defined on arguments
rather than sets of arguments. More related is [5]: the authors study potential and necessary credulous and sceptical acceptance in IAFs, where necessary sceptical acceptanceof a given argument A, for example, means that in each specification’s certain projection,
each extension (under a given semantics) contains A. The notions of necessary credulous
and sceptical acceptance are very similar to specific stability problems: in fact, we used
results regarding their complexity for proving the complexity of stable-IN statuses. Finally, the notion of stability, which was originally defined on structured argumentation
frameworks in [7], is transposed to the context of IAFs in [6] and preliminary complexity
results for stability under four semantics are provided. In our work, we define a morefine-grained notion of stability and provide more precise complexity characterisations.
Our notion of relevance has not been introduced or studied before. It is related to
the notion of influenced sets in e.g. [18], which intuitively are sets of arguments whose
justification status may change after an update. This notion is however less strict than
relevance: there are situations in which some argument A would be in the influenced setof adding an uncertain attack (B,C), while addition of (B,C) is not relevant for A.

6. Conclusion
We studied the complexity of detecting stability and relevance in incomplete argumentation frameworks. First, we redefined stability [7,8,6] on IAFs. Our definition is a morefine-grained notion than the existing definition on IAFs [6], since it distinguishes between
IN , OUT and UNDEC justification statuses. This distinction is appropriate in for example
applications in inquiry [7,8], where a dialogue discussing a given argument should beterminated if more information cannot change the argument’s (exact) justification status.
As second main contribution of this paper, we introduced the notion of relevance,
which has not been studied before in the context of stability, and analysed its complexity.
Returning to the application in inquiry, the identification of relevant elements can be used
to select the next question, reaching a stable situation in an efficient way.
It is however unlikely that the stability and relevance problem itself can be solved
efficiently for all inputs: our complexity analysis revealed that the nontrivial variants

of the relevance and stability problems have a complexity ranging from the first to thethird level of the polynomial hierarchy; see Table 1 for an overview. Interestingly, even
within the same semantics, there are differences in the complexity of UNDEC-STABILITY
problems and the corresponding IN-STABILITY problems – we consider this to be an
additional reason to study a fine-grained notion of stability and relevance.
In future work we will complete Table 1, by studying the computational complexity of relevance for the other semantics and UNDEC status. In addition, to apply these
theoretical concepts in practice, we plan to develop algorithms for evaluating or estimating stability and relevance. Finally, we will study stability and relevance in structured
argumentation frameworks, such as a dynamic version of ASPIC+ , for various semantics.
References
[1]
[2]

[3]

[4]
[5]
[6]
[7]

[8]
[9]
[10]
[11]
[12]

[13]
[14]
[15]
[16]

[17]

[18]

Atkinson K, Baroni P, Giacomin M, Hunter A, Prakken H, Reed C, et al. Towards artificial argumentation. AI magazine. 2017;38(3):25-36. doi:10.1609/aimag.v38i3.2704.
Dung PM. On the acceptability of arguments and its fundamental role in nonmonotonic reasoning,
logic programming and n-person games. Artificial Intelligence. 1995;77:321-57. doi:10.1016/00043702(94)00041-X.
Cayrol C, Devred C, Lagasquie-Schiex MC. Handling ignorance in argumentation: Semantics of partial
argumentation frameworks. In: European Conference on Symbolic and Quantitative Approaches toReasoning and Uncertainty. Springer; 2007. p. 259-70. doi:10.1007/978-3-540-75256-1 25.
Baumeister D, Neugebauer D, Rothe J, Schadrack H. Verification in incomplete argumentation frameworks. Artificial Intelligence. 2018;264:1-26. doi:10.1016/j.artint.2018.08.001.
Baumeister D, Järvisalo M, Neugebauer D, Niskanen A, Rothe J. Acceptance in incomplete argumentation frameworks. Artificial Intelligence. 2021;295:103470. doi:10.1016/j.artint.2021.103470.
Mailly JG, Rossit J. Stability in Abstract Argumentation. In: NMR 2020 Workshop Notes; 2020. p.
93-9. doi:10.48550/arXiv.2012.12588.
Testerink B, Odekerken D, Bex F. A Method for Efficient Argument-based Inquiry. In: Proceedings ofthe 13th International Conference on Flexible Query Answering Systems. Springer International Publishing; 2019. p. 114-25. doi:10.1007/978-3-030-27629-4 13.
Odekerken D, Borg A, Bex F. Estimating Stability for Efficient Argument-based Inquiry. In: Computational Models of Argument. Proceedings of COMMA 2020; 2020. p. 307-18. doi:10.3233/FAIA200514.
Papadimitriou C. Computational Complexity. Addison-Wesley; 1994.
Caminada M. On the issue of reinstatement in argumentation. In: European Workshop on Logics in
Artificial Intelligence. Springer; 2006. p. 111-23. doi:10.1007/11853886 11.
Dimopoulos Y, Torres A. Graph theoretical structures in logic programs and default theories. TheoreticalComputer Science. 1996;170(1-2):209-44.
Coste-Marquis S, Devred C, Marquis P. Symmetric argumentation frameworks. In: European Conference on Symbolic and Quantitative Approaches to Reasoning and Uncertainty. Springer; 2005. p.
317-28. doi:10.1007/11518655 28.
Dunne PE, Bench-Capon TJ. Coherence in finite argument systems. Artificial Intelligence. 2002;141(12):187-203. doi:10.1016/S0004-3702(02)00261-8.
Dunne PE, Wooldridge M. Complexity of abstract argumentation. In: Argumentation in artificial intelligence. Springer; 2009. p. 85-104. doi:978-0-387-98197-0 5.
Dvorák W, Dunne PE. Computational problems in formal argumentation and their complexity. Handbook of formal argumentation. 2018:631-87.
Dvořák W. On the complexity of computing the justification status of an argument. In: International Workshop on Theorie and Applications of Formal Argumentation. Springer; 2011. p. 32-49.
doi:10.1007/978-3-642-29184-5 3.
Alfano G, Greco S, Parisi F, Trubitsyna I. Incomplete Argumentation Frameworks: Properties andComplexity. In: Proceedings of the AAAI Conference on Artificial Intelligence; 2022. p. 5451-60.
doi:10.1609/aaai.v36i5.20483.
Alfano G, Greco S, Parisi F, , Simari GI, Simari GR. On the Incremental Computation of Semantics inDynamic Argumentation. Journal of Applied Logics. 2021;8(6):1749-92.