Justification, stability and relevance in incomplete argumentation frameworks

1.Introduction

A central concept in computational argumentation is that of argumentation frameworks (AFs), in which arguments and the attack relation between them are represented as a directed graph where nodes correspond to arguments and edges display the attack relation [10]. One of the assumptions in such Dung-style argumentation frameworks is that all arguments and attacks are known. However, in practice, argumentation is a dynamic process in which not all arguments and attacks may be known in advance. For example, not all the evidence on which arguments are based might already have been observed, making the presence of a specific argument uncertain [16]. AFs are not able to represent qualitative uncertainty on the existence of specific arguments and attacks. For this reason, incomplete argumentation frameworks (IAFs) have been designed [3,4,7,15]. IAFs are an extension to AFs in which not only certain arguments are specified, but also arguments and attacks for which it is uncertain whether they are present. By deciding for every uncertain argument and attack whether it is present or absent, it is possible to “complete” an IAF, turning it into an AF. Thus, an IAF represents a set of possible AFs, its completions.

Since every completion of an IAF is an AF, standard Dung semantics can be applied to determine the extensions of any completion [10]. Based on these extensions, one can determine the justification status of every argument in every completion of the IAF. The justification status is defined in terms of labels like in (expressing that the argument is in some, or all, extensions and therefore should be accepted), out (expressing that the argument is attacked by an in argument and therefore should be rejected) and undec (for all other arguments, which are undecided) [6]. Note that the notion of justification status is only defined on the AFs that make up the completions of an IAF, but not on the IAF itself.

Now suppose that we are interested in the justification status of a particular argument, but are faced with an IAF containing uncertainties concerning the presence of (other) arguments and attacks. Then it would be interesting to know whether it is required to resolve these uncertainties. In a situation where the argument we are interested in has the same justification status in each completion of the IAF, there is no need for further investigation into the uncertain arguments and attacks. Then we say that the argument is stable with respect to the IAF and justification status. The detection of such stability has practical applications, for instance as a termination criterion for argumentative dialogue agents: in the agent architecture for inquiry proposed in [16,17], stability detection prevents the agent from asking unnecessary questions. In addition, [15] 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.

In the case that the argument of interest is not stable in the given IAF, we know that the agent should collect more information. However, not all information that is currently unknown can influence the justification status of the argument of interest. A natural question would therefore be: which uncertainties should we resolve in order to reach a point 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 or negotiation process ensures that the questions that are asked contribute to reaching stability.

The problem of detecting stability has been studied for structured (ASPIC⁺) approaches to argumentation in [16,17,23]. The algorithms proposed in this line of research have been implemented in an inquiry system for the intake of online trade fraud that has been used by hundreds of users every day since its launch in September 2019 [16]. For abstract approaches to argumentation, the problem of detecting stability was introduced in [15] and the subsequent problem of detecting relevance in incomplete (abstract) argumentation frameworks was introduced in our earlier work in [18]. Given the high potential for applications of stability and relevance in inquiry and negotiation, it would be useful to have efficient algorithms for solving these problems in abstract approaches to argumentation as well. In this paper we take a first step in the development of such algorithms, by investigating in which complexity class the problems of detecting stability and relevance are situated: insights in the complexity of the problems establish the possible efficiency of any algorithm to solve them.

The contribution of this paper, which expands on [18], is the extensive study of the complexity of justification, stability and relevance in the context of IAFs. Specifically, we present precise complexity results for each of these three problems under grounded, complete, stable and preferred semantics.11 Table 1 provides an overview of all these results. We further provide full proofs and illustrative examples for all the complexity results of justification, stability and relevance.

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 of an argument. These results are used in Section 4 in our complexity analysis of the stability problem. We then introduce the relevance problem for IAFs in Section 5 and provide complexity results. Related work is discussed in Section 6; we conclude in Section 7.

2.Preliminaries

In this section, we recall the most important notions from abstract argumentation and the associated semantics [10], as well as incomplete argumentation frameworks and their completions [3,4,7,15]. We also provide a brief introduction to the polynomial hierarchy, which is required for our complexity study.

2.1.Argumentation frameworks and semantics

An argumentation framework (AF) ⟨A,R⟩, as introduced in [10], consists of a finite set A of arguments and a binary attack relation R⊆A×A on them, where (A,B)∈R indicates that argument A attacks argument B. In this paper, we evaluate arguments using the semantics of [10].

Definition 1

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 acceptable with 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 a 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.

Example 1.

Fig. 1 shows an example of an argumentation framework AF=⟨A,R⟩ where A={A,B,C,D,E} and R={(A,B),(B,C),(C,B),(D,C),(D,E),(E,D)}. The grounded extension of AF is {A}. This is also a complete extension. Additionally, there are two complete extensions that are also preferred and stable: {A,C,E} and {A,D}.

In order to decide if an argument should be accepted w.r.t. a given AF and semantics, one can choose between different strategies. We will refer to these as acceptability strategies, following [5, Definition 1]. Dependent on the strategy, the argument is accepted iff it occurs in one and/or all extensions.

Definition 2

Definition 2(Acceptability strategies).

Let AF=⟨A,R⟩ be an argumentation framework and σ some semantics in {GR,CP,PR,ST} and let A be some argument in A.

• A is sceptically accepted w.r.t. σ semantics iff A belongs to each σ-extension of AF;

• A is credulously accepted w.r.t. σ semantics iff A belongs to some σ-extension of AF; and

• A is sceptically-existent accepted w.r.t. σ semantics iff AF has at least one σ-extension and A belongs to each σ-extension of AF.

We refer to sceptical, credulous and sceptical-existent as acceptability strategies.

Note that the sceptical-existent acceptability strategy only differs from the sceptical strategy for st semantics: for gr, cp and pr semantics, each AF has at least one extension, while it is possible for an AF to have no st extension.

Example 2.

In the AF illustrated in Fig. 1, only the argument A is sceptically accepted w.r.t. cp semantics. The arguments C, D and E are all credulously accepted. Argument B is not accepted for any acceptability strategy.

Fig. 1.

An example of an argumentation framework. Arguments are depicted as circles, whereas attacks are depicted as arrows.

2.2.Incomplete argumentation frameworks

Incomplete argumentation frameworks (IAFs) [3,4,15] are an extension to AFs, initially proposed as partial AFs in [7]. 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 part of 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 3

Definition 3(Incomplete argumentation framework).

An incomplete argumentation framework is a tuple I=⟨A,A?,R,R?⟩, where A∩A?=∅, R∩R?=∅ 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.

Example 3

Example 3(IAF).

Fig. 2 shows an example of an incomplete argumentation framework I=⟨A,A?,R,R?⟩ where A={B,C,E}, A?={A,D}, R={(A,B),(B,C),(D,C),(D,E),(E,D)} and R?={(C,B)}. Arguments A and D are currently absent but may be added in the future. The attack from A to B is certainly present if A is present. Similarly, the attacks (D,C), (D,E) and (E,D) are certainly present if D is present. The attack from C to B, on the other hand, is uncertain: although the arguments B and C are certainly present, the attack itself is currently absent but may still be added.

Fig. 2.

An example of an incomplete argumentation framework. Certain arguments are depicted as circles with solid borders, whereas uncertain arguments are circles with dashed borders. Attacks are depicted as arrows, which have a solid line if they represent certain attacks and a dashed line if they represent uncertain attacks.

An incomplete argumentation framework can be completed by deciding for all uncertain arguments and attacks whether or not they are present, as defined below.

Definition 4

Definition 4(Completions).

Given an IAF I=⟨A,A?,R,R?⟩, a completion is any AF ⟨A′,R′⟩ that satisfies A⊆A′⊆A∪A? and R|A′⊆R′⊆(R∪R?)|A′ where the restriction R|A′ of an attack R to a set of arguments A′ is defined as R|A′={(A,B)∈R|A∈A′ and B∈A′}.

Example 4

Example 4(Completions).

The incomplete argumentation framework from our previous example has eight completions. These are illustrated in Fig. 3.

Fig. 3.

The eight completions of our incomplete argumentation framework.

Since completions are abstract argumentation frameworks, we can use the semantics from Section 2.1 to evaluate arguments in the completions of an incomplete argumentation framework. This leads to two ways of defining acceptance for incomplete argumentation frameworks, proposed in [3, pages 6-7]: necessary and possible acceptance. Informally, some argument is necessarily accepted if it is accepted in each completion, whereas the argument is possibly accepted if this holds for some completion. The definitions below make a distinction between the different acceptability strategies.

Fig. 4.

Visualisation of the cp extensions of each of the eight completions of I from Example 3, where the completion is repeated for each cp extension and argument that are present in that extension are coloured green.

Definition 5

Definition 5(Necessary acceptance).

Given an incomplete argumentation framework I=⟨A,A?,R,R?⟩, a certain argument A∈A, some semantics σ in {GR,CP,PR,ST} and some acceptability strategy α∈{sceptical,credulous,sceptical-existent}, A is necessarily α-σ accepted w.r.t. I iff A is α-σ accepted in each completion of I.

Definition 6

Definition 6(Possible acceptance).

Given an incomplete argumentation framework I=⟨A,A?,R,R?⟩, a certain argument A∈A, some semantics σ in {GR,CP,PR,ST} and an acceptability strategy α∈{sceptical,credulous,sceptical-existent}, A is possibly α-σ accepted w.r.t. I iff A is α-σ accepted in some completion of I.

Example 5

Example 5(Necessary and possible acceptance).

Fig. 4 displays the cp extensions of each of the eight completions of I from Example 4, where the completion is repeated for each cp extension. None of the certain arguments in I is necessarily sceptically accepted w.r.t. cp semantics, because no argument is in all extensions of all completions. Note that A, although it is present in all extensions of all completions of I in which it occurs, is not necessarily sceptically accepted w.r.t. cp semantics: A is not a certain argument in I. The only argument that is necessarily credulously accepted w.r.t. cp semantics is E. B is possibly sceptically accepted w.r.t. cp semantics, because the argument is in each extension of the completion AF7 (as well as AF8). C and E are possibly sceptically accepted w.r.t. cp semantics as well, thanks to their presence in the only extension of AF2. Finally, all certain arguments of I (B, C and E) are possibly credulously accepted w.r.t. cp semantics.

The definitions of necessary and possible acceptance are particularly interesting for our work, as they are strongly related to the notion of stability, to be defined formally in Section 4. Before we do so, we first explain the polynomial hierarchy in the next section.

2.3.The polynomial hierarchy

In this section, we give a brief introduction to the polynomial hierarchy – for a more detailed explanation, we refer to [14]. This is required for the complexity study presented in this paper as the problems we study are situated on various levels in the polynomial hierarchy.

The polynomial hierarchy [19] is a hierarchy of complexity classes defined using 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 a class X defined by resource bounds, XC 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. For example, problems in NP are decidable with a resource bound given by NP and an oracle for a problem in P, therefore NP=NPP.

Based on these notions, the sets Σkp and Πkp are defined as follows: Σ0p=Π0p=P, Σk+1p=NPΣkp and Πk+1p=CoNPΣkp. So problems in Σ2p are decidable with a resource bound given NP and an oracle for a problem in Σ1p=NP. The polynomial hierarchy (PH) is then defined as the union of these complexity classes: PH=⋃k=0∞Σkp=⋃k=0∞Πkp. Finally, note that the definition over classes in the polynomial hierarchy imply a subset relation, illustrated in Fig. 5. By this relation, for each i∈N, each problem in Σip is also in Σi+1p, as well as in Πi+1p.

A problem that is Σ2p-complete is Σ2-SAT [22]; in this paper we will use the CNF formulation that is also used in, e.g. [3,4]. An instance of Σ2-SAT would be (Φ,X,Y), where Φ is an input formula in CNF over the pairwise disjoint sets of propositional variables X and Y. Then the Σ2-SAT problem is to decide if there exists a truth value assignment τX to variables of X such that for each truth value assignment τY: Φ[τX,τY]=False, where Φ[τX,τY] is the truth value that Φ evaluates to when applying the assignment τX to X and τY to Y.

Fig. 5.

The relation between complexity classes in the polynomial hierarchy. The lines between classes denote a subset relationship: all problems in the class of the left side are also contained in the class on the right side.

3.Justification status

In this section, we define the notion of justification status and study the complexity of determining this status for a given argument. The justification status [6] is a notion of acceptance for arguments in abstract argumentation frameworks that is more fine-grained than only considering the presence or absence in extensions. Given an AF ⟨A,R⟩, an argument A and a semantics σ, A’s justification status can be determined by either considering all σ-extensions (sceptical and sceptical-existent) 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).

The justification statuses that we consider in this paper are {GR,CP,PR,ST}×{sceptical,credulous,sceptical-existent}×{IN,OUT,UNDEC}. In the remainder of this paper, we refer to in-, out or undec-justification in case the semantics and acceptability strategy is obvious or irrelevant.

We formulate the identification of justification status as a decision problem j-justification (where j∈{GR,CP,PR,ST}×{sceptical,credulous,sceptical-existent}×{IN,OUT,UNDEC}):

The remainder of this section provides proofs for complexity results related to justification problems. Whereas the complexity of in-justification has been studied before (as acceptance problems, see [8–11]), this is not the case for out- and undec-justification. This is unfortunate, as detecting out- and undec-justification has interesting applications as well: since arguments that are undec are “more acceptable” than arguments that are out, these justification statuses provide a more fine-grained notion of acceptability than the distinction between accepted and not accepted. In addition, more insight in the complexity of detecting these justification statuses could for example be helpful in developing fast algorithms. Furthermore, we will use the complexities of out- and undec-justification later for finding the complexities of out- and undec-stability (Section 4) and out- and undec-relevance (Section 5). We will therefore provide complexity proofs for these types of justification under gr, cp, st and pr semantics. Our strategy in proving these complexities is to relate them to the complexities of in-justification and using existing results from the complexity of acceptance problems. Short proofs will be given directly after the lemmas and propositions, whereas we provide sketches for longer proofs; the full proofs can be found in Appendix A. We start with a lemma for justification that shows that in-justification and out-justification are in the same complexity class:

Contrary to out-justification, undec-justification is not necessarily in the same complexity class as in-justification. However, under gr, cp and pr semantics, there is another relation, as we will show in Lemma 3.22 Before we can do so, we prove relations between credulous-in- and sceptical-undec-justification, as well as between credulous-undec- and sceptical-in-justification, in the following lemma. The transformations used in this lemma are illustrated in Fig. 6.

Fig. 6.

Illustration of the argumentation frameworks that are used in transformations between justification problem instances used for proving Lemma 2. The figure illustrates three argumentation frameworks: AF=⟨A,R⟩ (first column), AF′=⟨A∪{A′},R∪{(A,A′),(A′,A′)}⟩ (second column) and AF″=⟨A∪{A′,B,C},R∪{(A,B),(A,C),(B,C),(C,A′)}⟩ (third column). The dotted, rounded rectangles represent all arguments in A except A. Each of the argumentation frameworks is displayed three times, corresponding to different extensions of AF: the first row, where A is coloured yellow, represents extensions that do not contain A or any attacker of A (“A is undec”). The second row, where A is green and with boldface font, represents extensions containing A (“A is in”). Finally, the third row, where A is red and with italic font, represents extensions containing some attacker of A (“A is out”). The colours and typesetting refer to the justification statuses of arguments, where green and boldface font stands for in; yellow and regular font for undec and red and italic font for out.

Lemma 2 is used in the following lemma to show that credulous-in-justification and sceptical-undec-justification are in complementary complexity classes, as well as credulous-undec-justification and sceptical-in-justification, under gr, cp and pr semantics.

Using Lemma 3, we can now directly derive justification statuses for undec-justification under cp, gr and pr semantics in Propositions 1, 2 and 3.

For st semantics, the situation is different, since for each st extension S, each argument is either in S or attacked by some argument in S. In the remainder of this section, we give the complexity results of undec-justification for st semantics.

In addition, an argument can only be st-sceptical-undec in a given argumentation framework AF if AF does not have any st extension.

At this point, we have studied the complexity of the justification problem for GR, CP, PR and ST semantics, for sceptical and credulous (and sceptical-existent of st semantics) acceptance and labels in, out and undec. These results are summarised in Table 2. In the following sections, we will see that these definitions and complexity results can be used for defining and studying the complexity of the stability and relevance problems.

Table 2

Overview of all complexity results related to justification. If a reference is specified, this complexity result is trivial from an earlier result in the literature. New results are printed bold; we refer to the corresponding proposition by “P” and the proposition number. Full proofs for each of the propositions are presented in the appendix. The complexities for in- and out-justification are the same; this follows from Lemma 1

4.Stability

In this section, we will formally define stability and study its complexity. Stability can be seen as a dynamic variant of justification, defined on incomplete argumentation frameworks: whereas the notion of justification only takes certain arguments and attacks into account, the notion of stability also considers arguments and attacks for which their presence is still uncertain. Whereas justification status is defined on arguments in an abstract argumentation framework, stability status is defined on certain arguments in an incomplete argumentation framework. Informally, a certain argument is stable if its justification is the same in all completions of the IAF. In the definition below, we define j-stability based on j-justification, where j can be any justification status considered in the previous section: j∈{GR,CP,PR,ST}×{sceptical,credulous,sceptical-existent}×{IN,OUT,UNDEC}.

Example 7

Example 7(Stability).

We reconsider the incomplete argumentation framework I=⟨A,A?,R,R?⟩ from Example 3. The arguments in A are B, C and E. Figure 7 illustrates the complete in/out/undec-labellings of each of the completions (AF1,…,AF8) of I. For each of these eight AFs, each complete extension is represented by colouring the argument nodes: nodes corresponding to arguments in the extension are coloured green and with boldface font; arguments attacked by an argument in the extension are coloured red and with italic font; all other arguments are yellow and with regular font. Note that for each completion of I, there is at least one complete extension containing E. In other words: E is stable-cp-credulous-in. Similarly, for each completion of I, there is at least one preferred and stable extension containing E, so E is stable-pr-credulous-in and stable-st-credulous-in as well. Under grounded semantics, E is not stable-in, since there are completions (such as AF1) for which E is not in the grounded extension.

For each σ∈{GR,CP,PR,ST}, there is no argument that is stable-σ-sceptical-in, -out or -undec. In practice, this means that a sceptical reasoner interested in one of the arguments in A would require more information.

Fig. 7.

Visualisation of the complete in/out/undec-labellings of each of the eight unique completions of I, where the argumentation framework is repeated for each cp extension. Arguments that are in that extension are coloured green and with boldface font; argument attacked by some argument in that extension are red and with italic font; and all other arguments are yellow and with regular font.

Finally recall that stability is not defined for A and D, since they are in A? rather than A. So although the argument A is in each gr, cp, pr and st extension in each completion in which the argument exists, it is not stable-gr/cp/pr/st-sceptical/credulous-in because there are completions that do not contain A.33

Note that the notion of stability is strongly related to the notion of necessary acceptance, defined in Section 2. In fact, for any semantics σ, certain arguments are stable-σ-sceptical-in if and only if they are necessarily sceptically accepted (i.e. in each extension of each completion); similarly, certain arguments are stable-σ-credulous-in if and only if they are necessarily credulously accepted (i.e. in some extension of each completion). However, stability provides a more fine-grained notion of (non-)acceptance in IAFs than necessary acceptance. Using (out-)stability, it is, for example, also possible to express that, in any completion, some certain argument is attacked by an argument (not necessarily the same) in a σ-extension of that completion.

In the remainder of this section, we present our results on the complexity of the task of identifying a stability status. The following formulates this task as a decision problem.

Next, we give complexity results for variants of the stability problem. We start with relating in-stability to necessary (sceptical and credulous) acceptance, as defined in Definition 5 (which was adapted from [3]).

We continue with relating in- and out-stability. Similar to what we did for in- and out-justification in Lemma 1, we show that the complexity of in-stability is the same as the complexity of out-stability.

Using Lemma 5, we can show that for any given σ∈{GR,CP,PR,ST} and c∈{sceptical,credulous}, we can derive the complexity of σ-c-out-stability directly from the complexity of σ-c-in-stability. In the following lemma, we relate undec-stability for specific semantics with possible sceptical and credulous acceptance (Definition 6). Similar to Lemma 2, we prove this for gr, cp and pr semantics but not for st semantics: the relation does not hold for st semantics because arguments cannot be st-credulous-undec.

The results of Lemma 6 can be used to derive the complexity classes of undec-stability based on existing results for possible acceptance from [3] for cp, gr and pr semantics.

Finally, we turn to st semantics. Our strategy for proving these complexities is similar to our approach for the st-undec-justification complexity proofs in the previous section.

To conclude this section, we have studied the complexity of the stability problem for gr, cp, pr and st semantics, for sceptical and credulous (and sceptical-existent for st semantics) acceptance and labels in, out and undec. For an overview of the results, we refer to Table 3. In the following section, we consider the problem of identifying relevance.

Table 3

Overview of all complexity results related to stability. If a reference is specified, this complexity result is trivial from an earlier result in the literature. New results are printed bold; we refer to the corresponding proposition by “P” and the proposition number. Full proofs for each of the propositions are presented in Appendix B. The complexities for in- and out-stability are the same; this follows from Lemma 5

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

Fig. 8.

Illustration of the IAF I=⟨A,A?,R,R?⟩ from Example 3.

The example showed that being certain about the existence of the attack (C,B) does not contribute anything to the stability status of C in a situation where we already know that A is present and D is absent: both with and without (C,B), C is stable-gr-sceptical-in. In general, adding or removing an argument or attack is only relevant if there is a situation in which this argument or attack is really necessary to obtain stability. In order to define which uncertainties are relevant to be resolved for obtaining some stability status, we therefore need some notion of “partial” completions, in which only those uncertainties are resolved that are required for stability. A partial completion of an IAF I is an IAF I′ such that a (possibly empty) part of the uncertain elements of I is resolved in I′, while another (possibly empty) part of the uncertain elements is still uncertain.44 Next, we formally define such partial completions.

In order to be able to apply the semantics of [10], which are defined on AFs, to IAFs, we define the certain projection of an IAF. This is an AF consisting of only the IAF’s certain arguments and the attacks between them.

Example 9

Example 9(Partial completions and certain projections).

Returning to the IAF I=⟨A,A?,R,R?⟩, given in Example 3 and illustrated in Fig. 8, the following IAFs are some (but not all) examples of partial completions in part(I):

• I1=⟨A∪A?,∅,R∪R?,∅⟩: all uncertain arguments and attacks have become certain.

• I2=⟨A,∅,{(B,C)},∅⟩: all uncertain arguments and attacks are removed, as well as all attacks that are not in the restriction of R to A.

• I3=⟨A∪{A},A?,R,R?⟩: the argument A is moved from the uncertain to the certain part. The argument D and the attack (C,B) are still uncertain.

Fig. 9.

Three partial completions of our incomplete argumentation framework and their certain projections.

The partial completions I1, I2 and I3 are illustrated on the left side of Fig. 9. The certain projection of I1 is ⟨A∪A?,R∪R?⟩. For I2, the certain projection is ⟨A,{(B,C)}⟩. Finally, cert(I3)=⟨{A,B,C,E},{(A,B),(B,C))}⟩. These AFs are illustrated on the right side of Fig. 9.

Before proceeding to a formal definition of relevance that matches the intuitions in the example above, we define the notion of minimal stable partial completions. In this definition, j refers to the justification status: j∈{GR,CP,PR,ST}×{sceptical,credulous,sceptical-existent}×{IN,OUT,UNDEC}.

Intuitively, the minimal stable-j partial completion for A is a partial completion in which A is stable-j, while A would not be stable-j in any partial completion with more uncertain elements.

Using the notion of minimal stable-j partial completions, we can now define j-relevance.

In other words, addition of an uncertain element U is j-relevant if a minimal stable-j partial completion can be reached by moving U from the uncertain to the certain 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 partial completion.

Fig. 10.

Partial completion I4, which is the only minimal stable-gr-sceptical-in partial completion for C w.r.t. I where I=⟨{B,C,E},{A,E},R,R?⟩ and I4=⟨{A,B,C,E},∅,{(A,B),(B,C)},R?⟩.

Like for justification and stability status, we formulate the identification of j-relevance as a decision problem:

In the remainder of this section, we study the complexity of relevance for complete, grounded, preferred and stable semantics. This work builds on initial research in [18], where we proved the complexity of in-relevance under grounded semantics. In order to prove complexity of j-relevance for each justification status j, we first give proofs for the upper bounds, that is: the membership in a given complexity class, in Section 5.1. Subsequently, we provide lower bounds, that is: hardness results, for relevance under grounded, complete and preferred semantics in Section 5.2. Finally, we prove the remaining hardness results for stable semantics in Section 5.3.