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 Πp2. 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. 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 contrast to these positive results, however, deciding whether an arbitrary set of arguments is “collectively acceptable” remains NP–complete in bipartite systems. In addition, a construction is presented by means of which questions posed of arguments in any given finite argument system may be expressed as questions within a related system in which every argument attacks and is attacked by at most two arguments. It follows that bounding the number of attacks on individual arguments is unlikely to produce a computationally more tractable environment.
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