Algorithms and Complexity Results for Persuasive ArgumentationEun Jung Kim, Sebastian Ordyniak andArtificial Intelligence, vol. 175, pp. 1722-1736, 2011. Preliminary and shortened version appeared in the proceedings of COMMA 2010, Third International Conference on Computational Models of Argument, Desenzano del Garda, Italy, September 8-10, 2010. Froniers in Artificial Intelligence and Applications, vol. 216, IOS Press, 2010, pp. 311-322. Abstract:Value-based argumentation frameworks, as introduced by Bench-Capon, allow the abstract representation of persuasive argumentation. This formalism takes into account the relative strength of arguments with respect to some ordering which represents an audience. Deciding subjective or objective acceptance (i.e., acceptance with respect to at least one or with respect to all orderings) are intractable computational problems.In this paper we study the computational complexity of testing the subjective or objective acceptance for problem instances that obey certain restrictions. We consider structural restrictions in terms of the underlying graph structure of the value-based argumentation framework and in terms of properties of the equivalence relation formed by arguments with the same relative strength. We identify new tractable fragments where subjective and objective acceptance can be tested in polynomial time. Furthermore we show the intractability of some fragments that are located at the boundary to tractability. Our results disprove two conjectures of Dunne (Artificial Intelligence 171, 2007). Keywords: Value-based argumentation frameworks, treewidth, NP-hardness, polynomial-time tractability, subjective and objective acceptance. Preprint available from [arXiv.1104.4290] |