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

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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"> <mml:mo stretchy="false">(</mml:mo> <mml:mi>p</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:math> and out-degree <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"> <mml:mo stretchy="false">(</mml:mo> <mml:mi>q</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:math> of the arguments are restricted to <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"> <mml:mn>2</mml:mn> </mml:math> . 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 “ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"> <mml:mi>p</mml:mi> </mml:math> ” or “ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"> <mml:mi>q</mml:mi> </mml:math> ” is restricted to <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"> <mml:mn>1</mml:mn> </mml:math> , both problems CredA and SkepA can be solved in polynomial time. Subsequently, we impose additional constraints on the argumentation framework by analyzing the quantities “ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"> <mml:mi>a</mml:mi> </mml:math> ,” “ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"> <mml:mi>b</mml:mi> </mml:math> ,” and “ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"> <mml:mi>c</mml:mi> </mml:math> .” For an argumentation framework <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"> <mml:mi>A</mml:mi> <mml:mi>F</mml:mi> </mml:math> and all arguments “ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"> <mml:mi>x</mml:mi> </mml:math> ” of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"> <mml:mi>A</mml:mi> <mml:mi>F</mml:mi> </mml:math> , the parameter “ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"> <mml:mi>a</mml:mi> </mml:math> ” indicates the maximum number of attackers that any argument “ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"> <mml:mi>x</mml:mi> </mml:math> ” can have among all those that are not attacked by “ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"> <mml:mi>x</mml:mi> </mml:math> ” <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"> <mml:mi>A</mml:mi> <mml:mi>F</mml:mi> </mml:math> , “ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"> <mml:mi>b</mml:mi> </mml:math> ” indicates the maximum number of arguments that any argument “ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"> <mml:mi>x</mml:mi> </mml:math> ” attacks among all those that do not attack “ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"> <mml:mi>x</mml:mi> </mml:math> ”, and “ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"> <mml:mi>c</mml:mi> </mml:math> ” denotes the maximum number of arguments that any argument “ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"> <mml:mi>x</mml:mi> </mml:math> ” attacks among those that attack “ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"> <mml:mi>x</mml:mi> </mml:math> ”. Surprisingly, even when all these quantities are restricted to <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"> <mml:mn>1</mml:mn> </mml:math> , the computational complexity of CredA persists. Furthermore, we explore the influence of symmetric attacks by fixing “ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"> <mml:mi>c</mml:mi> </mml:math> ” to zero, while setting “ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"> <mml:mi>a</mml:mi> </mml:math> ” and “ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline"