Reasoning in Argumentation Frameworks of Bounded Clique-WidthWolfgang Dvovrak, , and Stefan Woltran.
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. 219-230.
Abstract:Most computational problems in the area of abstract argumentation are intractable, thus identifying tractable fragments and developing efficient algorithms for such fragments are important objectives towards practically efficient argumentation systems. One approach to tractability is to view abstract argumentation frameworks (AFs) as directed graphs and bound certain graph parameters. In particular, Dunne showed that many problems can be solved in linear time for AFs of bounded treewidth. In this paper we consider the graph-parameter clique-width, which is more general than treewidth. An additional advantage of clique-width over treewidth is that it applies well to directed graphs and takes the orientation of edges into account. We first give theoretical tractability results for AFs of bounded clique-width and then introduce dynamic-programming algorithms for credulous and skeptical reasoning.
Keywords: Computational Properties of Argumentation, Clique-Width, Fixed-Parameter Tractability