This work focuses on generalizing the existence problems for extensions in abstract argumentation to incomplete argumentation frameworks. In this extended model, incomplete or conflicting knowledge about the state of the arguments and attacks are allowed. We propose possible and necessary variations of the existence and nonemptiness problems, originally defined for (complete) argumentation frameworks, to extend these problems to incomplete argumentation frameworks. While the computational complexity of existence problems is already known for the standard model, we provide a full analysis of the complexity for incomplete argumentation frameworks using the most prominent semantics, namely, the conflict-free, admissible, complete, grounded, preferred, and stable semantics. We show that the complexity rises from NP-completeness to ∏p2-completeness for most “necessary” problem variants when uncertainty is allowed.
IOS Press, Inc.
6751 Tepper Drive
Clifton, VA 20124
Tel.: +1 703 830 6300
Fax: +1 703 830 2300 firstname.lastname@example.org
(Corporate matters and books only) IOS Press c/o Accucoms US, Inc.
For North America Sales and Customer Service
West Point Commons
Lansdale PA 19446
Tel.: +1 866 855 8967
Fax: +1 215 660 5042 email@example.com