Analyzing the impact of bounded degree constraints on computational complexity of argumentation frameworks

Example 4

Let A F = ⟨ A , R ⟩ be the argumentation framework described by Figure 1. Within this framework, the argument a 1 is skeptically accepted under preferred extensions, implying that it is also credulously accepted under these extensions. In contrast, arguments a 3 and a 4 are credulously accepted under preferred extensions but are not skeptically accepted under these extensions.

Now, we consider the argumentation frameworks defined by the property Δ ( p , q ) as follows.

Definition 1

Let A F = ⟨ A , R ⟩ be an argumentation framework. A F satisfies the property Δ ( p , q ) if

∀ x ∈ A | { y ∈ A | ( y , x ) ∈ R } | ≤ p and | { y ∈ A | ( x , y ) ∈ R } | ≤ q .

Note that p and q are bounded such that 0 ≤ p , q ≤ | A | , with | A | is the size of A .

To illustrate Definition 1, consider the argumentation frameworks depicted in Figure 2. The left part of the figure (Figure 2(a)) shows an argumentation framework where each argument attacks at most two arguments and is attacked by at most two arguments, satisfying the property Δ ( 2 , 2 ) . The right part of Figure 2(b) shows an argumentation framework where argument a 1 attacks more than two arguments, thus not satisfying the property Δ ( 2 , 2 ) .

OPEN IN VIEWER

Figure 2.

Example of an argumentation framework that satisfies the property Δ ( 2 , 2 ) and one that does not. (a) Satisfies Δ ( 2 , 2 ) . (b) Does not satisfy Δ ( 2 , 2 ) .

Given an argumentation framework A F = ⟨ A , R ⟩ that satisfies the property Δ ( 2 , 2 ) , Dunne ¹⁵ has shown the following results.

Theorem 5

Let A F = ⟨ A , R ⟩ be an argumentation framework. If A F satisfies the property Δ ( 2 , 2 ) then: (1)

CredA is NP-complete.

(2)

SkepA is ∏ 2 p -complete.

According to Dunne, ¹⁵ the problems CredA and SkepA are hard to solve even when the values of “ p ” and “ q ” are restricted to 2 , that is, p = q = 2 . This raises the question: what is the complexity of these problems when “ p ” or “ q ” is limited to 1 ? In the subsequent analysis, we show that when “ p ” or “ q ” is restricted to 1 , the problems CredA and SkepA become solvable efficiently.

Let us start by restricting p to 1, implying that the argumentation framework A F satisfies the property Δ ( 1 , q ) . The framework depicted in Figure 3 satisfies the property Δ ( 1 , q ) .

OPEN IN VIEWER

Figure 3.

Example of an argumentation framework satisfying the property Δ ( 1 , q ) . The associated implication system to this framework is Σ = { { a 1 } → a 4 , { a 1 } → a 3 , { a 2 } → a 5 , { a 2 } → a 6 } , which is unit. This framework has two preferred extensions, namely { a 1 , a 3 , a 4 } and { a 2 , a 5 , a 6 } . All arguments are credulously accepted in this framework, but none are skeptically accepted.

In this case, the associated implicational system Σ = { y − → z ∣ ( y , z ) ∈ R and ( z , y ) ∉ R } , to A F is unit. In Elaroussi et al., ³⁷ particularly in the proof of Theorem 3, the authors propose a polynomial time algorithm to construct an argumentation framework A F ′ = ⟨ A , R ′ ⟩ such that P R E F ( A F ) = N A I V ( A F ′ ) . This result leads to the following theorem.

Theorem 6

Let A F = ⟨ A , R ⟩ be an argumentation framework satisfying the property Δ ( 1 , q ) . Then, there exists a polynomial time algorithm to construct an argumentation framework A F ′ = ⟨ A , R ′ ⟩ such that P R E F ( A F ) = N A I V ( A F ′ ) .

From this, we state the following result.

Theorem 7

Let A F = ⟨ A , R ⟩ be an argumentation framework. If A F satisfies the property Δ ( 1 , q ) , then: (1)

CredA can be solved in polynomial time.

(2)

SkepA can be solved in polynomial time.

Proof.

Given an argumentation framework A F = ⟨ A , R ⟩ that satisfies the property Δ ( 1 , q ) . According to Theorem 6, we can construct in polynomial time an argumentation framework A F ′ = ⟨ A , R ′ ⟩ such that P R E F ( A F ) = N A I V ( A F ′ ) . Through the transformation to A F ′ , it becomes evident that an argument x belongs to a preferred extension (credulously accepted) in A F if and only if it is not self-attacking in A F ′ . Additionally, x belongs to all preferred extensions (skeptically accepted) in A F if and only if it is not self-attacking in A F ′ and none of its neighbors is credulously accepted, that is, they are self-attacking. We deduce the proof.

Now, let us restrict “ q ” to 1 , which means that the argumentation framework A F satisfies the property Δ ( p , 1 ) . The framework depicted in Figure 4 satisfies the property Δ ( p , 1 ) .

OPEN IN VIEWER

Figure 4.

Example of an argumentation framework satisfying the property Δ ( p , 1 ) . The associated implication system to this framework is Σ = { { a 5 , a 6 } → a 2 , ∅ → a 2 , ∅ → a 3 } , which is not unit. This framework has a unique preferred extension, namely { a 1 , a 4 , a 5 , a 6 } . Only the arguments a 1 , a 4 , a 5 , and a 6 are credulously accepted, and they are also skeptically accepted.

Prior to delving into our results, let us start with the following observation.

Lemma 1

Let A F = ⟨ A , R ⟩ be an argumentation framework that satisfies the property Δ ( p , 1 ) . If A F is an isolated cycle of even length, then A F has exactly two preferred extensions.

Proof.

Given that A F forms an even length cycle, we can arrange its arguments sequentially as C = x 1 , x 2 , … , x 2 k , where 2 k is the size of the set of arguments A . In this sequence, each argument attacks the next one, and x 2 k attacks x 1 . Also, due to the fact that A F satisfies the property Δ ( p , 1 ) , each argument attacks at most one other argument. Consequently, there are no attacks between arguments outside of this sequential order C . Now, let us consider two subsets of arguments:

S 1 = { x 2 i − 1 ∣ 1 ≤ i ≤ k } , S 2 = { x 2 i ∣ 1 ≤ i ≤ k } .

The union of S 1 and S 2 covers all arguments in A F .

We will show that S 1 and S 2 are two preferred extensions of A F . Since there are no attacks between arguments outside of the sequential order C , there are no attacks within S 1 or within S 2 . Moreover, these sets are maximally conflict-free, as adding any argument from the other set would unavoidably cause conflicts. Furthermore, each argument in S 1 and S 2 defends the others within its set against external attacks. In S 1 , for 3 ≤ i ≤ 2 k − 1 , each x i ∈ S 1 is only attacked by x i − 1 ; however, it is defended by x i − 2 ∈ S 1 , which attacks x i − 1 . Moreover, x 1 ∈ S 1 is only attacked by x 2 k ; however, it is defended by x 2 k − 1 ∈ S 1 . Similarly, in S 2 , for 4 ≤ i ≤ 2 k , each x i ∈ S 2 is only attacked by x i − 1 ; however, it is defended by x i − 2 ∈ S 2 against x i − 1 . Additionally, x 2 ∈ S 2 is only attacked by x 1 ; however, it is defended by x 2 k ∈ S 2 . Consequently, both S 1 and S 2 meet the criteria for preferred extensions.

To show that S 1 and S 2 are the only preferred extensions, assume there exists another preferred extension S such that S ≠ S 1 and S ≠ S 2 . Thus, S must contain both an argument x 2 i * − 1 ∈ S 1 and x 2 j * ∈ S 2 with i * , j * ∈ { 1 , … , k } . Since x 2 i * − 1 ∈ S , then S to be self-defending, S 1 must be a subset of it. Thus, S is not conflict-free, as S would contain both x 2 j * − 1 and x 2 j * , with x 2 j * − 1 is a direct attacker of x 2 j * . This contradicts the assumption that S is conflict-free. Therefore, any other subset S containing arguments from both S 1 and S 2 cannot be a preferred extension. Consequently, S 1 and S 2 are the unique preferred extensions of A F .

Let A F = ⟨ A , R ⟩ be an argumentation framework, and let x ∈ A be an argument in A F . We define A x as the set of all arguments that are connected to x in A F . Formally, A x = { y ∣ y is connected to x in A F } . We recall that an argument y is said to be connected to x in A F if there exists a path from y to x . Let A F x = ⟨ A x , R x ⟩ be a sub-argumentation framework of A F induced by the set A x , where R x = R ∩ ( A x × A x ) . Since R x ⊆ R , if A F satisfies the property Δ ( p , 1 ) , then A F x also satisfies the property Δ ( p , 1 ) . We state the following results.

Lemma 2

Let A F = ⟨ A , R ⟩ be an argumentation framework that satisfies the property Δ ( p , 1 ) , and let x ∈ A . Define A x = { y ∣ y is connected to x in A F } and let A F x = ⟨ A x , R x ⟩ be the sub-argumentation framework of A F induced by A x . Then A F x has at most one cycle. Moreover, if such a cycle exists, then x belongs to it.

Proof.

The proof proceeds in two steps:

First, we show that every argument in A F belongs to at most one cycle. Let y ∈ A and suppose C is a cycle in A F that contains y . In a cycle, every argument attacks at least one other argument within the same cycle. Since A F satisfies property Δ ( p , 1 ) , then y cannot attack another argument outside of C . Therefore, each argument in A F belongs to at most one cycle.

Second, we show that if C is a cycle in A F x , then x belongs to C . Suppose, for contradiction, that x does not belong to C . By definition, each argument in A x is connected to x in A F . Consequently, there exists an argument z in C that attacks an argument outside of C , since x is not in C . This contradicts the fact that A F satisfies the property Δ ( p , 1 ) , which states that each argument can attack at most one other argument. Therefore, x must belong to C . We deduce the proof.

Lemma 3

Let A F = ⟨ A , R ⟩ be an argumentation framework that satisfies the property Δ ( p , 1 ) , and let x ∈ A . Define A x = { y ∣ y is connected to x in A F } and let A F x = ⟨ A x , R x ⟩ be the sub-argumentation framework of A F induced by A x . Then, either A x + ∩ ( A ∖ A x ) = ∅ or A F x is acyclic.

Proof.

By the construction of A F x , each argument y ∈ ( A x ∖ { x } ) is connected to x . Thus, each argument y ∈ ( A x ∖ { x } ) attacks at least one argument within A F x . Given that A F satisfies the property Δ ( p , 1 ) , it follows that A F x also satisfies the property Δ ( p , 1 ) . Therefore, no argument in A x except x can attack arguments outside of A x . Formally, ( A x ∖ { x } ) + ∩ ( A ∖ A x ) = ∅ . Now, we show that A F x is acyclic if x + ∩ ( A ∖ A x ) ≠ ∅ . According to Lemma 2, A F x can have at most one cycle that includes x . Since x + ∩ ( A ∖ A x ) ≠ ∅ and A F x satisfies the property Δ ( p , 1 ) , it follows that x + ∩ A x = ∅ . As a result, A F x is acyclic. Hence, we have shown that either A x + ∩ ( A ∖ A x ) = ∅ or A F x is acyclic.

Lemma 4

Let A F = ⟨ A , R ⟩ be an argumentation framework, and let x ∈ A . Define A x = { y ∣ y is connected to x in A F } and let A F x = ⟨ A x , R x ⟩ be a sub-argumentation framework of A F induced by A x . If F is an admissible set of A F x , then F is an admissible set of A F .

Proof.

Let F be an admissible set of A F x . By definition, R x = R ∩ ( A x × A x ) , thus any attack between arguments of A x in R is in R x . Hence, F is conflict-free in A F . Moreover, ( A x ∩ F − ) ⊆ F + in A F . By the construction of A F x , no argument in A ∖ A x is connected to x and all arguments in A x are connected to x . Thus, A x − ∖ A x = ∅ . Hence, ( A ∩ F − ) ⊆ F + , which means that F is self-defending in A F . As a result, F is an admissible set in A F .

Lemma 5

Let A F = ⟨ A , R ⟩ be an argumentation framework, and let x ∈ A . Define A x = { y ∣ y is connected to x in A F } and let A F x = ⟨ A x , R x ⟩ be the sub-argumentation framework of A F induced by A x . If F is a preferred extension of A F , then F ∩ A x is a preferred extension of A F x .

Proof.

Let F be a preferred extension of A F . By definition, F is conflict-free and self-defending in A F . This means there are no arguments y , z ∈ F such that ( y , z ) ∈ R . Since R x ⊆ R , there can be no arguments y , z ∈ F ∩ A x such that ( y , z ) ∈ R x . Therefore, F ∩ A x is conflict-free in A F x . Next, we need to show that F ∩ A x is self-defending in A F x . For the sake of contradiction, suppose the contrary. Then, there exists an argument y ∈ F ∩ A x and an argument z ∈ A x such that ( z , y ) ∈ R x and z ∉ ( F ∩ A x ) + . Since F is self-defending in A F , there exists t ∈ F such that ( t , z ) ∈ R . Because z ∈ A x and t attacks z , t must be connected to x , and therefore, t ∈ A x . Thus, t ∈ F ∩ A x , contradicting the assumption that z ∉ ( F ∩ A x ) + . Therefore, F ∩ A x is self-defending in A F x . Since F ∩ A x is conflict-free and self-defending, it is an admissible set of A F x .

To show that F ∩ A x is a preferred extension of A F x , suppose for contradiction that there is a preferred extension T in A F x such that F ∩ A x ⊊ T . By Lemma 4, T is also an admissible set in A F . Let S = F ∖ A x . We will show that T ∪ S is an admissible set of A F . First, we show that T ∪ S is self-defending in A F . Since S − ⊆ F + ⊆ T + and T is an admissible set in A F , T ∪ S is self-defending in A F . Next, we show that T ∪ S is conflict-free in A F . For the sake of contradiction, suppose the contrary. Since S ⊆ F and F is conflict-free in A F , S is conflict-free in A F . We have T is conflict-free in A F x . Thus, there exist y ∈ T and z ∈ S such that ( z , y ) ∈ R or ( y , z ) ∈ R . Since A x − ∩ ( A ∖ A x ) = ∅ and T ⊆ A x , it follows that ( y , z ) ∈ R . By Lemma 3, y = x and A F x is acyclic. According to Theorem 2, T is the only preferred extension of A F x . Since A x − ∩ ( A ∖ A x ) = ∅ and S − ∩ T + = ∅ , S cannot be a subset of any admissible set in A F . We have S ⊆ F , which contradicts the fact that F is an admissible set in A F . Hence, T ∪ S is an admissible set in A F . We have F ⊊ T ∪ S and T ∪ S is an admissible set in A F . This contradicts the maximality of F as a preferred extension of A F . Therefore, F ∩ A x is a preferred extension of A F x .

From the previous lemmas, in the following result, we show that the argument x is credulously (respectively, skeptically) accepted in A F if and only if it is credulously (respectively, skeptically) accepted in A F x .

Theorem 8

Let A F = ⟨ A , R ⟩ be an argumentation framework, and let x ∈ A . Define A x = { y ∣ y is connected to x in A F } and let A F x = ⟨ A x , R x ⟩ be the sub-argumentation framework of A F induced by A x . Then, x is credulously (respectively, skeptically) accepted in A F if and only if it is credulously (respectively, skeptically) accepted in A F x .

Proof.

We provide the proof for skeptical acceptance only. For credulous acceptance, the “if” part follows directly from Lemma 5 and the “only if” part follows directly from Lemma 4.

( ⇒ ) We proceed by contrapositive. Suppose that x is not skeptically accepted in A F x . This means there exists a preferred extension F in A F x such that x ∉ F . By Lemma 4, F is an admissible set in A F . Therefore, there exists a preferred extension T of A F such that F ⊆ T . Let us show that x ∉ T . Suppose, for the sake of contradiction, that x ∈ T . By Lemma 5, T ∩ A x is a preferred extension of A F x . Since x ∈ T ∩ A x and x ∉ F , it follows that F ⊊ T ∩ A x , which contradicts the fact that F is a preferred extension of A F x . Therefore, x ∉ T , which means that x is not skeptically accepted in A F .

( ⇐ ) We proceed by contradiction. Suppose that x is skeptically accepted in A F x but not in A F . This means there exists a preferred extension F in A F such that x ∉ F . By Lemma 5, F ∩ A x is a preferred extension in A F x . Since x ∈ A x and x ∉ F , it follows that x ∉ F ∩ A x . This contradicts the assumption that x is skeptically accepted in A F x , i.e., x should be in every preferred extension of A F x .

Hence, x is skeptically accepted in A F if and only if it is skeptically accepted in A F x .

According to Theorem 8, the argument x is credulously (respectively, skeptically) accepted in A F if and only if it is credulously (respectively, skeptically) accepted in the sub-argumentation framework A F x . In what follows, we will show that if A F satisfies the property Δ ( p , 1 ) , then checking the skeptical and credulous acceptance of x in A F x can be done in polynomial time. To begin, the following lemma shows that A F x has at most two preferred extensions.

Lemma 6

Let A F = ⟨ A , R ⟩ be an argumentation framework that satisfies the property Δ ( p , 1 ) , and let x ∈ A . Define A x = { y ∣ y is connected to x in A F } and let A F x = ⟨ A x , R x ⟩ be the sub-argumentation framework of A F induced by A x . Then A F x has at most two preferred extensions, which can be computed in polynomial time.

Proof.

If A F x does not contain an even length cycle, it has a unique preferred extension according to Theorem 3. Now, suppose A F x contains an even length cycle. As shown in Lemma 1, A F x has exactly one cycle, which we denote as C . We split A F x into two sub-argumentation frameworks: A F 1 [ A 1 = A x ∖ A x ( C ) ] , containing all arguments except those in C , and A F 2 [ A x ( C ) ] , containing only the arguments in C . As a result, A F 1 is acyclic and has only one preferred extension according to Theorem 3, which is also a stable extension according to Theorem 2. Let F be the unique stable extension of A F 1 . The framework A F 2 is an even length cycle and by Lemma 1, A F 2 has exactly two preferred extensions, denoted S 1 and S 2 . Since A F x satisfies the property Δ ( p , 1 ) , C does not have outgoing attacks, that is, ( A x ( C ) ) + ∖ A x ( C ) = ∅ . Next, we distinguish two cases regarding the intersection F + ∩ A x ( C ) : (1)

If F + ∩ A x ( C ) = ∅ , then F ∪ S 1 and F ∪ S 2 are conflict-free. Moreover, since F is a stable extension, then ( A 1 ∖ F ) ⊆ F + . As a result, F ∪ S 1 and F ∪ S 2 are the only preferred extensions of A F x .

(2)

If F + ∩ A x ( C ) ≠ ∅ , we will show that that A F x has a unique preferred extension. For the sake of contradiction, assume that two preferred extensions of A F x exist: F 1 and F 2 . Then, there exist two arguments y ∈ F 1 and z ∈ F 2 such that ( y , z ) ∈ R x or ( z , y ) ∈ R x . Without loss of generality, assume that ( y , z ) ∈ R x . Since A F 1 has only one preferred extension, then y and z must be in C . Let P = t , x 1 , … , y , z be a shortest path from t ∈ F to z . Such a path must exist because we have assumed that F + ∩ A x ( C ) ≠ ∅ . Since ( A x ( C ) ) + ∖ A x ( C ) = ∅ , x 1 cannot belong to any preferred extensions in A F x . We have P is a short path, so ( A x ( P ) ∖ t ) ⊆ A x ( C ) and ( A x ( P ) ∖ x 1 ) ∩ F + = ∅ . Then, if P is odd-length, z cannot belong to any preferred extensions in A F x . If P is even length, y cannot belong to any preferred extensions in A F x . Thus, either y or z cannot belong to any preferred extensions in A F x , leading to a contradiction.

Therefore, A F x has at most two preferred extensions.

Finally, let us show that computing the preferred extensions of A F x can be done in polynomial time. For the acyclic sub-argumentation framework A F 1 , computing its unique preferred extension is feasible in polynomial time (see Theorem 4). Regarding A F 2 , which comprises arguments uniquely within the even length cycle C , Lemma 1 shows that A F 2 has exactly two preferred extensions. By partitioning A x ( C ) into subsets S 1 and S 2 , covering odd and even positioned arguments, respectively, we obtain the two preferred extensions of A F 2 . To compute the preferred extensions for A F x , we consider two scenarios. If F does not intersect with the arguments in C , that is, F + ∩ A x ( C ) = ∅ , then we combine F with S 1 and S 2 to form F ∪ S 1 and F ∪ S 2 , the two unique preferred extensions of A F 2 . However, if F accepts arguments from C , indicating F + ∩ A x ( C ) ≠ ∅ , A F x has a unique preferred extension. Nonetheless, computing this extension remains viable in polynomial time. We start with F , the unique preferred extension of A F 1 , then iteratively add arguments from C accepted by F until saturation. This iterative process ensures efficient computation of the preferred extension of A F x , considering the size of A F x .

Given an argumentation framework A F = ⟨ A , R ⟩ that satisfies the property Δ ( p , 1 ) and an argument x ∈ A , we want to check whether x is credulously or skeptically accepted in A F . Let A F x = ⟨ A x , R x ⟩ be a sub-argumentation framework of A F induced by the set A x (the set of arguments connected to x ). The construction of A F x can be done in polynomial time. According to Theorem 8, the argument x is credulously (respectively, skeptically) accepted in A F if and only if it is credulously (respectively, skeptically) accepted in A F x . Moreover, Lemma 6 shows that A F x has at most two preferred extensions, which can be computed in polynomial time. Therefore, we deduce the following result.

Theorem 9

Let A F = ⟨ A , R ⟩ be an argumentation framework. If A F satisfies the property Δ ( p , 1 ) , then: (1)

CredA can be solved in polynomial time.

(2)

SkepA can be solved in polynomial time.

As a result, we conclude that the computational complexity of both problems CredA and SkepA is influenced by the constraints on in-degree and out-degree. When the argumentation framework satisfies the property Δ ( 2 , 2 ) , both problems are hard to solve, as shown by Dunne. ¹⁵ Conversely, when the argumentation framework satisfies the property Δ ( 1 , q ) or Δ ( p , 1 ) , it becomes solvable in polynomial time, as shown in Theorems 7 and 9, respectively. In the following sections, we delve deeper into how the bounded degree of an argumentation framework influences the complexity of the problems CredA and SkepA by considering additional constraints.

3.1. Deeper analysis of bounded degree classes of argumentation frameworks with extended parameters

To gain a deeper understanding of how the bounded degree of an argumentation framework A F affects the complexity of the problems CredA and SkepA, we will further investigate specific quantities in this section. We will focus on exploring the following quantities:

(1)

“ a ” represents the maximum number of attackers that any argument x can have in A F among all those that are not attacked by x in A F ;

(2)

“ b ” denotes the maximum number of arguments that any argument x attacks in A F among all those that do not attack x in A F ; and

(3)

“ c ” indicates the maximum number of arguments that any argument x attacks in A F among those that attack x in A F .

By examining these quantities, we aim to gain insights into their impact on the complexity of the CredA and SkepA problems.

Formally, an argumentation framework is defined by the property δ ( a , b , c ) as follows.

Definition 2

Let A F = ⟨ A , R ⟩ be an argumentation framework. A F satisfies the property δ ( a , b , c ) if

∀ x ∈ A | { y ∈ A | ( y , x ) ∈ R and ( x , y ) ∉ R } | ≤ a , | { y ∈ A | ( x , y ) ∈ R and ( y , x ) ∉ R } | ≤ b , and | { y ∈ A | ( x , y ) ∈ R and ( y , x ) ∈ R } | ≤ c .

Note that a , b , and c are bounded such that 0 ≤ a , b , c ≤ | A | , with | A | is the size of A .

In order to highlight the differences between the property Δ ( p , q ) (Definition 1) and the property δ ( a , b , c ) (Definition 2), we present Figure 5. All argumentation frameworks depicted in Figure 5 satisfy the property Δ ( 2 , 2 ) . The property δ ( a , b , c ) distinguishes between symmetric and non-symmetric attacks, unlike the property Δ ( p , q ) . From left to right: the argumentation framework depicted in Figure 5(a) satisfies the property δ ( 1 , 1 , 1 ) ; the argumentation framework depicted in Figure 5(b) satisfies the property δ ( 0 , 0 , 2 ) ; the argumentation framework depicted in Figure 5(c) satisfies the property δ ( 2 , 2 , 0 ) .

OPEN IN VIEWER

Figure 5.

Argumentation frameworks highlighting the differences between the property Δ ( p , q ) and the property δ ( a , b , c ) .

Let us start with the existing results in the literature. According to Definition 2, an argumentation framework satisfies the property δ ( 0 , 0 , c ) if and only if it is a symmetric argumentation framework. As shown by Coste-Marquis et al., ²⁵ for a symmetric argumentation framework, both the CredA and SkepA problems can be solved in polynomial time. We have the following result.

Theorem 10

Let A F = ⟨ A , R ⟩ be an argumentation framework. If A F satisfies the property δ ( 0 , 0 , c ) , then: (1)

CredA can be solved in polynomial time.

(2)

SkepA can be solved in polynomial time.

In what follows, we analyze the implications of restricting a , b , and c to 1 . Surprisingly, we find that, contrary to expectations, the computational complexity of CredA persists even under these restrictions.

Let us start with the following result.

Theorem 11

Let A F = ⟨ A , R ⟩ be an argumentation framework. If A F satisfies the property δ ( 1 , 1 , c ) then CredA is an NP-complete problem.

Proof.

The proof is a reduction from 3-SAT. In 3-SAT, we are given a Boolean expression in conjunctive normal form.

ϕ = ⋀ i = 1 m C i = ⋀ i = 1 m ( p i , 1 ∨ p i , 2 ∨ p i , 3 ) .

Note that ϕ is the conjunction of m clauses, where each clause is the disjunction of 3 literals. This particular structure is known as 3-CNF in the literature. A literal p i , j represents either a Boolean variable u k or its negation ¬ u k . ϕ is satisfiable if the u k ’s can be assigned Boolean values so that ϕ is true. The 3-SAT problem is to determine whether ϕ is satisfiable. The complexity of a 3-SAT problem is known to be NP-complete. ³⁸ From a given Boolean expression ϕ , we construct an argumentation framework A F = ⟨ A , R ⟩ . The set of arguments A consists of three source arguments t 1 , t 2 , and t 3 , a sink argument s , an argument y , and two arguments x i , j and y i , j for each literal p i , j in ϕ . Note that ( t 1 ∨ t 2 ∨ t 3 ) is considered as the first clause of ϕ , and s as the last clause of ϕ . Formally, A F = ⟨ A , R ⟩ defined as follows:

A = { t 1 , t 2 , t 3 , s , y } ∪ { x i , j , y i , j ∣ 1 ≤ i ≤ m and 1 ≤ j ≤ 3 } ; R = { ( t j , y 1 , j ) | 1 ≤ j ≤ 3 } ∪ { ( y i , j , x i , j ) | 1 ≤ i ≤ m and 1 ≤ j ≤ 3 } ∪ { ( x i , j , y i + 1 , k ) , ( y i + 1 , k , x i , j ) | 1 ≤ i ≤ m − 1 and 1 ≤ j , k ≤ 3 } ∪ { ( x m , j , y ) , ( y , x m , j ) | 1 ≤ j ≤ 3 } ∪ { ( y , s ) } ∪ { ( x i , j , x k , l ) , ( x k , l , x i , j ) ∣ p i , j = ¬ p k , l } .

An illustration of this construction is given in Figure 6. OPEN IN VIEWER

Figure 6.

Argumentation framework constructed from the Boolean expression in conjunctive normal form C = ( p 1 , 1 ∨ p 1 , 2 ∨ p 1 , 3 ) ∧ ( p 2 , 1 ∨ p 2 , 2 ∨ p 2 , 3 ) with p 2 , 1 = ¬ p 1 , 1 .

The construction of A F is done in polynomial time in the size of ϕ . Moreover, each argument x in this framework possesses, at most, one argument that attacks “ x ” without being countered by “ x ,” as well as at most one argument attacked by “ x ” that does not attack “ x .” Consequently, the framework A F satisfies the property δ ( 1 , 1 , c ) . We will now show that this statement: there exists an admissible set F in A F includes the sink argument s if and only if ϕ is satisfiable.

Let us first show the “if” part of the statement. Suppose that there exists an admissible set F in A F such that s ∈ F . By the construction of A F , we have ( y , s ) ∈ R , and y − ∖ { x m , 1 , x m , 2 , x m , 3 } = ∅ . Since s is in F and F is a self-defending set, then it holds that F ∩ { x m , 1 , x m , 2 , x m , 3 } ≠ ∅ . As a result, at least one argument among those corresponding to the literals in the last clause of ϕ is in F . Furthermore, for each argument x i , j ∈ A , there exists an argument y i , j ∈ A such that ( y i , j , x i , j ) ∈ R and y i , j − ∖ { x i − 1 , 1 , x i − 1 , 2 , x i − 1 , 3 } = ∅ . Therefore, as F is self-defending then F ∩ { x i − 1 , 1 , x i − 1 , 2 , x i − 1 , 3 } ≠ ∅ for all 2 ≤ i ≤ m . This ensures that for each clause of ϕ , there exists in F an argument among those corresponding to the literals of this clause. As F is conflict-free by definition, then the arguments corresponding to a variable and its negation cannot both belong to F . Therefore, by selecting all literals p i , j for which there exists a x i , j ∈ F to be true, the entire expression ϕ is evaluated as true.

Now, let us show the “only if” part of the statement. Suppose that the Boolean expression ϕ is satisfiable, meaning that there exists an assignment of Boolean values to the variables such that ϕ is true. Based on this assignment, we can select the corresponding arguments in A F for the literals that are true and add the sink argument s and at least one of the source arguments t 1 , t 2 , or t 3 to construct a subset of A denoted as F . Since ϕ is satisfiable, then at least one literal in each clause is true. Therefore, for all 1 ≤ i ≤ m it holds that F ∩ { x i , 1 , x i , 2 , x i , 3 } ≠ ∅ , implying that y ∈ F + and y i , j ∈ F + for all 1 ≤ i ≤ m and 1 ≤ j ≤ 3 . Furthermore, the assignment ensures that only one of a variable and its negation is true. Thus, F does not contain both a variable and its negation for any clause, making it conflict-free. Therefore, F satisfies the properties required for an admissible set in A F , and since s is in F , the existence of an admissible set including s in A F is proved. This concludes the proof.

Remark 1

The idea of the proof of Theorem 11 comes from the proof of Lemma 2 in Gabow et al. ³⁹

Throughout the rest of this section, we will work with the argumentation framework obtained from 3 -CNF through the procedure mentioned previously in the proof of Theorem 11. For the sake of brevity and clarity, we refer to this framework as A F S A T .

We aim to transform the argumentation framework A F S A T into a new framework A F that satisfies the δ ( 1 , 1 , 1 ) property. This transformation involves reducing the number of symmetric attacks to at most one per argument. Additionally, we want to ensure that the existence of an admissible set F containing the argument “ s ” in A F S A T is equivalent to the existence of an admissible set T in A F , which also contains the argument “ s .”

To achieve this goal, we start by minimizing symmetric attacks between the arguments x i , j and y i + 1 , j for 1 ≤ i ≤ m − 1 and 1 ≤ j ≤ 3 , ensuring each x i , j has at most one symmetric attack with an argument from the set { y i + 1 , 1 , y i + 1 , 2 , y i + 1 , 3 } . In A F S A T , for all 1 ≤ i ≤ m − 1 and 1 ≤ j ≤ 3 , we have x i + 1 , j − ∖ x i + 1 , j + = { y i + 1 , j } and y i + 1 , j − = { x i , 1 , x i , 2 , x i , 3 } . Thus, for each self-defending set S in A F S A T , if x i + 1 , j ∈ S , then S ∩ { x i , 1 , x i , 2 , x i , 3 } ≠ ∅ (referred to as Condition A). To preserve the existence of an admissible set containing “ s ” in the framework after the transformation, if and only if an admissible set that includes “ s ” exists in A F S A T , it is essential to maintain Condition A.

To preserve Condition A in the transformation, for each i ∈ { 1 , … , m } , we introduce new arguments a i , 1 , a i , 2 , b i , 1 , and b i , 2 . We replace the existing attacks between x i , j and y i + 1 , j with the following attacks: ( x i , 1 , y i + 1 , 1 ) , ( x i , 1 , a i , 1 ) , ( a i , 1 , x i , 1 ) , ( x i , 2 , a i , 1 ) , ( x i , 2 , a i , 2 ) , ( a i , 2 , x i , 2 ) , ( x i , 3 , y i + 1 , 3 ) , ( x i , 3 , a i , 2 ) , and ( y i + 1 , 3 , x i , 3 ) . This transformation is illustrated in Figure 7, where the left side shows the attacks before the transformation and the right side shows the attacks after the transformation.

OPEN IN VIEWER

Figure 7.

Transformation of attacks between arguments in A F S A T . (a) Before transformation. (b) After transformation.

Consider a self-defending set S in the framework constructed from A F S A T using this transformation. After this transformation, for x i + 1 , 1 , we have x i + 1 , 1 − ∖ x i + 1 , 1 + = { y i + 1 , 1 } and y i + 1 , 1 − = { b i , 1 , x i , 1 } . Additionally, b i , 1 − = a i , 2 and a i , 2 − = { x i , 2 , x i , 3 } . Therefore, if x i + 1 , 1 ∈ S , then S ∩ { x i , 1 , x i , 2 , x i , 3 } ≠ ∅ . Similarly, for x i + 1 , 2 , we have x i + 1 , 2 − ∖ x i + 1 , 2 + = { y i + 1 , 2 } and y i + 1 , 2 − = { b i , 1 , b i , 2 } , with b i , 1 − = a i , 2 , b i , 2 − = a i , 1 , and a i , 1 − ∪ a i , 2 − = { x i , 1 , x i , 2 , x i , 3 } . So, if x i + 1 , 2 ∈ S , then S ∩ { x i , 1 , x i , 2 , x i , 3 } ≠ ∅ . For x i + 1 , 3 , we have x i + 1 , 3 − ∖ x i + 1 , 3 + = { y i + 1 , 3 } and y i + 1 , 3 − = { b i , 2 , x i , 3 } , with b i , 2 − = a i , 1 and a i , 1 − = { x i , 1 , x i , 2 } . Thus, if x i + 1 , 3 ∈ S , then S ∩ { x i , 1 , x i , 2 , x i , 3 } ≠ ∅ . We deduce that S ∩ { x i , 1 , x i , 2 , x i , 3 } ≠ ∅ if x i + 1 , j ∈ S for 1 ≤ j ≤ 3 . Thus, Condition A is preserved after the transformation.

Using this transformation, we construct a new argumentation framework A F = ⟨ B , D ⟩ from A F S A T = ⟨ A , R ⟩ , where the number of symmetric attacks is reduced compared to A F S A T . Formally, A F = ⟨ B , D ⟩ is defined as follows.

B = A ∪ { a i , j , b i , j ∣ 1 ≤ i ≤ m − 1 and 1 ≤ j ≤ 2 } ∪ { a , b } ; D = ( R ∖ ( { ( y i + 1 , 1 , x i , 1 ) , ( x i , 2 , y i + 1 , 2 ) , ( y i + 1 , 2 , x i , 2 ) | 1 ≤ i ≤ m − 1 } ∪ { ( y i + 1 , k , x i , j ) , ( x i , j , y i + 1 , k ) | j ≠ k with 1 ≤ i ≤ m − 1 and 1 ≤ j , k ≤ 3 } ∪ { ( x m , j , y ) , ( y , x m , j ) ∣ 1 ≤ j ≤ 2 } ) ) ⋃ ( { ( x i , j , a i , 1 ) ∣ 1 ≤ i ≤ m − 1 and 1 ≤ j ≤ 2 } ∪ { ( x i , j , a i , 2 ) ∣ 1 ≤ i ≤ m − 1 and 2 ≤ j ≤ 3 } ∪ { ( a i , j , x i , j ) ∣ 1 ≤ i ≤ m − 1 and 1 ≤ j ≤ 2 } ∪ { ( a i , 1 , b i , 2 ) , ( a i , 2 , b i , 1 ) ∣ 1 ≤ i ≤ m − 1 } ∪ { ( b i , 1 , y i + 1 , j ) ∣ 1 ≤ i ≤ m − 1 and 1 ≤ j ≤ 2 } ∪ { ( b i , 2 , y i + 1 , j ) ) ∣ 1 ≤ i ≤ m − 1 and 2 ≤ j ≤ 3 } ∪ { ( y i + 1 , j , b i , j ) ∣ 1 ≤ i ≤ m − 1 and 1 ≤ j ≤ 2 } ∪ { ( x m , 1 , a ) , ( a , x m , 1 ) , ( x m , 2 , a ) , ( a , b ) , ( b , y ) } ) .

(1)

An illustration of this construction is given in Figure 8.

OPEN IN VIEWER

Figure 8.

Argumentation framework constructed from the argumentation framework depicted in Figure 6 using formula (1).

The following theorem states that there exists an admissible set in A F S A T contains “s” if and only if there exists one in A F contains “s.”

Theorem 12

Consider A F = ⟨ B , D ⟩ be the argumentation framework constructed from the framework A F S A T = ⟨ A , R ⟩ using formula (1). Then there exists an admissible set F ∈ A D M ( A F S A T ) such that s ∈ F if and only if there exists an admissible set T ∈ A D M ( A F ) such that s ∈ T .

Proof.

We show the forward implication. Let F be an admissible set of A F S A T and suppose that s ∈ F . Then for all 1 ≤ i ≤ m it holds that F ∩ { x i , 1 , x i , 2 , x i , 3 } ≠ ∅ . Consequently, this implies that in A F , we have F + ∩ { a i , 1 , a i , 2 } ≠ ∅ and { y i , 1 , y i , 2 , y i , 3 } ∩ F = ∅ for all 1 ≤ i ≤ m − 1 . Therefore, in the framework A F , the set F ∪ { b i , 1 , b i , 2 ∣ 1 ≤ i ≤ m − 1 } is conflict-free. Let T be a subset of B constructed as follows:

T = F ∪ { b i , 1 ∣ a i , 2 ∈ F + with 1 ≤ i ≤ m − 1 } ∪ { b i , 2 ∣ a i , 1 ∈ F + with 1 ≤ i ≤ m − 1 } ∪ { b ∣ a ∈ F + } .

We aim to show that T is an admissible set in A F . We have s ∈ F then it follows that y ∉ F . We deduce that b ∉ λ ( F ) implies that T is a conflict-free set in A F . Now, it remains to show that T is self-defending in A F . To reach a contradiction, suppose that T is not self-defending in A F . By the construction of T , it holds that b i , 1 ∈ T if a i , 2 ∈ F + and b i , 2 ∈ T if a i , 1 ∈ F + for all 1 ≤ i ≤ m − 1 . Since in A F , b i , j − ∖ { a i , j } = ∅ for all 1 ≤ i ≤ m − 1 and 1 ≤ j ≤ 2 , it follows that ( { b i , j ∣ 1 ≤ i ≤ m − 1 and 1 ≤ j ≤ 2 } ∩ T ) − ⊆ T + . Furthermore, by the construction of T , b ∈ T if a ∈ T + and since in A F , b − ∖ { a } = ∅ , it follows that b − ⊆ T + when b ∈ T . Therefore, there must exist an x i * , j * ∈ F such that x i * , j * − ⊈ T + with i * ∈ { 1 , … , m } and j * ∈ { 1 , 2 , 3 } , or s − ⊈ T + . First, suppose that s − ⊈ T + . Since in A F , s − ∖ { y } = ∅ and y − = { b , x m , 3 } , it follows that T ∩ { b , x m , 3 } = ∅ . As b ∉ T , we can infer from the construction of T that a ∉ F + . As in A F , a − = { x m , 1 , x m , 2 } , which implies that T ∩ { x m , 1 , x m , 2 , x m , 3 } = ∅ . This contradicts the fact that F is an admissible set containing s in A F . Now, suppose that there exists an x i * , j * ∈ F such that x i * , j * − ⊈ T + with i * ∈ { 1 , … , m } and j * ∈ { 1 , 2 , 3 } . In A F , we have x i * , j * − = { y i * , j * } . If i * = 1 , then y 1 , j * − = { t j * } . Thus, if x 1 , j * − ⊈ T + , it follows that t j * ∉ F ⊆ T . In A F S A T , x 1 , j * ∈ y 1 , j * + and y 1 , j * − = { t j * } , so x 1 , j * − ⊈ F + . This contradicts the fact that F is an admissible set in A F S A T . Now, suppose i * > 1 . In this case we have: y i * , 1 − = { x i * − 1 , 1 , b i * − 1 , 1 } ; y i * , 2 − = { b i * − 1 , 1 , b i * − 1 , 2 } ; and y i * , 3 − = { x i * − 1 , 3 , b i * − 1 , 2 } . Hence, T ∩ { x i * − 1 , 1 , x i * − 1 , 3 , b i * − 1 , 1 , b i * − 1 , 2 } = ∅ . By the construction of T , we have b i * − 1 , 1 ∈ T if a i * − 1 , 2 ∈ F + and b i * − 1 , 2 ∈ T if a i * − 1 , 1 ∈ F + . It follows that F + ∩ { a i * − 1 , 1 , a i * − 1 , 2 } = ∅ . As in A F , { a i * − 1 , 1 , a i * − 1 , 2 } − = { x i * − 1 , 1 , x i * − 1 , 2 , x i * − 1 , 3 } then F ∩ { x i * − 1 , 1 , x i * − 1 , 2 , x i * − 1 , 3 } = ∅ . This contradicts the fact that F is an admissible set containing s in A F . Thus, in both cases, we arrive at a contradiction; we can conclude that T must be self-defending in A F . Therefore, T is an admissible set in A F containing s .

Now, we show the reverse implication. Let F be an admissible set of A F such that s ∈ F . Since s ∈ F , ( y , s ) ∈ D and y − = { b , x m , 3 } , then F ∩ { b , x m , 3 } ≠ ∅ . If b ∈ F , then as ( a , b ) ∈ D and a − = { x m , 1 , x m , 2 } , it follows that F ∩ { x m , 1 , x m , 2 } ≠ ∅ . Hence, F ∩ { x m , 1 , x m , 2 , x m , 3 } ≠ ∅ . Additionally, in A F , for all 2 ≤ i ≤ m and 1 ≤ j ≤ 3 , we have ( y i , j , x i , j ) ∈ D and y i , 1 − = { x i − 1 , 1 , b i − 1 , 1 } , y i , 2 − = { b i − 1 , 1 , b i − 1 , 2 } , and y i , 3 − = { x i − 1 , 3 , b i − 1 , 2 } . Thus, for all 1 ≤ i ≤ m − 1 , F ∩ { x i , 1 , x i , 3 , b i , 1 , b i , 2 } ≠ ∅ . Similarly, for all 1 ≤ i ≤ m − 1 and 1 ≤ j ≤ 2 in A F , we have ( a i , j , b i , j ) ∈ D , a i , 1 − = { x i , 1 , x i , 2 } , and a i , 2 − = { x i , 2 , x i , 3 } . Therefore, we deduce that for all 1 ≤ i ≤ m , F ∩ { x i , 1 , x i , 2 , x i , 3 } ≠ ∅ . Furthermore, y 1 , j − = { t j } for all 1 ≤ j ≤ 3 , so F ∩ { t 1 , t 2 , t 3 } ≠ ∅ . As a result, the set

T = { s } ∪ ( F ∩ { x i , j ∣ 1 ≤ i ≤ m and 1 ≤ j ≤ 3 } ) ∪ ( F ∩ { t 1 , t 2 , t 3 } )

is self-defending in A F S A T . Thus, T is an admissible set in A F S A T if it is conflict-free in A F S A T . By the construction of A F , ( x i , j , x k , l ) ∈ D if and only if ( x i , j , x k , l ) ∈ R with 1 ≤ i , k ≤ m and 1 ≤ j , l ≤ 3 . Hence, T is conflict-free in A F S A T . We deduce that T is an admissible set in A F S A T that contains s . The proof follows.

Consider A F = ⟨ A , R ⟩ , the argumentation framework constructed from A F S A T using formula (1). This framework A F satisfies the property δ ( 1 , 1 , c ) . Furthermore, all arguments in A F , except those in the set { x i , j ∈ A ∣ 1 ≤ i ≤ m and 1 ≤ j ≤ 3 } , have at most one symmetric attack.

In order to obtain an argumentation framework that satisfies the property δ ( 1 , 1 , 1 ) , in the following step, we will remove all symmetric attacks between the arguments of the set { x i , j ∈ A ∣ 1 ≤ i ≤ m and 1 ≤ j ≤ 3 } . Let x i * , j * , with i * ∈ { 1 , … , m } and j * ∈ { 1 , … , 3 } , be an argument of A F . Suppose that the arguments with which x i * , j * has symmetric attacks, except those from the set { a i * , 1 , a i * , 2 , y i * + 1 , 3 } , are given in the order: x h 1 , l 1 , … , x h n , l n .

To maintain the existence of an admissible set F that includes “ s ” in A F if and only if there exists an admissible set T that includes “ s ” in the argumentation framework we wish to construct, it is essential to ensure that if x i * , j * ∈ S , then S ∩ { x h 1 , l 1 , … , x h n , l n } = ∅ . The idea here involves adding new arguments { z i * , 1 , … , z i * , n , t i * , 1 , … , t i * , n } and replacing the attacks ( x i * , j * , x h f , l f ) and ( x h f , l f , x i * , j * ) with the attacks ( z i * , f , x h f , l f ) and ( x h f , l f , z i * , f ) for all 1 ≤ f ≤ n . Additionally, we add the attacks and ( z i * , f , t i * , f ) for all 1 ≤ f ≤ n , ( t i * , f , z i * , f + 1 ) for all 1 ≤ f ≤ n − 1 , and ( t i * , n , x i * , j * ) . This transformation is illustrated in Figure 9, where Figure 9(a) shows the attacks before the transformation, and Figure 9(b) shows the attacks after the transformation.

OPEN IN VIEWER

Figure 9.

Transformation to reduce symmetric attacks. (a) Before transformation. (b) After transformation.

Observe that in the constructed framework using this transformation, we have x i * , j * − = { t i * , n } and t i * , f − ∖ { z i * , f } = ∅ for all 1 ≤ f ≤ n . Consider an admissible set S in the framework constructed from A F using this transformation. If x i * , j * belongs to S , then { z i * , 1 , … , z i * , n } ⊆ S . Since { x h 1 , l 1 , … , x h n , l n } ⊆ λ ( { z i * , 1 , … , z i * , n } ) , then S ∩ { x h 1 , l 1 , … , x h n , l n } = ∅ .

Using this transformation on A F , we are now ready to present our fundamental result, indicating that the computational complexity of the problem CredA persists within argumentation frameworks that satisfy the property δ ( 1 , 1 , 1 ) .

Theorem 13

Let A F = ⟨ A , R ⟩ be an argumentation framework. If A F satisfies the property δ ( 1 , 1 , 1 ) then CredA is N P -complete.

Proof.

Let A F = ⟨ A , R ⟩ be an argumentation framework constructed from the argumentation framework A F S A T using formula (1). Define A F ( k ) = ⟨ A ( k ) , R ( k ) ⟩ as an argumentation framework constructed constructed from A F ( k − 1 ) = ⟨ A ( k − 1 ) , R ( k − 1 ) ⟩ with A F ( 0 ) = A F as follows.

First, we define the set Sym ( k ) ( x i , j ) = { x h , l ∈ A ( k ) | ( x i , j , x h , l ) ∈ R ( k ) } ∪ { z h , l ∈ A ( k ) | ( x i , j , z h , l ) ∈ R ( k ) } as the set of arguments that both attack x i , j and are attacked by x i , j in A F ( k ) , which we aim to remove their symmetric attacks with x i , j . Let x i * , j * ∈ A with i * ∈ { 1 , … , m } and j * ∈ { 1 , 2 , 3 } be the first argument in A F ( k − 1 ) for which Sym ( k − 1 ) ( x i * , j * ) is not empty. In other words, if there exists another argument x h * , l * ∈ A with h * ∈ { 1 , … , m } and l * ∈ { 1 , 2 , 3 } for which Sym ( k − 1 ) ( x i * , j * ) is not empty, then 1 ≤ i * ≤ h * ≤ m and 1 ≤ j * < l * ≤ 3 when i * = h * .

Suppose that the elements of Sym ( k − 1 ) ( x i * , j * ) are ordered as follows: x h 1 , l 1 , … , x h n , l n , z h n + 1 , l n + 1 , … , z h r , l r , with r is the size of Sym ( k − 1 ) ( x i * , j * ) . Consider the framework A F ( k ) = ⟨ A ( k ) , R ( k ) ⟩ constructed from A F ( k − 1 ) by introducing new arguments { z i * , 1 , … , z i * , r } and { t i * , 1 , … , t i * , r } . Formally A F ( k ) is defined as follows:

A ( k ) = A ( k − 1 ) ∪ { z i * , 1 , … , z i * , r , t i * , 1 , … , t i * , r } ; R ( k ) = ( R ( k − 1 ) ∖ ( { ( x h f , l f , x i * , j * ) , ( x i * , j * , x h f , l f ) ∣ 1 ≤ f ≤ n } ∪ { ( z h f , l f , x i * , j * ) , ( x i * , j * , z h f , l f ) ∣ n + 1 ≤ f ≤ r } ∪ { ( y i * , j * , x i * , j * ) } ) ) ⋃ ( { ( y i * , j * , z i * , 1 ) } ∪ { ( z i * , f , x h f , l f ) , ( x h f , l f , z i * , f ) ∣ 1 ≤ f ≤ n } ∪ { ( z i * , f , z h f , l f ) , ( z h f , l f , z i * , f ) ∣ n + 1 ≤ f ≤ r } ∪ { ( z i * , f , t i * , f ) ∣ 1 ≤ f ≤ r } ∪ { ( t i * , f , z i * , f + 1 ) ∣ 1 ≤ f ≤ r − 1 } ∪ { ( t i * , r , x i * , j * ) } ) .

An illustration of this construction is given in Figure 10. Let us define A F ( n ) as the last argumentation framework that can be constructed using the above procedure. Specifically, A F ( n ) is the framework where no x i , j ∈ A with 1 ≤ i ≤ m and 1 ≤ j ≤ 3 has Sym ( n ) ( x i , j ) ≠ ∅ . An illustrative example of this case is provided in Figure 11. The construction of A F ( n ) can be done in a polynomial time in the size of A F . Moreover, A F ( n ) satisfies the property δ ( 1 , 1 , 1 ) . Now, we aim to show this statement: There exists an admissible set F that includes “ s ” in A F if and only if there exists an admissible set T in A F ( n ) that includes “ s .” OPEN IN VIEWER

Figure 10.

Argumentation framework A F ( 1 ) constructed from the argumentation framework depicted in Figure 8.

OPEN IN VIEWER

Figure 11.

Transforming the argumentation presented in Figure 8 to satisfy the Δ ( 1 , 1 , 1 ) property by successfully applying the procedure described in the proof of Theorem 13.

First, we show the forward implication of the statement. We proceed by induction. Suppose that F is an admissible set of A F ( k ) , where 1 ≤ k ≤ n . Let x i * , j * ∈ A be the first argument in A F ( k ) for which Sym ( k ) ( x i * , j * ) is not empty. Given that the construction of A F ( k + 1 ) does not modify the attackers of arguments other than x i * , j * , it follows that F remains an admissible set in A F ( k + 1 ) if x i * , j * ∉ F . Now, suppose that x i * , j * ∈ F , and let T = F ∪ { z i * , 1 , … , z i * , r } be a subset of A ( k + 1 ) . We will show that T is an admissible set of A F ( k + 1 ) . By supposition F is conflict-free in A F ( k ) and x i * , j * ∈ F , as ( Sym ( k ) ( x i * , j * ) ∪ { y i * , j * } ) ⊆ λ ( x i * , j * ) , it holds that F ∩ ( Sym ( k ) ( x i * , j * ) ∪ { y i * , j * } ) = ∅ . Furthermore, following the construction of A F ( k + 1 ) , we observe that ( λ ( { z i * , 1 , … , z i * , r } ) ∩ A ( k ) ) ∖ ( Sym ( k ) ( x i * , j * ) ∪ { y i * , j * } ) = ∅ , confirming that T is conflict-free in A F ( k + 1 ) . Now, it suffices to show that T is a self-defending set of A F ( k + 1 ) . By the construction of A F ( k + 1 ) , we have z i * , 1 − = { y i * , j * } . In A F ( k ) , we have x i * , j * + ∖ x i * , j * − = { y i * , j * } , and based on our supposition that F is self-defending in A F ( k ) with x i * , j * ∈ F , it implies that y i * , j * ∈ F + , hence z i * , 1 − ∈ F + . Furthermore, in A F ( k + 1 ) , we have x i * , j * − = { t i * , r } , { z i * , 2 , … , z i * , r } − = { t i * , 1 , … , t i * , r − 1 } , and { t i * , 1 , … , t i * , r } ⊆ { z i * , 1 , … , z i * , r } + , leading to ( { z i * , 1 , … , z i * , r } ∪ { x i * , j * } ) − ⊆ T + . As ( F ∖ ( { z i * , 1 , … , z i * , r } ∪ { x i * , j * } ) ) − ⊆ F + ⊆ T + , we can deduce that T is an admissible set in A F ( k + 1 ) . Consequently, there exists an admissible set T in A F ( n ) such that F ⊆ T if F is an admissible set in A F .

Next, we show the reverse implication of the statement. We proceed by induction. Suppose that F is an admissible set in A F ( k ) , where 1 ≤ k ≤ n . Let x i * , j * ∈ A be the first argument in A F ( k − 1 ) for which Sym ( k − 1 ) ( x i * , j * ) is not empty. As the construction of A F ( k ) does not modify the attackers of arguments other than x i * , j * then it follows that F is an admissible set of A F ( k − 1 ) if x i * , j * ∉ F . Suppose now that x i * , j * ∈ F and let T = F ∖ { z i * , 1 , … , z i * , r } be a subset of A ( k − 1 ) . Let us now show that T is an admissible set of A F ( k − 1 ) . We analyze the specific construction of A F ( k ) to deduce properties of F . First, we notice that ( t i * , r , x i * , j * ) ∈ R ( k ) and t i * , r − ∖ { z i * , r } = ∅ . From this, we can conclude that z i * , r ∈ F . Furthermore, in A F ( k ) , we have ( t i * , f , z i * , f + 1 ) ∈ R ( k ) for every 1 ≤ f ≤ r − 1 and t i * , f − ∖ { z i * , f − 1 } = ∅ for every 2 ≤ f ≤ r . Consequently, we can deduce that { z i * , 1 , … , z i * , r } ⊆ F . By supposition F is conflict-free in A F ( k ) and given that in A F ( k ) , Sym ( k − 1 ) ( x i * , j * ) ∪ { y i * , j * } ⊆ λ ( { z i * , 1 , … , z i * , r } ) , we can deduce that F ∩ ( Sym ( k − 1 ) ( x i * , j * ) ∪ { y i * , j * } ) = ∅ . For the suck of simplicity, we define N = Sym ( k − 1 ) ( x i * , j * ) ∪ { x i * , j * , y i * , j * } . By the construction of A F ( k ) , we have R ( k − 1 ) ∖ R ( k ) ⊆ N × N , so we can deduce that T is conflict-free in A F ( k − 1 ) . It remains to show that T is self-defending in A F ( k − 1 ) . As the construction of A F ( k ) does not modify the attackers of arguments other than x i * , j * and by supposition F is self-defending in A F ( k ) , then ( T ∖ { x i , j } ) − ⊆ T + . Thus, T is self-defending in A F ( k ) if x i * , j * − ⊆ T + . We have ( y i * , j * , z i * , 1 ) ∈ R ( k ) , and y i * , j * − ∩ ( A ( k ) ∖ A ) = ∅ . As, F is self-defending in A F ( k ) and z i * , 1 ∈ F then we can deduce that x i * , j * − = { y i * , j * } ⊆ T + conforming that T is an admissible set in A F ( k − 1 ) . This concludes the proof.

To further understand the relationship between the computational complexity of the problem CredA and symmetric attacks, we set “ c ” to zero and “ a ” and “ b ” to 2 . Surprisingly, our results show that the complexity of CredA persists under this variation as well.

Consider A F = ⟨ A , R ⟩ , the framework constructed in the proof of Theorem 13. We aim to construct an argumentation framework from A F that satisfies the property δ ( 2 , 2 , 0 ) while preserving the existence of an admissible set F in A F such that s ∈ F if and only if there exists an admissible set T that includes s in the constructed framework.

Consider two arguments z i , j and z k , l , with 1 ≤ i , k ≤ m and 1 ≤ j , l ≤ 3 in A F . Suppose that there is a symmetric attack between them, that is, ( z i , j , z k , l ) ∈ R and ( z k , l , z i , j ) ∈ R . Therefore, if F is an admissible set in A F such that z i , j ∈ F , then z k , l ∉ F . We want to remove the symmetric attack between any pair of arguments z i , j and z k , l while preserving the property that if one argument belongs to an admissible set, the other cannot. The basic idea is transforming the symmetric attack between any pair of arguments into a cycle of length six. To achieve this transformation, we add new arguments c i , j , c k , l , d i , j , and d k , l . We replace the attacks ( z i , j , z k , l ) and ( z k , l , z i , j ) with the attacks ( z i , j , c k , l ) , ( c k , l , d i , j ) , ( d i , j , z k , l ) , ( z k , l , c i , j ) , ( c i , j , d k , l ) , and ( d k , l , z i , j ) .

An illustration of this transformation is given in Figure 12. In Figure 12(a), we see a pair of arguments ( z i , j , z k , l ) with a symmetric attack. Figure 12(b) shows the transformation of the symmetric attack into a cycle of length six.

OPEN IN VIEWER

Figure 12.

Transformation of symmetric attacks into a cycle of length six. (a) Before transformation. (b) After transformation.

In the transformed framework depicted in Figure 12(b), z i , j − = { d k , l } , and d k , l − = { c i , j } . Thus, if F is an admissible set in the framework constructed using this transformation and z i , j ∈ F , then c i , j ∈ F . Since c i , j attacks z k , l , it follows that z k , l ∉ F . Moreover, z k , l − = { d i , j } , so d i , j ∈ F . Given that d i , j − is a subset of z i , j + , it follows that z i , j − is a subset of F + . Thus, z i , j belongs to an admissible set in the constructed framework using this transformation if it belongs to an admissible set in A F .

By applying this transformation to A F , we show in the following theorem that the computational complexity of the problem CredA persists even within argumentation frameworks that satisfy the property δ ( 2 , 2 , 0 ) .

Theorem 14

Let A F = ⟨ A , R ⟩ be an argumentation framework. If A F satisfies the property δ ( 2 , 2 , 0 ) then CredA is NP-complete.

Proof.

Consider A F = ⟨ A , R ⟩ be the framework constructed in the proof of Theorem 13. Let A F ′ = ⟨ B , D ⟩ be an argumentation framework constructed from A F using the following formula:

B = A ∪ { c i , j , c k , l , d i , j , d k , l ∣ ( z i , j , z k , l ) ∈ R with 1 ≤ i , k ≤ m and 1 ≤ j , l ≤ 3 } ; D = ( R ∖ ( { ( z i , j , z k , l ) , ( z k , l , z i , j ) ∣ 1 ≤ i , k ≤ m and 1 ≤ j , l ≤ 3 } ∪ { ( a i , j , x i , j ) , ( y i + 1 , j , b i , j ) ∣ 1 ≤ i ≤ m − 1 and 1 ≤ j ≤ 2 } ∪ { ( y i + 1 , 3 , x i , 3 ) ∣ 1 ≤ i ≤ m − 1 } ∪ { ( a , x m , 1 ) , ( y , x m , 3 ) } ) ) ∪ { ( z i , j , c k , l ) , ( c k , l , d i , j ) , ( d i , j , z k , l ) , ( z k , l , c i , j ) , ( c i , j , d k , l ) , ( d k , l , z i , j ) ∣ ( z i , j , z k , l ) ∈ R with 1 ≤ i , k ≤ m and 1 ≤ j , l ≤ 3 } .

(2)

Figure 13 provides an illustration of this construction. OPEN IN VIEWER

Figure 13.

Transforming the argumentation presented in Figure 11 to satisfy the Δ ( 2 , 2 , 0 ) property by applying formula (2).

We show this statement: there exists an admissible set F ∈ A D M ( A F ) such that s ∈ F if and only if there exists an admissible set T ∈ A D M ( A F ′ ) such that s ∈ T .

First, we show the “if” part of the statement. Let F be an admissible set of A F with s ∈ F . We define the set T = F ∪ { c i , j , d i , j ∣ z i , j ∈ F with 1 ≤ i ≤ m and 1 ≤ j ≤ 3 } . Considering s is an element of F , it is apparent that s is also an element of T . Now, we aim to show that T is admissible of A F ′ . Let z i * , j * ∈ F with i * ∈ { 1 , … , m } and j * ∈ { 1 , 2 , 3 } . In A F , there exists a unique argument z k * , l * ∈ A with k * ∈ { 1 , … , m } and l * ∈ { 1 , 2 , 3 } such that ( z i * , j * , z k * , l * ) ∈ R . Since F is conflict-free in A F , then z k * , l * ∉ F . It follows that c k * , l * , d k * , l * ∉ T . Since in A F ′ , λ ( { c i * , j * , d i * , j * } ) ∖ { z k * , l * , c k * , l * , d k * , l * } = ∅ and given that F is conflict-free in A F , we deduce that T is conflict-free in A F ′ . Now, it remains to show that T is self-defending in A F ′ . For the suck of simplicity, we define N = A ∖ { z i , j ∣ 1 ≤ i ≤ m and 1 ≤ j ≤ 3 } . By the construction of A F ′ , we have D ∩ ( N × N ) = R . Thus, T is self-defending in A F ′ if for all 1 ≤ i , k ≤ m and 1 ≤ j , l ≤ 3 the following condition holds:

if ( z i , j , z k , l ) ∈ R and z i , j ∈ F then ( { z k , l } ∪ ( { z i , j , c i , j , d i , j } ) − ) ⊆ T + .

Let z i * , j * , z k * , l * ∈ A such that ( z i * , j * , z k * , l * ) ∈ R and suppose that z i * , j * ∈ F . By the construction of A F ′ , we have ( { z i * , j * } × B ) ∩ D ∖ R = { ( z i * , j * , c k * , l * ) , ( d k * , l * , z i * , j * ) } . Thus, z i * , j * − ⊆ T + if d k * , l * ∈ T + . In A F ′ , we have { c i * , j * , d i * , j * } − ∖ { z k * , l * , c k * , l * , d k * , l * } = ∅ and { z k * , l * , c k * , l * , d k * , l * } ⊆ { z i * , j * , c i * , j * , d i * , j * } + , then { z i * , j * , c i * , j * , d i * , j * } − ⊆ T + . As a result, T is self-defending in A F ′ implying that T is admissible set in A F ′ .

Now, we proceed to show the “only if” part of the statement. Let F be an admissible set of A F ′ . We define T = F ∩ A , given that s is an element of A , it is apparent that s is also an element of T . We will show that T is an admissible set of A F . For the sake of contradiction, suppose the contrary, that is, T is not admissible in A F . It follows by definition that T is not self-defending or not conflict-free in A F . First, suppose that T is not self-defending. Since B ∖ A = { c i , j , d i , j ∣ 1 ≤ i ≤ m and 1 ≤ j ≤ 3 } and ( { c i , j , d i , j ∣ 1 ≤ i ≤ m and 1 ≤ j ≤ 3 } + ∩ A ) ⊆ { z i , j ∣ 1 ≤ i ≤ m and 1 ≤ j ≤ 3 } . We deduce that there exists z i * , j * ∈ A with i * ∈ { 1 , … , m } and j * ∈ { 1 , 2 , 3 } such that z i * , j * ∉ T + . Let z k * , l * ∈ A with k * ∈ { 1 , … , m } and l * ∈ { 1 , 2 , 3 } such that ( z k * , l * , z i * , j * ) ∈ R . Not that z k * , l * exists and unique in A F . Since z i * , j * ∉ T + it follows that z k * , l * ∉ T or equivalently z k * , l * ∉ F . Given that F is self-defending in A F ′ by assumption, and in A F ′ , z i * , j * − ∩ ( B ∖ A ) = d k * , l * , we conclude that d k * , l * ∈ F . In A F ′ , we have d k * , l * − ⊈ ( B ∖ { z k * , l * } ) + , and as, z k * , l * ∉ F then we obtain a contradiction with the fact that F is a self-defending set in A F ′ . We deduce that T is a self-defending set in A F . Therefore, T is not conflict-free in A F . We have R ∖ { ( z k , l , z i , j ) , ( z i , j , z k , l ) ∣ 1 ≤ i , k ≤ m and 1 ≤ j , l ≤ 3 } ⊆ D . By supposition, F is conflict-free in A F ′ , then there exists z k * , l * , z i * , j * ∈ T such that ( z k * , l * , z i * , j * ) ∈ R . By the construction of A F ′ , there exists d i * , j * ∈ B such that ( d i * , j * , z k * , l * ) ∈ D . Moreover, d i * , j * − = { c k * , l * } . Since F is self-defending in A F ′ and z k * , l * ∈ F then c k * , l * ∈ F . Thus { z i * , j * , c k * , l * } ⊆ F and as ( z i * , j * , c k * , l * ) ∈ D then we obtain a contradiction with the fact that F is conflict-free in A F ′ . In both cases, we obtain a contradiction. Therefore, T is an admissible set of A F . This concludes the proof.

Note that the argumentation frameworks satisfying the property δ ( 1 , b , 0 ) and δ ( a , 1 , 0 ) are a subclass of the argumentation frameworks satisfying the property Δ ( a , 1 ) and Δ ( 1 , b ) , respectively. Therefore, both CredA and SkepA problems can be solved in polynomial time for this class of argumentation frameworks (Table 1).

OPEN IN VIEWER

Table 1.

Complexity results for problems CredA and SkepA under various bounded-degree constraints.

Satisfied property by the argumentation framework	CredA	SkepA	Reference
Δ ( 2 , 2 )	NP-complete	∏ 2 p -complete	Dunne 15
Δ ( p , 1 )	Polynomial	Polynomial	Theorem 7
Δ ( 1 , q )	Polynomial	Polynomial	Theorem 9
δ ( 1 , 1 , 1 )	NP-complete	–	Theorem 13
δ ( 2 , 2 , 0 )	NP-complete	–	Theorem 14
δ ( p , 1 , 0 )	Polynomial	Polynomial	Theorem 7
δ ( 1 , q , 0 )	Polynomial	Polynomial	Theorem 9
δ ( 0 , 0 , c )	Polynomial	Polynomial	Coste-Marquis et al. 25

We conclude this section by providing the following table that summarizes key studies, highlighting the relationship between specific bounded-degree constraints satisfied by an argumentation framework and the corresponding complexity of CredA and SkepA.

4. Conclusion