Abstract

We explore the computational complexity of justification, stability and relevance in incomplete argumentation frameworks (IAFs). IAFs are abstract argumentation frameworks that encode qualitative uncertainty by distinguishing between certain and uncertain arguments and attacks. These IAFs can be completed by deciding for each uncertain argument or attack whether it is present or absent. Such a completion is an abstract argumentation framework, for which it can be decided which arguments are acceptable under a given semantics. The justification status of an argument in a completion then expresses whether the argument is accepted (in), not accepted because it is attacked by an accepted argument (out) or neither (undec). For a given IAF and certain argument, the justification status of that argument need not be the same in all completions. This is the issue of stability, where an argument is stable if its justification status is the same in all completions. For arguments that are not stable in an IAF, the relevance problem is of interest: which uncertain arguments or attacks should be investigated for the argument to become stable? In this paper, we define justification, stability and relevance for IAFs and provide a complexity analysis for these problems under grounded, complete, preferred and stable semantics.