Complexity Properties of Critical Sets of Arguments

Richard Booth, Martin Caminada, Paul Dunne, Mikolaj Podlaszewski, Iyad Rahwan

Research output: Chapter in Book/Report/Conference proceedingPublished conference contribution

9 Citations (Scopus)
7 Downloads (Pure)


In an abstract argumentation framework, there are often multiple plausible ways to evaluate (or label) the status of each argument as accepted, rejected, or undecided. But often there exists a critical set of arguments whose status is sufficient to determine uniquely the status of every other argument. Once an agent has decided its position on a critical set of arguments, then essentially the entire framework has been evaluated. Likewise, once a group, e.g. a jury,
agrees on the status of a critical set of arguments, all of their different views over all other arguments are resolved. Thus, critical sets of arguments are important both for efficient evaluation by individual agents and for collective agreement by groups of such. To exploit this idea in practice, however, a number of computational questions must be considered. In particular, how much computational effort is needed to verify that a set is, indeed, a critical set or a minimal critical set. In this paper we determine exact bounds on the computational complexity of these and related questions. In addition
we provide similar analyses of issues: a concept closely related to critical set and derived in terms of (equivalence) classes of arguments related through "common" labelling behaviours.
Original languageEnglish
Title of host publicationComputational Models of Argument
Subtitle of host publicationProceedings of COMMA 2014
EditorsSimon Parsons, Nir Oren, Chris Reed, Frederico Cerutti
Place of PublicationAmsterdam
PublisherIOS Press
Number of pages11
ISBN (Electronic)9781614994367
ISBN (Print)9781614994350
Publication statusPublished - 2014


  • argumentation frameworks
  • labelling schemes
  • computational complexity


Dive into the research topics of 'Complexity Properties of Critical Sets of Arguments'. Together they form a unique fingerprint.

Cite this