On the Complexity of Determining Defeat Relations Consistent with Abstract Argumentation Semantics

Abstract

Copyright 2022 The authors and IOS Press. Typically in abstract argumentation, one starts with arguments and a defeat relation, and applies some semantics in order to determine the acceptability status of the arguments. We consider the converse case where we have knowledge of the acceptability status of arguments and want to identify a defeat relation that is consistent with the known acceptability data – the σ-consistency problem. Focusing on complete semantics as underpinning the majority of the major semantic types, we show that the complexity of determining a defeat relation that is consistent with some set of acceptability data is highly dependent on how the data is labelled. The extension-based 2-valued σ-consistency problem for complete semantics is revealed as NP-complete, whereas the labelling-based 3-valued σ-consistency problem is solvable within polynomial time. We then present an informal discussion on application to grounded, stable, and preferred semantics.