Tech Reports

ULCS-06-004

Computational properties of argument systems satisfying graph-theoretic constraints

Paul E. Dunne

Abstract

One difficulty that arises in abstract argument systems is that many natural questions regarding argument acceptability are, in general, computationally intractable having been classified as complete for classes such as NP, co-NP, and Pi_{2}. In consequence, a number of researchers have considered methods for specialising the structure of such systems so as to identify classes for which efficient decision processes exist. In this paper the effect of a number of graph-theoretic restrictions is considered: k-partite systems (k>=2) in which the set of arguments may be partitioned into k sets each of which is conflict-free; systems in which the numbers of attacks originating from and made upon any argument are bounded; planar systems; and, finally, those of k-bounded treewidth.

For the class of bipartite graphs, it is shown that determining the acceptability status of a specific argument can be accomplished in polynomial-time under both credulous and sceptical semantics. In addition we establish the existence of polynomial time methods for systems having bounded treewidth when deciding the following: whether a given (set of) arguments is credulously accepted; if the system has a non-empty preferred extension; has a stable extension; is coherent; has at least one sceptically accepted argument.

In contrast to these positive results, however, deciding whether an arbitrary set of arguments is "collectively acceptable" remains NP-complete in bipartite systems. Furthermore for both planar and bounded degree systems the principal decision problems are as hard as the unrestricted cases. In deriving these latter results we introduce various concepts of "simulating" a general argument system by a restricted class so allowing any argument system to be translated to one which has both bounded degree and is planar. Finally, for the development of basic argument systems to so-called "value-based frameworks", we present results indicating that decision problems known to be intractable in their most general form remain so even under quite severe graph-theoretic restrictions. In particular the problem of deciding "subjective acceptability" continues to be NP - complete even when the underlying graph is a binary tree.

For each technical report listed here, copyright and all intellectual property rights remain with the respective authors. Copyright is effective from the year of publication in each case. By downloading a file from this page, you agree to use it only for purposes of research and scholarship. Any other use of this material or storage of it in any medium or its sale or distribution in any form is expressly forbidden without prior written permission from the authors concerned.