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

Abstract

This research explores the relationship between the bounded in-degree and out-degree of an argumentation framework and the computational complexity of the problems of Credulous Acceptance (CredA) and Skeptical Acceptance (SkepA) under preferred extensions. Researchers have studied the complexity of these problems when the in-degree $(p)$ and out-degree $(q)$ of the arguments are restricted to $2$ . Despite this restriction, the computational complexities of CredA and SkepA persist. Based on these results, we presents new results that provide deeper insights into the impact of additional constraints on the argumentation framework. Specifically, we show that when “ $p$ ” or “ $q$ ” is restricted to $1$ , both problems CredA and SkepA can be solved in polynomial time. Subsequently, we impose additional constraints on the argumentation framework by analyzing the quantities “ $a$ ,” “ $b$ ,” and “ $c$ .” For an argumentation framework $AF$ and all arguments “ $x$ ” of $AF$ , the parameter “ $a$ ” indicates the maximum number of attackers that any argument “ $x$ ” can have among all those that are not attacked by “ $x$ ” $AF$ , “ $b$ ” indicates the maximum number of arguments that any argument “ $x$ ” attacks among all those that do not attack “ $x$ ”, and “ $c$ ” denotes the maximum number of arguments that any argument “ $x$ ” attacks among those that attack “ $x$ ”. Surprisingly, even when all these quantities are restricted to $1$ , the computational complexity of CredA persists. Furthermore, we explore the influence of symmetric attacks by fixing “ $c$ ” to zero, while setting “ $a$ ” and “ $b$ ” to $2$ . Remarkably, the complexity of CredA persists under this restriction as well.

1. Introduction

Abstract argumentation frameworks ¹ are widely used in artificial intelligence,^2,3 result applications in decision-making,^4,5 multi-agent systems,^6,7 and argumentation-based recommender and decision support systems.^8–10 These frameworks provide a means to study and understand the interactions between arguments, enhancing our understanding of complex reasoning processes.

Informally, an abstract argumentation framework consists of a set of arguments and an attack relation between these arguments. Arguments represent individual points of view, claims, or statements, while attack relations capture the idea that one argument challenges or undermines another. This notion of attack allows for the exploration of conflicts and disagreements among arguments, simulating the process of critical discussion.

One of the key aspects of abstract argumentation involves the concept of the acceptability or justifiability of arguments. In these frameworks, determining whether a particular argument exists in any or all preferred extensions is crucial. Admissible sets represent conflict-free sets of arguments that counterattack all external attackers, while preferred extensions are maximal admissible sets based on set inclusion. Analyzing the acceptability status of arguments aids in identifying the most plausible and robust arguments within a given context.

To address this, two decision problems, Credulous Acceptance (CredA) and Skeptical Acceptance (SkepA), have been introduced. In the problem CredA the objective is to determine whether an argument $x$ is credulously accepted in an argumentation framework $AF=⟨\mathcal{A},\mathcal{R}⟩$ , that is, whether there exists at least one preferred extension of $AF$ that contains $x$ . Similarly, in the problem SkepA, the objective is to determine whether an argument $x$ is skeptically accepted in $AF$ , that is, whether every preferred extension of $AF$ contains $x$ . Extensive research has been devoted to studying these problems and developing effective algorithms and approaches to address them.^11–23 The complexity of these problems is known to be NP-complete for the CredA problem ²⁴ and $\prod _2^p$ -complete for the SkepA problem. ¹²

However, there are specific classes of argumentation frameworks that allow efficient solving of the problems CredA and SkepA. Notable examples include the class of symmetric argumentation frameworks, ²⁵ argumentation frameworks without even length cycles, ²⁶ bipartite argumentation frameworks, ¹⁵ and bounded treewidth argumentation frameworks. ¹⁵ Recent advancements in this area have further explored tractable fragments and reasoning techniques. For instance, Thimm et al. ²⁷ proposed methods for skeptical reasoning with preferred semantics without computing preferred extensions. Additionally, Dvořák et al. ²⁸ analyzed the complexity of preferred semantics in argumentation frameworks with bounded cycle length, and Dvořák et al. ²⁹ explored tractable abstract argumentation via backdoor-treewidth.

An argumentation framework can be represented by a directed graph, where the arguments are depicted as nodes, and the attacks as arcs. In the context of the complexity of the CredA and SkepA problems, Dunne ¹⁵ introduces the bounded degree class of abstract argumentation framework. In this class, each argument “ $x$ ” possesses an in-degree (the number of arguments that attack it) denoted by “ $p$ ” and an out-degree (the number of arguments it attacks) denoted by “ $q$ .” Interestingly, the complexity of the problems CredA and SkepA persists even when considering argumentation frameworks where both the in-degree and out-degree are restricted to $2$ (i.e., $p=q=2$ ), as shown by Dunne. ¹⁵ Thus, identifying the specific bounded-degree constraints under which this complexity reduces is essential. In addition, highlighting the variation in the complexity of these problems under different bounded-degree constraints is crucial for developing efficient algorithms. This understanding is not only academically interesting but also practically significant, as it can lead to the development of more effective computational tools. By proposing efficient algorithms tailored to specific bounded-degree constraints, we can expand the range of scenarios where these problems can be solved effectively, thus enhancing the practical applicability and performance of argumentation-based systems in real-world applications.

This paper aims to delve deeper into the relationship between degree bounds and the computational complexity of reasoning within abstract argumentation frameworks. A notable result from our own research highlights that when “ $p$ ” or “ $q$ ” is restricted to $1$ , the problems CredA and SkepA can be efficiently solved in polynomial time. Building upon this valuable insight, we further explore additional constraints on the argumentation framework. Consider an argumentation framework $AF$ . We investigate the following quantities: “ $a$ ,” which represents the maximum number of attackers that any argument “ $x$ ” can have in $AF$ among all those that are not attacked by “ $x$ ” in $AF$ , while “ $b$ ” indicates the maximum number of arguments that any argument “ $x$ ” attacks in $AF$ among all those that do not attack “ $x$ ” in $AF$ . Finally, “ $c$ ” denotes the maximum number of arguments that any argument “ $x$ ” attacks in $AF$ among those that attack “ $x$ ” in $AF$ .

Through a comprehensive analysis, we have obtained some surprising results: even when all the quantities “ $a$ ,” “ $b$ ,” and “ $c$ ” are strictly constrained to 1, the computational complexity of CredA continues to endure. To extend our investigation, we also considered the influence of symmetric attacks by fixing “ $c$ ” to zero, while setting “ $a$ ” and “ $b$ ” to 2. Surprisingly, our results indicate that the complexity of CredA remains persistent under this specific variation. Clarifying the difference between symmetric attacks and symmetric argumentation frameworks is crucial. In a symmetric argumentation framework, the attack relation is symmetric, meaning if an argument “ $x$ ” attacks an argument “ $y$ ,” then “ $y$ ” must also attack “ $x$ .” This property generally simplifies the computational complexity, as discussed in Coste-Marquis et al. ²⁵ However, our study’s constraints do not create a symmetric argumentation framework. Specifically, by setting “ $c$ ” to zero, we ensure no bidirectional (symmetric) attack between any pair of arguments.

Our research contributes valuable insights into the computational properties of argumentation frameworks and their implications for developing efficient algorithms and practical applications. The study highlights that regardless of the bounded degree, reasoning within abstract argumentation frameworks remains inherently complex. This understanding can offer potential optimization opportunities for future research and advance our understanding of the complexity of problems in abstract argumentation frameworks.

The remainder of this paper is organized as follows: Section 2 introduces the fundamental concepts necessary for this study. The main results are presented in Section 3. Finally, the conclusion of this paper is provided in Section 4.

2. Preliminaries

In this paper, all the objects under consideration are finite. Let $\mathcal{A}$ be a set. We use $2^{\mathcal{A}}$ to represent the powerset of $\mathcal{A}$ , which is the set of all subsets of $\mathcal{A}$ . For a subset $S$ of $\mathcal{A}$ , the complement $S^c$ of $S$ with respect to $\mathcal{A}$ is obtained by taking the elements in $\mathcal{A}$ that are not in $S$ , that is, $S^c=\mathcal{A}\setminus S$ . Consider a set system $\mathcal{F}$ over $\mathcal{A}$ , where $\mathcal{F}$ is a subset of $2^{\mathcal{A}}$ . The complementary set of $\mathcal{F}$ with respect to $\mathcal{A}$ is denoted as ${\mathcal{F}}^c$ and is defined as the set system consisting of the complements of all sets in $\mathcal{F}$ . In other words, ${\mathcal{F}}^c=\{S^c\mid S\in \mathcal{F}\}$ .

2.1. Abstract argumentation framework

An abstract argumentation framework, proposed by Dung, ¹ is a pair $AF=⟨\mathcal{A},\mathcal{R}⟩$ , where $\mathcal{A}$ is a finite set of arguments and $\mathcal{R}$ is a binary attack relation defined on $\mathcal{A}$ . The attack relation $\mathcal{R}$ represents conflicts between arguments, with $(x,y)\in \mathcal{R}$ meaning that argument $x$ attacks argument $y$ . This framework can be visualized as a directed graph, called an attack graph, with arguments as vertices and attacks as edges. For a set $S\subseteq \mathcal{A}$ , the sub-argumentation framework of $AF$ induced by $S$ is $AF[S]=⟨S,\mathcal{R}\cap (S\times S)⟩$ .

Example 1

Figure 1 describes an argumentation framework $AF=⟨\mathcal{A},\mathcal{R}⟩$ , where $\mathcal{A}=\{a_1,a_2,a_3,a_4\}$ and $\mathcal{R}=\{(a_1,a_2),(a_2,a_3),(a_2,a_4),(a_3,a_4),(a_4,a_3)\}$ .

Figure 1.

Attack graph of $AF$ .

Given a set of arguments $S\subseteq \mathcal{A}$ , the set $S^{+}$ represents the arguments attacked by $S$ , that is, the arguments $x$ for which there exists $y\in S$ such that $(y,x)\in \mathcal{R}$ . Similarly, $S^{-}$ denotes the set of arguments attacking at least one argument in $S$ , that is, the arguments $x$ for which there exists $y\in S$ such that $(x,y)\in \mathcal{R}$ . In case $S$ is a singleton $\{y\}$ , we write $y^{-}$ as a shortcut for $\{y{\}}^{-}$ . Finally, the union of $S^{+}$ and $S^{-}$ is denoted by $\lambda (S)$ .

In the context of the argumentation framework, an argument $x\in \mathcal{A}$ is acceptable with respect to a set of arguments $S\subseteq \mathcal{A}$ if for every $y\in \mathcal{A}$ such that $(y,x)\in \mathcal{R}$ , there exists $z\in S$ such that $(z,y)\in \mathcal{R}$ . A set $S\subseteq \mathcal{A}$ is considered conflict-free if $S\cap S^{+}=\mathrm{\varnothing }$ . The set of all conflict-free sets of $AF$ is denoted by $CF(AF)$ . Naive sets in the framework are the conflict-free subsets of $\mathcal{A}$ that are maximal with respect to the set inclusion. ³⁰ An argument $x\in \mathcal{A}$ is said to be self-conflicting if $(x,x)\in \mathcal{R}$ , the set of all self-conflicting arguments of $AF$ is denoted by $\mathrm{\S }(AF)$ .

Furthermore, a set $S\subseteq \mathcal{A}$ is said to be self-defending if $S^{-}\subseteq S^{+}$ . The set of all self-defending sets of $AF$ is denoted by $SD(AF)$ . Dung ¹ introduces various extensions based on the concepts of conflict-free sets and acceptability. A conflict-free set $S\subseteq \mathcal{A}$ is said to be admissible if it is self-defending. The set of all admissible sets of $AF$ is denoted by $ADM(AF)$ . The admissible subsets of $\mathcal{A}$ that are maximal with respect to the set inclusion are called preferred extensions. The set of all preferred extensions of $AF$ is denoted by $PREF(AF)$ . We refer the reader to Baroni et al. ³¹ and Dunne et al. ³² for more discussion on other semantics.

Example 2

Let $AF=⟨\mathcal{A},\mathcal{R}⟩$ be the argumentation framework depicted in Figure 1. The set of all conflict-free sets of $AF$ is $CF(AF)=\{\mathrm{\varnothing },\{a_4\}$ , $\{a_1\}$ , $\{a_1,a_4\}$ , $\{a_3\}$ , $\{a_1,a_3\}$ , $\{a_2\}\}$ . Notably, among these sets, $\{a_1,a_4\}$ , $\{a_1,a_3\}$ , and $\{a_2\}$ are the naive sets of $AF$ . Shifting attention to the self-defending sets in $AF$ , referred to as $SD(AF)$ , this set includes the sets $\mathrm{\varnothing }$ , $\{a_1\}$ , $\{a_1,a_4\}$ , $\{a_1,a_3\},$ and $\{a_1,a_3,a_4\}$ .

The intersection of self-defending and conflict-free sets of $AF$ , known as the set of admissible sets ( $ADM(AF)$ ), yields $ADM(AF)=\{\mathrm{\varnothing }$ , $\{a_1\}$ , $\{a_1,a_4\}$ , $\{a_1,a_3\}\}$ . It is noteworthy that among these sets $\{a_1,a_4\}$ and $\{a_1,a_3\}$ are the preferred extensions of $AF$ .

We conclude this part by introducing some graph concepts. For two arguments $x$ and $y$ in $\mathcal{A}$ , $x$ is considered a neighbor of $y$ in $AF$ if $x\in \lambda (\{y\})$ . A path in $AF$ is a sequence of edges directed in the same direction which joins a sequence of arguments $x_0,x_1,\dots ,x_{k-1},x_k$ . When $x_0=x_k$ holds, this sequence is referred to as a cycle. For a path $P$ in $AF$ , we denote by $\mathcal{A}(P)$ the set of arguments contained in it. The length of $P$ is defined as the number of edges it has. An argument $x$ is considered connected to an argument $y$ in $AF$ if there exists a directed path from $x$ to $y$ . Conversely, if no such directed path exists from $x$ to $y$ , then $x$ is said to be not connected to $y$ .

2.2. Closure systems and implicational systems

We use the terminology introduced in Grätzer ³³ and Wild. ³⁴ Consider a set system $\mathcal{F}$ over $\mathcal{A}$ . The notation $⟨\mathcal{F},\subseteq ⟩$ represents the family $\mathcal{F}$ with an ordering based on set inclusion. The system $\mathcal{F}$ is a closure system over $\mathcal{A}$ if $\mathcal{A}$ belongs to $\mathcal{F}$ , and the intersection of any two sets $F_1$ and $F_2$ in $\mathcal{F}$ also belongs to $\mathcal{F}$ . In other words, if $\mathcal{F}$ is closed under intersection. The sets within $\mathcal{F}$ are referred to as closed sets. Importantly, if $\mathcal{F}$ is a closure system, then $⟨\mathcal{F},\subseteq ⟩$ forms a lattice, as does $⟨{\mathcal{F}}^c,\subseteq ⟩$ .

An implication over $\mathcal{A}$ is an expression of the form $X\to y$ where $X\subseteq \mathcal{A}$ and $y\in \mathcal{A}$ . In $X\to y$ , $X$ is the premise and $y$ is the conclusion of the implication. Given an implicational system $\mathrm{\Sigma }=\{X_1\to x_1,\dots ,X_n\to x_n\}$ on a set $\mathcal{A}$ and a subset $S\subseteq \mathcal{A}$ , the $\mathrm{\Sigma }$ -closure of $S$ , denoted as $S^{\mathrm{\Sigma }}$ , represents the smallest set that contains $S$ and satisfies the following condition:

$$X_j\subseteq S^{\mathrm{\Sigma }}⟹x_j\in S^{\mathrm{\Sigma }}\text{ for every }1\le j\le n.$$

Computing $\mathrm{\Sigma }$ -closure of $S$ can be achieved in polynomial time. ³⁵ The family ${\mathcal{F}}_{\mathrm{\Sigma }}=\{S^{\mathrm{\Sigma }}\mid S\subseteq \mathcal{A}\}$ is a closure system.

When an implicational system $\mathrm{\Sigma }$ has the property that each implication $X\to x$ in $\mathrm{\Sigma }$ has a premise size of $1$ , that is, $|X|=1$ , it is referred to as a unit implicational system. In this case, the closure system associated with $\mathrm{\Sigma }$ is closed under both union and intersection, resulting in a distributive lattice $({\mathcal{F}}_{\mathrm{\Sigma }},\subseteq )$ . ³⁴

Let us conclude this part with a significant result that establishes a connection between the extensions of an argumentation framework and the closed sets of an implicational system. It has been shown in Elaroussi et al. ³⁶ that the closed sets of an implicational system coincide with the self-defending sets of an argumentation framework.

Theorem 1

Let $AF=⟨\mathcal{A},\mathcal{R}⟩$ be an argumentation framework, and let $\mathrm{\Sigma }=\{y^{-}\to z\mid (y,z)\in \mathcal{R}\text{ and }(z,y)\notin \mathcal{R}\}$ be its associated implicational system. Then ${\mathcal{F}}_{\mathrm{\Sigma }}^c=SD(AF)$ .

We give the following example to illustrate the above theorem.

Example 3

Consider $AF=⟨\mathcal{A},\mathcal{R}⟩$ the argumentation framework described by the Figure 1. The implicational system associated to $AF$ is $\mathrm{\Sigma }=\{\mathrm{\varnothing }\to a_2,\{a_1\}\to a_3,\{a_1\}\to a_4\}$ . For example, the implication $\{a_1\}\to a_3$ is derived from the fact that $a_2$ attacks $a_3$ and $a_2^{-}=\{a_1\}$ . The closure system of $\mathrm{\Sigma }$ is ${\mathcal{F}}_{\mathrm{\Sigma }}=\{\{a_1,a_2,a_3,a_4\}$ , $\{a_2,a_3,a_4\}$ , $\{a_2,a_3\}$ , $\{a_2,a_4\}$ , $\{a_2\}\}$ . Observe that ${\mathcal{F}}_{\mathrm{\Sigma }}=S{D}^c$ .

We end these preliminaries by gathering some existing results that will be useful throughout the paper.

Theorem 2 (Dung ¹ )

An argumentation framework $AF=⟨\mathcal{A},\mathcal{R}⟩$ has a unique preferred extension which is also a stable extension if it does not contain any cycles (acyclic).

Theorem 3 (Dunne and Bench-Capon ²⁶ )

An argumentation framework $AF=⟨\mathcal{A},\mathcal{R}⟩$ has a unique preferred extension if it does not contain any even length cycles.

Theorem 4 (Dunne and Bench-Capon ²⁶ )

The unique preferred extension of an argument framework $AF=⟨\mathcal{A},\mathcal{R}⟩$ that does not contain any even length cycles, can be constructed in $O(|\mathcal{A}|)$ steps.

3. On the bounded degree of an argumentation framework

In this section, we will delve into an investigation of how the complexity of the CredA and SkepA problems is affected by the bounded degree of an argumentation framework. By analyzing the relationship between the degree of the argumentation framework and the complexity of CredA and SkepA problems, we can gain a deeper understanding of the computational aspects involved in accepting or rejecting arguments in the framework.

Formally, CredA and SkepA problems can be defined as follows.

CredA

Input: An argumentation framework $AF=⟨\mathcal{A},\mathcal{R}⟩$ and an argument $x\in \mathcal{A}$

Question: Is $x$ contained in some $F\in PREF(AF)$ ?

SkepA

Input: An argumentation framework $AF=⟨\mathcal{A},\mathcal{R}⟩$ and an argument $x\in \mathcal{A}$

Question: Is $x$ contained in each $F\in PREF(AF)$ ?

Since any admissible set is a subset of some preferred extensions, credulous acceptance of an argument $x$ is ensured by finding any admissible (not necessarily maximal) set containing $x$ .

Example 4

Let $AF=⟨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 ${\mathrm{\Delta }}^{(p,q)}$ as follows.

Definition 1

Let $AF=⟨\mathcal{A},\mathcal{R}⟩$ be an argumentation framework. $AF$ satisfies the property ${\mathrm{\Delta }}^{(p,q)}$ if

$$\mathrm{\forall }x\in \mathcal{A}|\{y\in \mathcal{A}|(y,x)\in \mathcal{R}\}|\le p\text{ and }|\{y\in \mathcal{A}|(x,y)\in \mathcal{R}\}|\le q.$$

Note that $p$ and $q$ are bounded such that $0\le p,q\le |\mathcal{A}|$ , with $|\mathcal{A}|$ is the size of $\mathcal{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 ${\mathrm{\Delta }}^{(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 ${\mathrm{\Delta }}^{(2,2)}$ .

Figure 2.

Example of an argumentation framework that satisfies the property ${\mathrm{\Delta }}^{(2,2)}$ and one that does not. (a) Satisfies ${\mathrm{\Delta }}^{(2,2)}$ . (b) Does not satisfy ${\mathrm{\Delta }}^{(2,2)}$ .

Given an argumentation framework $AF=⟨\mathcal{A},\mathcal{R}⟩$ that satisfies the property ${\mathrm{\Delta }}^{(2,2)}$ , Dunne ¹⁵ has shown the following results.

Theorem 5

Let $AF=⟨\mathcal{A},\mathcal{R}⟩$ be an argumentation framework. If $AF$ satisfies the property ${\mathrm{\Delta }}^{(2,2)}$ then:

1. (1)

CredA is NP-complete.

(2)

SkepA is $\prod _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 $AF$ satisfies the property ${\mathrm{\Delta }}^{(1,q)}$ . The framework depicted in Figure 3 satisfies the property ${\mathrm{\Delta }}^{(1,q)}$ .

Figure 3.

Example of an argumentation framework satisfying the property ${\mathrm{\Delta }}^{(1,q)}$ . The associated implication system to this framework is $\mathrm{\Sigma }=\{\{a_1\}\to a_4,\{a_1\}\to a_3,\{a_2\}\to a_5,\{a_2\}\to 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 $\mathrm{\Sigma }=\{y^{-}\to z\mid (y,z)\in \mathcal{R}\text{ and }(z,y)\notin \mathcal{R}\}$ , to $AF$ 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}^{\prime }=⟨\mathcal{A},{\mathcal{R}}^{\prime }⟩$ such that $PREF(AF)=NAIV(A{F}^{\prime })$ . This result leads to the following theorem.

Theorem 6

Let $AF=⟨\mathcal{A},\mathcal{R}⟩$ be an argumentation framework satisfying the property ${\mathrm{\Delta }}^{(1,q)}$ . Then, there exists a polynomial time algorithm to construct an argumentation framework $A{F}^{\prime }=⟨\mathcal{A},{\mathcal{R}}^{\prime }⟩$ such that $PREF(AF)=NAIV(A{F}^{\prime })$ .

From this, we state the following result.

Theorem 7

Let $AF=⟨\mathcal{A},\mathcal{R}⟩$ be an argumentation framework. If $AF$ satisfies the property ${\mathrm{\Delta }}^{(1,q)}$ , then:

1. (1)

CredA can be solved in polynomial time.

(2)

SkepA can be solved in polynomial time.

Proof.

Given an argumentation framework $AF=⟨\mathcal{A},\mathcal{R}⟩$ that satisfies the property ${\mathrm{\Delta }}^{(1,q)}$ . According to Theorem 6, we can construct in polynomial time an argumentation framework $A{F}^{\prime }=⟨\mathcal{A},{\mathcal{R}}^{\prime }⟩$ such that $PREF(AF)=NAIV(A{F}^{\prime })$ . Through the transformation to $A{F}^{\prime }$ , it becomes evident that an argument $x$ belongs to a preferred extension (credulously accepted) in $AF$ if and only if it is not self-attacking in $A{F}^{\prime }$ . Additionally, $x$ belongs to all preferred extensions (skeptically accepted) in $AF$ if and only if it is not self-attacking in $A{F}^{\prime }$ 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 $AF$ satisfies the property ${\mathrm{\Delta }}^{(p,1)}$ . The framework depicted in Figure 4 satisfies the property ${\mathrm{\Delta }}^{(p,1)}$ .

Figure 4.

Example of an argumentation framework satisfying the property ${\mathrm{\Delta }}^{(p,1)}$ . The associated implication system to this framework is $\mathrm{\Sigma }=\{\{a_5,a_6\}\to a_2,\mathrm{\varnothing }\to a_2,\mathrm{\varnothing }\to 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 $AF=⟨\mathcal{A},\mathcal{R}⟩$ be an argumentation framework that satisfies the property ${\mathrm{\Delta }}^{(p,1)}$ . If $AF$ is an isolated cycle of even length, then $AF$ has exactly two preferred extensions.

Proof.

Given that $AF$ forms an even length cycle, we can arrange its arguments sequentially as $C=x_1,x_2,\dots ,x_{2k}$ , where $2k$ is the size of the set of arguments $\mathcal{A}$ . In this sequence, each argument attacks the next one, and $x_{2k}$ attacks $x_1$ . Also, due to the fact that $AF$ satisfies the property ${\mathrm{\Delta }}^{(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_{2i-1}\mid 1\le i\le k\},S_2=\{x_{2i}\mid 1\le i\le k\}.$$

The union of $S_1$ and $S_2$ covers all arguments in $AF$ .

We will show that $S_1$ and $S_2$ are two preferred extensions of $AF$ . 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\le i\le 2k-1$ , each $x_i\in S_1$ is only attacked by $x_{i-1}$ ; however, it is defended by $x_{i-2}\in S_1$ , which attacks $x_{i-1}$ . Moreover, $x_1\in S_1$ is only attacked by $x_{2k}$ ; however, it is defended by $x_{2k-1}\in S_1$ . Similarly, in $S_2$ , for $4\le i\le 2k$ , each $x_i\in S_2$ is only attacked by $x_{i-1}$ ; however, it is defended by $x_{i-2}\in S_2$ against $x_{i-1}$ . Additionally, $x_2\in S_2$ is only attacked by $x_1$ ; however, it is defended by $x_{2k}\in 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\ne S_1$ and $S\ne S_2$ . Thus, $S$ must contain both an argument $x_{2i^{*}-1}\in S_1$ and $x_{2j^{*}}\in S_2$ with $i^{*},j^{*}\in \{1,\dots ,k\}$ . Since $x_{2i^{*}-1}\in 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_{2j^{*}-1}$ and $x_{2j^{*}}$ , with $x_{2j^{*}-1}$ is a direct attacker of $x_{2j^{*}}$ . 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\text{ and }{S}_2\text{ are the unique preferred extensions of }AF.$

Let $AF=⟨\mathcal{A},\mathcal{R}⟩$ be an argumentation framework, and let $x\in \mathcal{A}$ be an argument in $AF$ . We define ${\mathcal{A}}_x$ as the set of all arguments that are connected to $x$ in $AF$ . Formally, ${\mathcal{A}}_x=\{y\mid y\text{ is connected to }x\text{ in }AF\}.$ We recall that an argument $y$ is said to be connected to $x$ in $AF$ if there exists a path from $y$ to $x$ . Let $A{F}_x=⟨{\mathcal{A}}_x,{\mathcal{R}}_x⟩$ be a sub-argumentation framework of $AF$ induced by the set ${\mathcal{A}}_x$ , where ${\mathcal{R}}_x=\mathcal{R}\cap ({\mathcal{A}}_x\times {\mathcal{A}}_x).$ Since ${\mathcal{R}}_x\subseteq \mathcal{R}$ , if $AF$ satisfies the property ${\mathrm{\Delta }}^{(p,1)}$ , then $A{F}_x$ also satisfies the property ${\mathrm{\Delta }}^{(p,1)}$ . We state the following results.

Lemma 2

Let $AF=⟨\mathcal{A},\mathcal{R}⟩$ be an argumentation framework that satisfies the property ${\mathrm{\Delta }}^{(p,1)}$ , and let $x\in \mathcal{A}$ . Define ${\mathcal{A}}_x=\{y\mid y\text{ is connected to }x\text{ in }AF\}$ and let $A{F}_x=⟨{\mathcal{A}}_x,{\mathcal{R}}_x⟩$ be the sub-argumentation framework of $AF$ induced by ${\mathcal{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 $AF$ belongs to at most one cycle. Let $y\in \mathcal{A}$ and suppose $C$ is a cycle in $AF$ that contains $y$ . In a cycle, every argument attacks at least one other argument within the same cycle. Since $AF$ satisfies property ${\mathrm{\Delta }}^{(p,1)}$ , then $y$ cannot attack another argument outside of $C$ . Therefore, each argument in $AF$ 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 ${\mathcal{A}}_x$ is connected to $x$ in $AF$ . 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 $AF$ satisfies the property ${\mathrm{\Delta }}^{(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 $AF=⟨\mathcal{A},\mathcal{R}⟩$ be an argumentation framework that satisfies the property ${\mathrm{\Delta }}^{(p,1)}$ , and let $x\in \mathcal{A}$ . Define ${\mathcal{A}}_x=\{y\mid y\text{ is connected to }x\text{ in }AF\}$ and let $A{F}_x=⟨{\mathcal{A}}_x,{\mathcal{R}}_x⟩$ be the sub-argumentation framework of $AF$ induced by ${\mathcal{A}}_x$ . Then, either ${\mathcal{A}}_x^{+}\cap (\mathcal{A}\setminus {\mathcal{A}}_x)=\mathrm{\varnothing }$ or $A{F}_x$ is acyclic.

Proof.

By the construction of $A{F}_x$ , each argument $y\in ({\mathcal{A}}_x\setminus \{x\})$ is connected to $x$ . Thus, each argument $y\in ({\mathcal{A}}_x\setminus \{x\})$ attacks at least one argument within $A{F}_x$ . Given that $AF$ satisfies the property ${\mathrm{\Delta }}^{(p,1)}$ , it follows that $A{F}_x$ also satisfies the property ${\mathrm{\Delta }}^{(p,1)}$ . Therefore, no argument in ${\mathcal{A}}_x$ except $x$ can attack arguments outside of ${\mathcal{A}}_x$ . Formally, $({\mathcal{A}}_x\setminus \{x\}{)}^{+}\cap (\mathcal{A}\setminus {\mathcal{A}}_x)=\mathrm{\varnothing }$ . Now, we show that $A{F}_x$ is acyclic if $x^{+}\cap (\mathcal{A}\setminus {\mathcal{A}}_x)\ne \mathrm{\varnothing }$ . According to Lemma 2, $A{F}_x$ can have at most one cycle that includes $x$ . Since $x^{+}\cap (\mathcal{A}\setminus {\mathcal{A}}_x)\ne \mathrm{\varnothing }$ and $A{F}_x$ satisfies the property ${\mathrm{\Delta }}^{(p,1)}$ , it follows that $x^{+}\cap {\mathcal{A}}_x=\mathrm{\varnothing }$ . As a result, $A{F}_x$ is acyclic. Hence, we have shown that either ${\mathcal{A}}_x^{+}\cap (\mathcal{A}\setminus {\mathcal{A}}_x)=\mathrm{\varnothing }$ or $A{F}_x$ is acyclic.

Lemma 4

Let $AF=⟨\mathcal{A},\mathcal{R}⟩$ be an argumentation framework, and let $x\in \mathcal{A}$ . Define ${\mathcal{A}}_x=\{y\mid y\text{ is connected to }x\text{ in }AF\}$ and let $A{F}_x=⟨{\mathcal{A}}_x,{\mathcal{R}}_x⟩$ be a sub-argumentation framework of $AF$ induced by ${\mathcal{A}}_x$ . If $F$ is an admissible set of $A{F}_x$ , then $F$ is an admissible set of $AF$ .

Proof.

Let $F$ be an admissible set of $A{F}_x$ . By definition, ${\mathcal{R}}_x=\mathcal{R}\cap ({\mathcal{A}}_x\times {\mathcal{A}}_x)$ , thus any attack between arguments of ${\mathcal{A}}_x$ in $\mathcal{R}$ is in ${\mathcal{R}}_x$ . Hence, $F$ is conflict-free in $AF$ . Moreover, $({\mathcal{A}}_x\cap F^{-})\subseteq F^{+}$ in $AF$ . By the construction of $A{F}_x$ , no argument in $\mathcal{A}\setminus {\mathcal{A}}_x$ is connected to $x$ and all arguments in ${\mathcal{A}}_x$ are connected to $x$ . Thus, ${\mathcal{A}}_x^{-}\setminus {\mathcal{A}}_x=\mathrm{\varnothing }$ . Hence, $(\mathcal{A}\cap F^{-})\subseteq F^{+}$ , which means that $F$ is self-defending in $AF$ . As a result, $F$ is an admissible set in $AF$ .

Lemma 5

Let $AF=⟨\mathcal{A},\mathcal{R}⟩$ be an argumentation framework, and let $x\in \mathcal{A}$ . Define ${\mathcal{A}}_x=\{y\mid y\text{ is connected to }x\text{ in }AF\}$ and let $A{F}_x=⟨{\mathcal{A}}_x,{\mathcal{R}}_x⟩$ be the sub-argumentation framework of $AF$ induced by ${\mathcal{A}}_x$ . If $F$ is a preferred extension of $AF$ , then $F\cap {\mathcal{A}}_x$ is a preferred extension of $A{F}_x$ .

Proof.

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

To show that $F\cap {\mathcal{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\cap {\mathcal{A}}_x⊊T$ . By Lemma 4, $T$ is also an admissible set in $AF$ . Let $S=F\setminus {\mathcal{A}}_x$ . We will show that $T\cup S$ is an admissible set of $AF$ . First, we show that $T\cup S$ is self-defending in $AF$ . Since $S^{-}\subseteq F^{+}\subseteq T^{+}$ and $T$ is an admissible set in $AF$ , $T\cup S$ is self-defending in $AF$ . Next, we show that $T\cup S$ is conflict-free in $AF$ . For the sake of contradiction, suppose the contrary. Since $S\subseteq F$ and $F$ is conflict-free in $AF$ , $S$ is conflict-free in $AF$ . We have $T$ is conflict-free in $A{F}_x$ . Thus, there exist $y\in T$ and $z\in S$ such that $(z,y)\in \mathcal{R}$ or $(y,z)\in \mathcal{R}$ . Since ${\mathcal{A}}_x^{-}\cap (\mathcal{A}\setminus {\mathcal{A}}_x)=\mathrm{\varnothing }$ and $T\subseteq {\mathcal{A}}_x$ , it follows that $(y,z)\in \mathcal{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 ${\mathcal{A}}_x^{-}\cap (\mathcal{A}\setminus {\mathcal{A}}_x)=\mathrm{\varnothing }$ and $S^{-}\cap T^{+}=\mathrm{\varnothing }$ , $S$ cannot be a subset of any admissible set in $AF$ . We have $S\subseteq F$ , which contradicts the fact that $F$ is an admissible set in $AF$ . Hence, $T\cup S$ is an admissible set in $AF$ . We have $F⊊T\cup S$ and $T\cup S$ is an admissible set in $AF$ . This contradicts the maximality of $F$ as a preferred extension of $AF$ . Therefore, $F\cap {\mathcal{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 $AF$ if and only if it is credulously (respectively, skeptically) accepted in $A{F}_x$ .

Theorem 8

Let $AF=⟨\mathcal{A},\mathcal{R}⟩$ be an argumentation framework, and let $x\in \mathcal{A}$ . Define ${\mathcal{A}}_x=\{y\mid y\text{ is connected to }x\text{ in }AF\}$ and let $A{F}_x=⟨{\mathcal{A}}_x,{\mathcal{R}}_x⟩$ be the sub-argumentation framework of $AF$ induced by ${\mathcal{A}}_x$ . Then, $x$ is credulously (respectively, skeptically) accepted in $AF$ 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.

$(\Rightarrow )$ 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\notin F$ . By Lemma 4, $F$ is an admissible set in $AF$ . Therefore, there exists a preferred extension $T$ of $AF$ such that $F\subseteq T$ . Let us show that $x\notin T$ . Suppose, for the sake of contradiction, that $x\in T$ . By Lemma 5, $T\cap {\mathcal{A}}_x$ is a preferred extension of $A{F}_x$ . Since $x\in T\cap {\mathcal{A}}_x$ and $x\notin F$ , it follows that $F⊊T\cap {\mathcal{A}}_x$ , which contradicts the fact that $F$ is a preferred extension of $A{F}_x$ . Therefore, $x\notin T$ , which means that $x$ is not skeptically accepted in $AF$ .

$(\Leftarrow )$ We proceed by contradiction. Suppose that $x$ is skeptically accepted in $A{F}_x$ but not in $AF$ . This means there exists a preferred extension $F$ in $AF$ such that $x\notin F$ . By Lemma 5, $F\cap {\mathcal{A}}_x$ is a preferred extension in $A{F}_x$ . Since $x\in {\mathcal{A}}_x$ and $x\notin F$ , it follows that $x\notin F\cap {\mathcal{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 $AF$ 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 $AF$ 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 $AF$ satisfies the property ${\mathrm{\Delta }}^{(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 $AF=⟨\mathcal{A},\mathcal{R}⟩$ be an argumentation framework that satisfies the property ${\mathrm{\Delta }}^{(p,1)}$ , and let $x\in \mathcal{A}$ . Define ${\mathcal{A}}_x=\{y\mid y\text{ is connected to }x\text{ in }AF\}$ and let $A{F}_x=⟨{\mathcal{A}}_x,{\mathcal{R}}_x⟩$ be the sub-argumentation framework of $AF$ induced by ${\mathcal{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[{\mathcal{A}}_1={\mathcal{A}}_x\setminus {\mathcal{A}}_x(C)]$ , containing all arguments except those in $C$ , and $A{F}_2[{\mathcal{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 ${\mathrm{\Delta }}^{(p,1)}$ , $C$ does not have outgoing attacks, that is, $({\mathcal{A}}_x(C){)}^{+}\setminus {\mathcal{A}}_x(C)=\mathrm{\varnothing }$ . Next, we distinguish two cases regarding the intersection $F^{+}\cap {\mathcal{A}}_x(C)$ :

1. (1)

If $F^{+}\cap {\mathcal{A}}_x(C)=\mathrm{\varnothing }$ , then $F\cup S_1$ and $F\cup S_2$ are conflict-free. Moreover, since $F$ is a stable extension, then $({\mathcal{A}}_1\setminus F)\subseteq F^{+}$ . As a result, $F\cup S_1$ and $F\cup S_2$ are the only preferred extensions of $A{F}_x$ .

(2)

If $F^{+}\cap {\mathcal{A}}_x(C)\ne \mathrm{\varnothing }$ , 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\in F_1$ and $z\in F_2$ such that $(y,z)\in {\mathcal{R}}_x$ or $(z,y)\in {\mathcal{R}}_x$ . Without loss of generality, assume that $(y,z)\in {\mathcal{R}}_x$ . Since $A{F}_1$ has only one preferred extension, then $y$ and $z$ must be in $C$ . Let $P=t,x_1,\dots ,y,z$ be a shortest path from $t\in F$ to $z$ . Such a path must exist because we have assumed that $F^{+}\cap {\mathcal{A}}_x(C)\ne \mathrm{\varnothing }$ . Since $({\mathcal{A}}_x(C){)}^{+}\setminus {\mathcal{A}}_x(C)=\mathrm{\varnothing }$ , $x_1$ cannot belong to any preferred extensions in $A{F}_x$ . We have $P$ is a short path, so $({\mathcal{A}}_x(P)\setminus t)\subseteq {\mathcal{A}}_x(C)$ and $({\mathcal{A}}_x(P)\setminus x_1)\cap F^{+}=\mathrm{\varnothing }$ . 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 ${\mathcal{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^{+}\cap {\mathcal{A}}_x(C)=\mathrm{\varnothing }$ , then we combine $F$ with $S_1$ and $S_2$ to form $F\cup S_1$ and $F\cup S_2$ , the two unique preferred extensions of $A{F}_2$ . However, if $F$ accepts arguments from $C$ , indicating $F^{+}\cap {\mathcal{A}}_x(C)\ne \mathrm{\varnothing }$ , $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 $AF=⟨\mathcal{A},\mathcal{R}⟩$ that satisfies the property ${\mathrm{\Delta }}^{(p,1)}$ and an argument $x\in \mathcal{A}$ , we want to check whether $x$ is credulously or skeptically accepted in $AF$ . Let $A{F}_x=⟨{\mathcal{A}}_x,{\mathcal{R}}_x⟩$ be a sub-argumentation framework of $AF$ induced by the set ${\mathcal{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 $AF$ 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 $AF=⟨\mathcal{A},\mathcal{R}⟩$ be an argumentation framework. If $AF$ satisfies the property ${\mathrm{\Delta }}^{(p,1)}$ , then:

1. (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 ${\mathrm{\Delta }}^{(2,2)}$ , both problems are hard to solve, as shown by Dunne. ¹⁵ Conversely, when the argumentation framework satisfies the property ${\mathrm{\Delta }}^{(1,q)}$ or ${\mathrm{\Delta }}^{(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 $AF$ 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 $AF$ among all those that are not attacked by $x$ in $AF$ ;

(2)

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

(3)

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

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 ${\delta }^{(a,b,c)}$ as follows.

Definition 2

Let $AF=⟨\mathcal{A},\mathcal{R}⟩$ be an argumentation framework. $AF$ satisfies the property ${\delta }^{(a,b,c)}$ if

$$\begin{array}{r}\mathrm{\forall }x\in \mathcal{A}|\{y\in \mathcal{A}|(y,x)\in \mathcal{R}\text{ and }(x,y)\notin \mathcal{R}\}|\le a,|\{y\in \mathcal{A}|(x,y)\in \mathcal{R}\text{ and }(y,x)\notin \mathcal{R}\}|\le b,\\ \text{ and }|\{y\in \mathcal{A}|(x,y)\in \mathcal{R}\text{ and }(y,x)\in \mathcal{R}\}|\le c.\end{array}$$

Note that $a$ , $b$ , and $c$ are bounded such that $0\le a,b,c\le |\mathcal{A}|$ , with $|\mathcal{A}|$ is the size of $\mathcal{A}$ .

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

Figure 5.

Argumentation frameworks highlighting the differences between the property ${\mathrm{\Delta }}^{(p,q)}$ and the property ${\delta }^{(a,b,c)}$ .

Let us start with the existing results in the literature. According to Definition 2, an argumentation framework satisfies the property ${\delta }^{(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 $AF=⟨\mathcal{A},\mathcal{R}⟩$ be an argumentation framework. If $AF$ satisfies the property ${\delta }^{(0,0,c)}$ , then:

1. (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 $AF=⟨\mathcal{A},\mathcal{R}⟩$ be an argumentation framework. If $AF$ satisfies the property ${\delta }^{(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.

$$\varphi =\underset{i=1}{\overset{m}{\bigwedge }}{C}_i=\underset{i=1}{\overset{m}{\bigwedge }}(p_{i,1}\vee p_{i,2}\vee p_{i,3}).$$

Note that $\varphi$ 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 $\mathrm{\neg }{u}_k$ . $\varphi$ is satisfiable if the $u_k$ ’s can be assigned Boolean values so that $\varphi$ is true. The 3-SAT problem is to determine whether $\varphi$ is satisfiable. The complexity of a 3-SAT problem is known to be NP-complete. ³⁸ From a given Boolean expression $\varphi$ , we construct an argumentation framework $AF=⟨\mathcal{A},\mathcal{R}⟩$ . The set of arguments $\mathcal{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 $\varphi$ . Note that $(t_1\vee t_2\vee t_3)$ is considered as the first clause of $\varphi$ , and $s$ as the last clause of $\varphi$ . Formally, $AF=⟨\mathcal{A},\mathcal{R}⟩$ defined as follows:

$$\begin{array}{rl}\mathcal{A}=& \{t_1,t_2,t_3,s,y\}\cup \{x_{i,j},y_{i,j}\mid 1\le i\le m\text{ and }1\le j\le 3\};\\ \mathcal{R}=& \{(t_j,y_{1,j})|1\le j\le 3\}\cup \{(y_{i,j},x_{i,j})|1\le i\le m\text{ and }1\le j\le 3\}\\ & \cup \{(x_{i,j},y_{i+1,k}),(y_{i+1,k},x_{i,j})|1\le i\le m-1\text{ and }1\le j,k\le 3\}\\ & \cup \{(x_{m,j},y),(y,x_{m,j})|1\le j\le 3\}\cup \{(y,s)\}\\ & \cup \{(x_{i,j},x_{k,l}),(x_{k,l},x_{i,j})\mid p_{i,j}=\mathrm{\neg }{p}_{k,l}\}.\end{array}$$

An illustration of this construction is given in Figure 6.

Figure 6.

Argumentation framework constructed from the Boolean expression in conjunctive normal form $C=(p_{1,1}\vee p_{1,2}\vee p_{1,3})\wedge (p_{2,1}\vee p_{2,2}\vee p_{2,3})$ with $p_{2,1}=\mathrm{\neg }{p}_{1,1}$ .

The construction of $AF$ is done in polynomial time in the size of $\varphi$ . 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 $AF$ satisfies the property ${\delta }^{(1,1,c)}$ . We will now show that this statement: there exists an admissible set $F$ in $AF$ includes the sink argument $s$ if and only if $\varphi$ is satisfiable.

Let us first show the “if” part of the statement. Suppose that there exists an admissible set $F$ in $AF$ such that $s\in F$ . By the construction of $AF$ , we have $(y,s)\in \mathcal{R}$ , and $y^{-}\setminus \{x_{m,1},x_{m,2},x_{m,3}\}=\mathrm{\varnothing }$ . Since $s$ is in $F$ and $F$ is a self-defending set, then it holds that $F\cap \{x_{m,1},x_{m,2},x_{m,3}\}\ne \mathrm{\varnothing }$ . As a result, at least one argument among those corresponding to the literals in the last clause of $\varphi$ is in $F$ . Furthermore, for each argument $x_{i,j}\in \mathcal{A}$ , there exists an argument $y_{i,j}\in \mathcal{A}$ such that $(y_{i,j},x_{i,j})\in \mathcal{R}$ and $y_{i,j}^{-}\setminus \{x_{i-1,1},x_{i-1,2},x_{i-1,3}\}=\mathrm{\varnothing }$ . Therefore, as $F$ is self-defending then $F\cap \{x_{i-1,1},x_{i-1,2},x_{i-1,3}\}\ne \mathrm{\varnothing }$ for all $2\le i\le m$ . This ensures that for each clause of $\varphi$ , 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}\in F$ to be true, the entire expression $\varphi$ is evaluated as true.

Now, let us show the “only if” part of the statement. Suppose that the Boolean expression $\varphi$ is satisfiable, meaning that there exists an assignment of Boolean values to the variables such that $\varphi$ is true. Based on this assignment, we can select the corresponding arguments in $AF$ 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 $\mathcal{A}$ denoted as $F$ . Since $\varphi$ is satisfiable, then at least one literal in each clause is true. Therefore, for all $1\le i\le m$ it holds that $F\cap \{x_{i,1},x_{i,2},x_{i,3}\}\ne \mathrm{\varnothing }$ , implying that $y\in F^{+}$ and $y_{i,j}\in F^{+}$ for all $1\le i\le m$ and $1\le j\le 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 $AF$ , and since $s$ is in $F$ , the existence of an admissible set including $s$ in $AF$ 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}_{SAT}$ .

We aim to transform the argumentation framework $A{F}_{SAT}$ into a new framework $AF$ that satisfies the ${\delta }^{(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}_{SAT}$ is equivalent to the existence of an admissible set $T$ in $AF$ , 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\le i\le m-1$ and $1\le j\le 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}_{SAT}$ , for all $1\le i\le m-1$ and $1\le j\le 3$ , we have $x_{i+1,j}^{-}\setminus 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}_{SAT}$ , if $x_{i+1,j}\in S$ , then $S\cap \{x_{i,1},x_{i,2},x_{i,3}\}\ne \mathrm{\varnothing }$ (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}_{SAT}$ , it is essential to maintain Condition A.

To preserve Condition A in the transformation, for each $i\in \{1,\dots ,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.

Figure 7.

Transformation of attacks between arguments in $A{F}_{SAT}$ . (a) Before transformation. (b) After transformation.

Consider a self-defending set $S$ in the framework constructed from $A{F}_{SAT}$ using this transformation. After this transformation, for $x_{i+1,1}$ , we have $x_{i+1,1}^{-}\setminus 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}\in S$ , then $S\cap \{x_{i,1},x_{i,2},x_{i,3}\}\ne \mathrm{\varnothing }$ . Similarly, for $x_{i+1,2}$ , we have $x_{i+1,2}^{-}\setminus 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}^{-}\cup a_{i,2}^{-}=\{x_{i,1},x_{i,2},x_{i,3}\}$ . So, if $x_{i+1,2}\in S$ , then $S\cap \{x_{i,1},x_{i,2},x_{i,3}\}\ne \mathrm{\varnothing }$ . For $x_{i+1,3}$ , we have $x_{i+1,3}^{-}\setminus 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}\in S$ , then $S\cap \{x_{i,1},x_{i,2},x_{i,3}\}\ne \mathrm{\varnothing }$ . We deduce that $S\cap \{x_{i,1},x_{i,2},x_{i,3}\}\ne \mathrm{\varnothing }$ if $x_{i+1,j}\in S$ for $1\le j\le 3$ . Thus, Condition A is preserved after the transformation.

Using this transformation, we construct a new argumentation framework $AF=⟨\mathcal{B},\mathcal{D}⟩$ from $A{F}_{SAT}=⟨\mathcal{A},\mathcal{R}⟩$ , where the number of symmetric attacks is reduced compared to $A{F}_{SAT}$ . Formally, $AF=⟨\mathcal{B},\mathcal{D}⟩$ is defined as follows.

$$\begin{array}{rl}\mathcal{B}=& \mathcal{A}\cup \{a_{i,j},b_{i,j}\mid 1\le i\le m-1\text{ and }1\le j\le 2\}\cup \{a,b\};\\ \mathcal{D}=& (\mathcal{R}\setminus (\{(y_{i+1,1},x_{i,1}),(x_{i,2},y_{i+1,2}),(y_{i+1,2},x_{i,2})|1\le i\le m-1\}\\ & \cup \{(y_{i+1,k},x_{i,j}),(x_{i,j},y_{i+1,k})|j\ne k\text{ with }1\le i\le m-1\text{ and }1\le j,k\le 3\}\\ & \cup \{(x_{m,j},y),(y,x_{m,j})\mid 1\le j\le 2\}))\\ & \bigcup (\{(x_{i,j},a_{i,1})\mid 1\le i\le m-1\text{ and }1\le j\le 2\}\\ & \cup \{(x_{i,j},a_{i,2})\mid 1\le i\le m-1\text{ and }2\le j\le 3\}\\ & \cup \{(a_{i,j},x_{i,j})\mid 1\le i\le m-1\text{ and }1\le j\le 2\}\\ & \cup \{(a_{i,1},b_{i,2}),(a_{i,2},b_{i,1})\mid 1\le i\le m-1\}\\ & \cup \{(b_{i,1},y_{i+1,j})\mid 1\le i\le m-1\text{ and }1\le j\le 2\}\\ & \cup \{(b_{i,2},y_{i+1,j}))\mid 1\le i\le m-1\text{ and }2\le j\le 3\}\\ & \cup \{(y_{i+1,j},b_{i,j})\mid 1\le i\le m-1\text{ and }1\le j\le 2\}\\ & \cup \{(x_{m,1},a),(a,x_{m,1}),(x_{m,2},a),(a,b),(b,y)\}).\end{array}$$

(1)

An illustration of this construction is given in Figure 8.

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}_{SAT}$ contains “s” if and only if there exists one in $AF$ contains “s.”

Theorem 12

Consider $AF=⟨\mathcal{B},\mathcal{D}⟩$ be the argumentation framework constructed from the framework $A{F}_{SAT}=⟨\mathcal{A},\mathcal{R}⟩$ using formula (1). Then there exists an admissible set $F\in ADM(A{F}_{SAT})$ such that $s\in F$ if and only if there exists an admissible set $T\in ADM(AF)$ such that $s\in T$ .

Proof.

We show the forward implication. Let $F$ be an admissible set of $A{F}_{SAT}$ and suppose that $s\in F$ . Then for all $1\le i\le m$ it holds that $F\cap \{x_{i,1},x_{i,2},x_{i,3}\}\ne \mathrm{\varnothing }$ . Consequently, this implies that in $AF$ , we have $F^{+}\cap \{a_{i,1},a_{i,2}\}\ne \mathrm{\varnothing }$ and $\{y_{i,1},y_{i,2},y_{i,3}\}\cap F=\mathrm{\varnothing }$ for all $1\le i\le m-1$ . Therefore, in the framework $AF$ , the set $F\cup \{b_{i,1},b_{i,2}\mid 1\le i\le m-1\}$ is conflict-free. Let $T$ be a subset of $\mathcal{B}$ constructed as follows:

$$T=F\cup \{b_{i,1}\mid a_{i,2}\in F^{+}\text{ with }1\le i\le m-1\}\cup \{b_{i,2}\mid a_{i,1}\in F^{+}\text{ with }1\le i\le m-1\}\cup \{b\mid a\in F^{+}\}.$$

We aim to show that $T$ is an admissible set in $AF$ . We have $s\in F$ then it follows that $y\notin F$ . We deduce that $b\notin \lambda (F)$ implies that $T$ is a conflict-free set in $AF$ . Now, it remains to show that $T$ is self-defending in $AF$ . To reach a contradiction, suppose that $T$ is not self-defending in $AF$ . By the construction of $T$ , it holds that $b_{i,1}\in T$ if $a_{i,2}\in F^{+}$ and $b_{i,2}\in T$ if $a_{i,1}\in F^{+}$ for all $1\le i\le m-1$ . Since in $AF$ , $b_{i,j}^{-}\setminus \{a_{i,j}\}=\mathrm{\varnothing }$ for all $1\le i\le m-1$ and $1\le j\le 2$ , it follows that $(\{b_{i,j}\mid 1\le i\le m-1\text{ and }1\le j\le 2\}\cap T{)}^{-}\subseteq T^{+}$ . Furthermore, by the construction of $T$ , $b\in T$ if $a\in T^{+}$ and since in $AF$ , $b^{-}\setminus \{a\}=\mathrm{\varnothing }$ , it follows that $b^{-}\subseteq T^{+}$ when $b\in T$ . Therefore, there must exist an $x_{i^{*},j^{*}}\in F$ such that $x_{i^{*},j^{*}}^{-}⊈T^{+}$ with $i^{*}\in \{1,\dots ,m\}$ and $j^{*}\in \{1,2,3\}$ , or $s^{-}⊈T^{+}$ . First, suppose that $s^{-}⊈T^{+}$ . Since in $AF$ , $s^{-}\setminus \{y\}=\mathrm{\varnothing }$ and $y^{-}=\{b,x_{m,3}\}$ , it follows that $T\cap \{b,x_{m,3}\}=\mathrm{\varnothing }$ . As $b\notin T$ , we can infer from the construction of $T$ that $a\notin F^{+}$ . As in $AF$ , $a^{-}=\{x_{m,1},x_{m,2}\}$ , which implies that $T\cap \{x_{m,1},x_{m,2},x_{m,3}\}=\mathrm{\varnothing }$ . This contradicts the fact that $F$ is an admissible set containing $s$ in $AF$ . Now, suppose that there exists an $x_{i^{*},j^{*}}\in F$ such that $x_{i^{*},j^{*}}^{-}⊈T^{+}$ with $i^{*}\in \{1,\dots ,m\}$ and $j^{*}\in \{1,2,3\}$ . In $AF$ , 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^{*}}\notin F\subseteq T$ . In $A{F}_{SAT}$ , $x_{1,j^{*}}\in 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}_{SAT}$ . 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\cap \{x_{i^{*}-1,1},x_{i^{*}-1,3},b_{i^{*}-1,1},b_{i^{*}-1,2}\}=\mathrm{\varnothing }$ . By the construction of $T$ , we have $b_{i^{*}-1,1}\in T$ if $a_{i^{*}-1,2}\in F^{+}$ and $b_{i^{*}-1,2}\in T$ if $a_{i^{*}-1,1}\in F^{+}$ . It follows that $F^{+}\cap \{a_{i^{*}-1,1},a_{i^{*}-1,2}\}=\mathrm{\varnothing }$ . As in $AF$ , $\{a_{i^{*}-1,1},a_{i^{*}-1,2}{\}}^{-}=\{x_{i^{*}-1,1},x_{i^{*}-1,2},x_{i^{*}-1,3}\}$ then $F\cap \{x_{i^{*}-1,1},x_{i^{*}-1,2},x_{i^{*}-1,3}\}=\mathrm{\varnothing }$ . This contradicts the fact that $F$ is an admissible set containing $s$ in $AF$ . Thus, in both cases, we arrive at a contradiction; we can conclude that $T$ must be self-defending in $AF$ . Therefore, $T$ is an admissible set in $AF$ containing $s$ .

Now, we show the reverse implication. Let $F$ be an admissible set of $AF$ such that $s\in F$ . Since $s\in F$ , $(y,s)\in \mathcal{D}$ and $y^{-}=\{b,x_{m,3}\}$ , then $F\cap \{b,x_{m,3}\}\ne \mathrm{\varnothing }$ . If $b\in F$ , then as $(a,b)\in \mathcal{D}$ and $a^{-}=\{x_{m,1},x_{m,2}\}$ , it follows that $F\cap \{x_{m,1},x_{m,2}\}\ne \mathrm{\varnothing }$ . Hence, $F\cap \{x_{m,1},x_{m,2},x_{m,3}\}\ne \mathrm{\varnothing }$ . Additionally, in $AF$ , for all $2\le i\le m$ and $1\le j\le 3$ , we have $(y_{i,j},x_{i,j})\in \mathcal{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\le i\le m-1$ , $F\cap \{x_{i,1},x_{i,3},b_{i,1},b_{i,2}\}\ne \mathrm{\varnothing }$ . Similarly, for all $1\le i\le m-1$ and $1\le j\le 2$ in $AF$ , we have $(a_{i,j},b_{i,j})\in \mathcal{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\le i\le m$ , $F\cap \{x_{i,1},x_{i,2},x_{i,3}\}\ne \mathrm{\varnothing }$ . Furthermore, $y_{1,j}^{-}=\{t_j\}$ for all $1\le j\le 3$ , so $F\cap \{t_1,t_2,t_3\}\ne \mathrm{\varnothing }$ . As a result, the set

$$T=\{s\}\cup (F\cap \{x_{i,j}\mid 1\le i\le m\text{ and }1\le j\le 3\})\cup (F\cap \{t_1,t_2,t_3\})$$

is self-defending in $A{F}_{SAT}$ . Thus, $T$ is an admissible set in $A{F}_{SAT}$ if it is conflict-free in $A{F}_{SAT}$ . By the construction of $AF$ , $(x_{i,j},x_{k,l})\in \mathcal{D}$ if and only if $(x_{i,j},x_{k,l})\in \mathcal{R}$ with $1\le i,k\le m$ and $1\le j,l\le 3$ . Hence, $T$ is conflict-free in $A{F}_{SAT}$ . We deduce that $T$ is an admissible set in $A{F}_{SAT}$ that contains $s$ . The proof follows.

Consider $AF=⟨\mathcal{A},\mathcal{R}⟩$ , the argumentation framework constructed from $A{F}_{SAT}$ using formula (1). This framework $AF$ satisfies the property ${\delta }^{(1,1,c)}$ . Furthermore, all arguments in $AF$ , except those in the set $\{x_{i,j}\in \mathcal{A}\mid 1\le i\le m\text{ and }1\le j\le 3\}$ , have at most one symmetric attack.

In order to obtain an argumentation framework that satisfies the property ${\delta }^{(1,1,1)}$ , in the following step, we will remove all symmetric attacks between the arguments of the set $\{x_{i,j}\in \mathcal{A}\mid 1\le i\le m\text{ and }1\le j\le 3\}$ . Let $x_{i^{*},j^{*}}$ , with $i^{*}\in \{1,\dots ,m\}$ and $j^{*}\in \{1,\dots ,3\}$ , be an argument of $AF$ . 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},\dots ,x_{h_n,l_n}$ .

To maintain the existence of an admissible set $F$ that includes “ $s$ ” in $AF$ 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^{*}}\in S$ , then $S\cap \{x_{h_1,l_1},\dots ,x_{h_n,l_n}\}=\mathrm{\varnothing }$ . The idea here involves adding new arguments $\{z_{i^{*},1},\dots ,z_{i^{*},n},t_{i^{*},1},\dots ,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\le f\le n$ . Additionally, we add the attacks and $(z_{i^{*},f},t_{i^{*},f})$ for all $1\le f\le n$ , $(t_{i^{*},f},z_{i^{*},f+1})$ for all $1\le f\le 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.

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}^{-}\setminus \{z_{i^{*},f}\}=\mathrm{\varnothing }$ for all $1\le f\le n$ . Consider an admissible set $S$ in the framework constructed from $AF$ using this transformation. If $x_{i^{*},j^{*}}$ belongs to $S$ , then $\{z_{i^{*},1},\dots ,z_{i^{*},n}\}\subseteq S$ . Since $\{x_{h_1,l_1},\dots ,x_{h_n,l_n}\}\subseteq \lambda (\{z_{i^{*},1},\dots ,z_{i^{*},n}\})$ , then $S\cap \{x_{h_1,l_1},\dots ,x_{h_n,l_n}\}=\mathrm{\varnothing }$ .

Using this transformation on $AF$ , 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 ${\delta }^{(1,1,1)}$ .

Theorem 13

Let $AF=⟨\mathcal{A},\mathcal{R}⟩$ be an argumentation framework. If $AF$ satisfies the property ${\delta }^{(1,1,1)}$ then CredA is $NP$ -complete.

Proof.

Let $AF=⟨\mathcal{A},\mathcal{R}⟩$ be an argumentation framework constructed from the argumentation framework $A{F}_{SAT}$ using formula (1). Define $A{F}^{(k)}=⟨{\mathcal{A}}^{(k)},{\mathcal{R}}^{(k)}⟩$ as an argumentation framework constructed constructed from $A{F}^{(k-1)}=⟨{\mathcal{A}}^{(k-1)},{\mathcal{R}}^{(k-1)}⟩$ with $A{F}^{(0)}=AF$ as follows.

First, we define the set ${\text{Sym}}^{(k)}(x_{i,j})=\{x_{h,l}\in {\mathcal{A}}^{(k)}|(x_{i,j},x_{h,l})\in {\mathcal{R}}^{(k)}\}\cup \{z_{h,l}\in {\mathcal{A}}^{(k)}|(x_{i,j},z_{h,l})\in {\mathcal{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^{*}}\in \mathcal{A}$ with $i^{*}\in \{1,\dots ,m\}$ and $j^{*}\in \{1,2,3\}$ be the first argument in $A{F}^{(k-1)}$ for which ${\text{Sym}}^{(k-1)}(x_{i^{*},j^{*}})$ is not empty. In other words, if there exists another argument $x_{h^{*},l^{*}}\in \mathcal{A}$ with $h^{*}\in \{1,\dots ,m\}$ and $l^{*}\in \{1,2,3\}$ for which ${\text{Sym}}^{(k-1)}(x_{i^{*},j^{*}})$ is not empty, then $1\le i^{*}\le h^{*}\le m$ and $1\le j^{*}<l^{*}\le 3$ when $i^{*}=h^{*}$ .

Suppose that the elements of ${\text{Sym}}^{(k-1)}(x_{i^{*},j^{*}})$ are ordered as follows: $x_{h_1,l_1},\dots ,x_{h_n,l_n},z_{h_{n+1},l_{n+1}},\dots ,z_{h_r,l_r},$ with $r$ is the size of ${\text{Sym}}^{(k-1)}(x_{i^{*},j^{*}})$ . Consider the framework $A{F}^{(k)}=⟨{\mathcal{A}}^{(k)},{\mathcal{R}}^{(k)}⟩$ constructed from $A{F}^{(k-1)}$ by introducing new arguments $\{z_{i^{*},1},\dots ,z_{i^{*},r}\}$ and $\{t_{i^{*},1},\dots ,t_{i^{*},r}\}$ . Formally $A{F}^{(k)}$ is defined as follows:

$$\begin{array}{rl}{\mathcal{A}}^{(k)}=& {\mathcal{A}}^{(k-1)}\cup \{z_{i^{*},1},\dots ,z_{i^{*},r},t_{i^{*},1},\dots ,t_{i^{*},r}\};\\ {\mathcal{R}}^{(k)}=& ({\mathcal{R}}^{(k-1)}\setminus (\{(x_{h_f,l_f},x_{i^{*},j^{*}}),(x_{i^{*},j^{*}},x_{h_f,l_f})\mid 1\le f\le n\}\\ & \cup \{(z_{h_f,l_f},x_{i^{*},j^{*}}),(x_{i^{*},j^{*}},z_{h_f,l_f})\mid n+1\le f\le r\}\\ & \cup \{(y_{i^{*},j^{*}},x_{i^{*},j^{*}})\}))\\ \bigcup & (\{(y_{i^{*},j^{*}},z_{i^{*},1})\}\\ & \cup \{(z_{i^{*},f},x_{h_f,l_f}),(x_{h_f,l_f},z_{i^{*},f})\mid 1\le f\le n\}\\ & \cup \{(z_{i^{*},f},z_{h_f,l_f}),(z_{h_f,l_f},z_{i^{*},f})\mid n+1\le f\le r\}\\ & \cup \{(z_{i^{*},f},t_{i^{*},f})\mid 1\le f\le r\}\\ & \cup \{(t_{i^{*},f},z_{i^{*},f+1})\mid 1\le f\le r-1\}\cup \{(t_{i^{*},r},x_{i^{*},j^{*}})\}).\end{array}$$

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}\in \mathcal{A}$ with $1\le i\le m$ and $1\le j\le 3$ has ${\text{Sym}}^{(n)}(x_{i,j})\ne \mathrm{\varnothing }$ . 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 $AF$ . Moreover, $A{F}^{(n)}$ satisfies the property ${\delta }^{(1,1,1)}$ . Now, we aim to show this statement: There exists an admissible set $F$ that includes “ $s$ ” in $AF$ if and only if there exists an admissible set $T$ in $A{F}^{(n)}$ that includes “ $s$ .”

Figure 10.

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

Figure 11.

Transforming the argumentation presented in Figure 8 to satisfy the ${\mathrm{\Delta }}^{(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\le k\le n$ . Let $x_{i^{*},j^{*}}\in \mathcal{A}$ be the first argument in $A{F}^{(k)}$ for which ${\text{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^{*}}\notin F$ . Now, suppose that $x_{i^{*},j^{*}}\in F$ , and let $T=F\cup \{z_{i^{*},1},\dots ,z_{i^{*},r}\}$ be a subset of ${\mathcal{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^{*}}\in F$ , as $({\text{Sym}}^{(k)}(x_{i^{*},j^{*}})\cup \{y_{i^{*},j^{*}}\})\subseteq \lambda (x_{i^{*},j^{*}})$ , it holds that $F\cap ({\text{Sym}}^{(k)}(x_{i^{*},j^{*}})\cup \{y_{i^{*},j^{*}}\})=\mathrm{\varnothing }$ . Furthermore, following the construction of $A{F}^{(k+1)}$ , we observe that $(\lambda (\{z_{i^{*},1},\dots ,z_{i^{*},r}\})\cap {\mathcal{A}}^{(k)})\setminus ({\text{Sym}}^{(k)}(x_{i^{*},j^{*}})\cup \{y_{i^{*},j^{*}}\})=\mathrm{\varnothing }$ , 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^{*}}^{+}\setminus x_{i^{*},j^{*}}^{-}=\{y_{i^{*},j^{*}}\}$ , and based on our supposition that $F$ is self-defending in $A{F}^{(k)}$ with $x_{i^{*},j^{*}}\in F$ , it implies that $y_{i^{*},j^{*}}\in F^{+}$ , hence $z_{i^{*},1}^{-}\in F^{+}$ . Furthermore, in $A{F}^{(k+1)}$ , we have $x_{i^{*},j^{*}}^{-}=\{t_{i^{*},r}\}$ , $\{z_{i^{*},2},\dots ,z_{i^{*},r}{\}}^{-}=\{t_{i^{*},1},\dots ,t_{i^{*},r-1}\}$ , and $\{t_{i^{*},1},\dots ,t_{i^{*},r}\}\subseteq \{z_{i^{*},1},\dots ,z_{i^{*},r}{\}}^{+}$ , leading to $(\{z_{i^{*},1},\dots ,z_{i^{*},r}\}\cup \{x_{i^{*},j^{*}}\}{)}^{-}\subseteq T^{+}$ . As $(F\setminus (\{z_{i^{*},1},\dots ,z_{i^{*},r}\}\cup \{x_{i^{*},j^{*}}\}){)}^{-}\subseteq F^{+}\subseteq 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\subseteq T$ if $F$ is an admissible set in $AF$ .

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\le k\le n$ . Let $x_{i^{*},j^{*}}\in \mathcal{A}$ be the first argument in $A{F}^{(k-1)}$ for which ${\text{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^{*}}\notin F$ . Suppose now that $x_{i^{*},j^{*}}\in F$ and let $T=F\setminus \{z_{i^{*},1},\dots ,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^{*}})\in {\mathcal{R}}^{(k)}$ and $t_{i^{*},r}^{-}\setminus \{z_{i^{*},r}\}=\mathrm{\varnothing }$ . From this, we can conclude that $z_{i^{*},r}\in F$ . Furthermore, in $A{F}^{(k)}$ , we have $(t_{i^{*},f},z_{i^{*},f+1})\in {\mathcal{R}}^{(k)}$ for every $1\le f\le r-1$ and $t_{i^{*},f}^{-}\setminus \{z_{i^{*},f-1}\}=\mathrm{\varnothing }$ for every $2\le f\le r$ . Consequently, we can deduce that $\{z_{i^{*},1},\dots ,z_{i^{*},r}\}\subseteq F$ . By supposition $F$ is conflict-free in $A{F}^{(k)}$ and given that in $A{F}^{(k)}$ , ${\text{Sym}}^{(k-1)}(x_{i^{*},j^{*}})\cup \{y_{i^{*},j^{*}}\}\subseteq \lambda (\{z_{i^{*},1},\dots ,z_{i^{*},r}\})$ , we can deduce that $F\cap ({\text{Sym}}^{(k-1)}(x_{i^{*},j^{*}})\cup \{y_{i^{*},j^{*}}\})=\mathrm{\varnothing }$ . For the suck of simplicity, we define $N={\text{Sym}}^{(k-1)}(x_{i^{*},j^{*}})\cup \{x_{i^{*},j^{*}},y_{i^{*},j^{*}}\}$ . By the construction of $A{F}^{(k)}$ , we have ${\mathcal{R}}^{(k-1)}\setminus {\mathcal{R}}^{(k)}\subseteq N\times 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\setminus \{x_{i,j}\}{)}^{-}\subseteq T^{+}$ . Thus, $T$ is self-defending in $A{F}^{(k)}$ if $x_{i^{*},j^{*}}^{-}\subseteq T^{+}$ . We have $(y_{i^{*},j^{*}},z_{i^{*},1})\in {\mathcal{R}}^{(k)}$ , and $y_{i^{*},j^{*}}^{-}\cap ({\mathcal{A}}^{(k)}\setminus \mathcal{A})=\mathrm{\varnothing }$ . As, $F$ is self-defending in $A{F}^{(k)}$ and $z_{i^{*},1}\in F$ then we can deduce that $x_{i^{*},j^{*}}^{-}=\{y_{i^{*},j^{*}}\}\subseteq 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 $AF=⟨\mathcal{A},\mathcal{R}⟩$ , the framework constructed in the proof of Theorem 13. We aim to construct an argumentation framework from $AF$ that satisfies the property ${\delta }^{(2,2,0)}$ while preserving the existence of an admissible set $F$ in $AF$ such that $s\in 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\le i,k\le m$ and $1\le j,l\le 3$ in $AF$ . Suppose that there is a symmetric attack between them, that is, $(z_{i,j},z_{k,l})\in \mathcal{R}$ and $(z_{k,l},z_{i,j})\in \mathcal{R}$ . Therefore, if $F$ is an admissible set in $AF$ such that $z_{i,j}\in F$ , then $z_{k,l}\notin 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.

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}\in F$ , then $c_{i,j}\in F$ . Since $c_{i,j}$ attacks $z_{k,l}$ , it follows that $z_{k,l}\notin F$ . Moreover, $z_{k,l}^{-}=\{d_{i,j}\}$ , so $d_{i,j}\in 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 $AF$ .

By applying this transformation to $AF$ , we show in the following theorem that the computational complexity of the problem CredA persists even within argumentation frameworks that satisfy the property ${\delta }^{(2,2,0)}$ .

Theorem 14

Let $AF=⟨\mathcal{A},\mathcal{R}⟩$ be an argumentation framework. If $AF$ satisfies the property ${\delta }^{(2,2,0)}$ then CredA is NP-complete.

Proof.

Consider $AF=⟨\mathcal{A},\mathcal{R}⟩$ be the framework constructed in the proof of Theorem 13. Let $A{F}^{\prime }=⟨\mathcal{B},\mathcal{D}⟩$ be an argumentation framework constructed from $AF$ using the following formula:

$$\begin{array}{rl}\mathcal{B}=& \mathcal{A}\cup \{c_{i,j},c_{k,l},d_{i,j},d_{k,l}\mid (z_{i,j},z_{k,l})\in \mathcal{R}\text{ with }1\le i,k\le m\text{ and }1\le j,l\le 3\};\\ \mathcal{D}=& (\mathcal{R}\setminus (\{(z_{i,j},z_{k,l}),(z_{k,l},z_{i,j})\mid 1\le i,k\le m\text{ and }1\le j,l\le 3\}\\ & \cup \{(a_{i,j},x_{i,j}),(y_{i+1,j},b_{i,j})\mid 1\le i\le m-1\text{ and }1\le j\le 2\}\\ & \cup \{(y_{i+1,3},x_{i,3})\mid 1\le i\le m-1\}\cup \{(a,x_{m,1}),(y,x_{m,3})\}))\\ & \cup \{(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})\mid (z_{i,j},z_{k,l})\in \mathcal{R}\\ & \text{ with }1\le i,k\le m\text{ and }1\le j,l\le 3\}.\end{array}$$

(2)

Figure 13 provides an illustration of this construction.

Figure 13.

Transforming the argumentation presented in Figure 11 to satisfy the ${\mathrm{\Delta }}^{(2,2,0)}$ property by applying formula (2).

We show this statement: there exists an admissible set $F\in ADM(AF)$ such that $s\in F$ if and only if there exists an admissible set $T\in ADM(A{F}^{\prime })$ such that $s\in T$ .

First, we show the “if” part of the statement. Let $F$ be an admissible set of $AF$ with $s\in F$ . We define the set $T=F\cup \{c_{i,j},d_{i,j}\mid z_{i,j}\in F\text{ with }1\le i\le m\text{ and }1\le j\le 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}^{\prime }$ . Let $z_{i^{*},j^{*}}\in F$ with $i^{*}\in \{1,\dots ,m\}$ and $j^{*}\in \{1,2,3\}$ . In $AF$ , there exists a unique argument $z_{k^{*},l^{*}}\in \mathcal{A}$ with $k^{*}\in \{1,\dots ,m\}$ and $l^{*}\in \{1,2,3\}$ such that $(z_{i^{*},j^{*}},z_{k^{*},l^{*}})\in \mathcal{R}$ . Since $F$ is conflict-free in $AF$ , then $z_{k^{*},l^{*}}\notin F$ . It follows that $c_{k^{*},l^{*}},d_{k^{*},l^{*}}\notin T$ . Since in $A{F}^{\prime }$ , $\lambda (\{c_{i^{*},j^{*}},d_{i^{*},j^{*}}\})\setminus \{z_{k^{*},l^{*}},c_{k^{*},l^{*}},d_{k^{*},l^{*}}\}=\mathrm{\varnothing }$ and given that $F$ is conflict-free in $AF$ , we deduce that $T$ is conflict-free in $A{F}^{\prime }$ . Now, it remains to show that $T$ is self-defending in $A{F}^{\prime }$ . For the suck of simplicity, we define $N=\mathcal{A}\setminus \{z_{i,j}\mid 1\le i\le m\text{ and }1\le j\le 3\}$ . By the construction of $A{F}^{\prime }$ , we have $\mathcal{D}\cap (N\times N)=\mathcal{R}$ . Thus, $T$ is self-defending in $A{F}^{\prime }$ if for all $1\le i,k\le m\text{ and }1\le j,l\le 3$ the following condition holds:

$$\text{ if }(z_{i,j},z_{k,l})\in \mathcal{R}\text{ and }{z}_{i,j}\in F\text{ then }(\{z_{k,l}\}\cup (\{z_{i,j},c_{i,j},d_{i,j}\}{)}^{-})\subseteq T^{+}.$$

Let $z_{i^{*},j^{*}},z_{k^{*},l^{*}}\in \mathcal{A}$ such that $(z_{i^{*},j^{*}},z_{k^{*},l^{*}})\in \mathcal{R}$ and suppose that $z_{i^{*},j^{*}}\in F$ . By the construction of $A{F}^{\prime }$ , we have $(\{z_{i^{*},j^{*}}\}\times \mathcal{B})\cap D\setminus \mathcal{R}=\{(z_{i^{*},j^{*}},c_{k^{*},l^{*}}),(d_{k^{*},l^{*}},z_{i^{*},j^{*}})\}$ . Thus, $z_{i^{*},j^{*}}^{-}\subseteq T^{+}$ if $d_{k^{*},l^{*}}\in T^{+}$ . In $A{F}^{\prime }$ , we have $\{c_{i^{*},j^{*}},d_{i^{*},j^{*}}{\}}^{-}\setminus \{z_{k^{*},l^{*}},c_{k^{*},l^{*}},d_{k^{*},l^{*}}\}=\mathrm{\varnothing }$ and $\{z_{k^{*},l^{*}},c_{k^{*},l^{*}},d_{k^{*},l^{*}}\}\subseteq \{z_{i^{*},j^{*}},c_{i^{*},j^{*}},d_{i^{*},j^{*}}{\}}^{+}$ , then $\{z_{i^{*},j^{*}},c_{i^{*},j^{*}},d_{i^{*},j^{*}}{\}}^{-}\subseteq T^{+}$ . As a result, $T$ is self-defending in $A{F}^{\prime }$ implying that $T$ is admissible set in $A{F}^{\prime }$ .

Now, we proceed to show the “only if” part of the statement. Let $F$ be an admissible set of $A{F}^{\prime }$ . We define $T=F\cap \mathcal{A}$ , given that $s$ is an element of $\mathcal{A}$ , it is apparent that $s$ is also an element of $T$ . We will show that $T$ is an admissible set of $AF$ . For the sake of contradiction, suppose the contrary, that is, $T$ is not admissible in $AF$ . It follows by definition that $T$ is not self-defending or not conflict-free in $AF$ . First, suppose that $T$ is not self-defending. Since $\mathcal{B}\setminus \mathcal{A}=\{c_{i,j},d_{i,j}\mid 1\le i\le m\text{ and }1\le j\le 3\}$ and $(\{c_{i,j},d_{i,j}\mid 1\le i\le m\text{ and }1\le j\le 3{\}}^{+}\cap \mathcal{A})\subseteq \{z_{i,j}\mid 1\le i\le m\text{ and }1\le j\le 3\}$ . We deduce that there exists $z_{i^{*},j^{*}}\in \mathcal{A}$ with $i^{*}\in \{1,\dots ,m\}$ and $j^{*}\in \{1,2,3\}$ such that $z_{i^{*},j^{*}}\notin T^{+}$ . Let $z_{k^{*},l^{*}}\in \mathcal{A}$ with $k^{*}\in \{1,\dots ,m\}$ and $l^{*}\in \{1,2,3\}$ such that $(z_{k^{*},l^{*}},z_{i^{*},j^{*}})\in \mathcal{R}$ . Not that $z_{k^{*},l^{*}}$ exists and unique in $AF$ . Since $z_{i^{*},j^{*}}\notin T^{+}$ it follows that $z_{k^{*},l^{*}}\notin T$ or equivalently $z_{k^{*},l^{*}}\notin F$ . Given that $F$ is self-defending in $A{F}^{\prime }$ by assumption, and in $A{F}^{\prime }$ , $z_{i^{*},j^{*}}^{-}\cap (\mathcal{B}\setminus \mathcal{A})=d_{k^{*},l^{*}}$ , we conclude that $d_{k^{*},l^{*}}\in F$ . In $A{F}^{\prime }$ , we have $d_{k^{*},l^{*}}^{-}⊈(\mathcal{B}\setminus \{z_{k^{*},l^{*}}\}{)}^{+}$ , and as, $z_{k^{*},l^{*}}\notin F$ then we obtain a contradiction with the fact that $F$ is a self-defending set in $A{F}^{\prime }$ . We deduce that $T$ is a self-defending set in $AF$ . Therefore, $T$ is not conflict-free in $AF$ . We have $\mathcal{R}\setminus \{(z_{k,l},z_{i,j}),(z_{i,j},z_{k,l})\mid 1\le i,k\le m\text{ and }1\le j,l\le 3\}\subseteq \mathcal{D}$ . By supposition, $F$ is conflict-free in $A{F}^{\prime }$ , then there exists $z_{k^{*},l^{*}},z_{i^{*},j^{*}}\in T$ such that $(z_{k^{*},l^{*}},z_{i^{*},j^{*}})\in \mathcal{R}$ . By the construction of $A{F}^{\prime }$ , there exists $d_{i^{*},j^{*}}\in \mathcal{B}$ such that $(d_{i^{*},j^{*}},z_{k^{*},l^{*}})\in \mathcal{D}$ . Moreover, $d_{i^{*},j^{*}}^{-}=\{c_{k^{*},l^{*}}\}$ . Since $F$ is self-defending in $A{F}^{\prime }$ and $z_{k^{*},l^{*}}\in F$ then $c_{k^{*},l^{*}}\in F$ . Thus $\{z_{i^{*},j^{*}},c_{k^{*},l^{*}}\}\subseteq F$ and as $(z_{i^{*},j^{*}},c_{k^{*},l^{*}})\in \mathcal{D}$ then we obtain a contradiction with the fact that $F$ is conflict-free in $A{F}^{\prime }$ . In both cases, we obtain a contradiction. Therefore, $T$ is an admissible set of $AF$ . This concludes the proof.

Note that the argumentation frameworks satisfying the property ${\delta }^{(1,b,0)}$ and ${\delta }^{(a,1,0)}$ are a subclass of the argumentation frameworks satisfying the property ${\mathrm{\Delta }}^{(a,1)}$ and ${\mathrm{\Delta }}^{(1,b)}$ , respectively. Therefore, both CredA and SkepA problems can be solved in polynomial time for this class of argumentation frameworks (Table 1).

Table 1.

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

Satisfied property by the argumentation framework	CredA	SkepA	Reference
${\mathrm{\Delta }}^{(2,2)}$	NP-complete	$\prod _2^p$ -complete	Dunne 15
${\mathrm{\Delta }}^{(p,1)}$	Polynomial	Polynomial	Theorem 7
${\mathrm{\Delta }}^{(1,q)}$	Polynomial	Polynomial	Theorem 9
${\delta }^{(1,1,1)}$	NP-complete	–	Theorem 13
${\delta }^{(2,2,0)}$	NP-complete	–	Theorem 14
${\delta }^{(p,1,0)}$	Polynomial	Polynomial	Theorem 7
${\delta }^{(1,q,0)}$	Polynomial	Polynomial	Theorem 9
${\delta }^{(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

This paper has presented a comprehensive exploration of the relationship between bounded in-degree and out-degree in abstract argumentation frameworks and the computational complexity of the CredA and SkepA decision problems under preferred extensions. Our research builds upon the existing literature, showing that even when in-degree and out-degree are strictly limited to $2$ $(p=q=2)$ , the computational complexities of CredA and SkepA persist.

Building upon these established results, we have unveiled new insights into the impact of additional constraints on the argumentation framework. Notably, we have shown when either “ $p$ ” or “ $q$ ” is restricted to $1$ , the problems CredA   and SkepA   can be efficiently solved in polynomial time. Furthermore, a comprehensive analysis of additional constraints explored the quantities “ $a$ ,” “ $b$ ,” and “ $c$ ,” representing distinct attack relationships between arguments. Surprisingly, even when all these quantities are strictly limited to $1$ , the computational complexity of CredA still persists. Additionally, we investigated the influence of symmetric attacks by fixing “c” to zero and setting “ $a$ ” and “ $b$ ” to $2$ , yet the complexity of CredA endured under this variation as well.

Overall, the results suggest that, within the context of CredA and SkepA problems, the structural constraints imposed by the bounded degrees do not significantly affect the computational requirements. This means the importance of further exploring other aspects of argumentation frameworks to uncover additional facets of their computational characteristics.