Counting Complexity for Reasoning in Abstract Argumentation
In this paper, we consider counting and projected model counting of extensions in abstract argumentation for various semantics. When asking for projected counts we are interested in counting the number of extensions of a given argumentation framework while multiple extensions that are identical when restricted to the projected arguments count as only one projected extension. We establish classical complexity results and parameterized complexity results when the problems are parameterized by treewidth of the undirected argumentation graph. To obtain upper bounds for counting projected extensions, we introduce novel algorithms that exploit small treewidth of the undirected argumentation graph of the input instance by dynamic programming (DP). Our algorithms run in time double or triple exponential in the treewidth depending on the considered semantics. Finally, we take the exponential time hypothesis (ETH) into account and establish lower bounds of bounded treewidth algorithms for counting extensions and projected extension.
Code (0)
등록된 구현이 없습니다.
Tasks
Abstract ArgumentationSimilar Papers 제목 키워드 기반
Facets in Argumentation: A Formal Approach to Argument Significance
Argumentation is a central subarea of Artificial Intelligence (AI) for modeling and reasoning about arguments. The semantics of abstract argumentation frameworks (AFs) is given by sets of arguments (extensions) and condi…
Abstract ArgumentationNavigateCounterfactual and Semifactual Explanations in Abstract Argumentation: Formal Foundations, Complexity and Computation
Explainable Artificial Intelligence and Formal Argumentation have received significant attention in recent years. Argumentation-based systems often lack explainability while supporting decision-making processes. Counterf…
Abstract ArgumentationcounterfactualDecision MakingExplainable artificial intelligenceAttacker and Defender Counting Approach for Abstract Argumentation
In Dung's abstract argumentation, arguments are either acceptable or unacceptable, given a chosen notion of acceptability. This gives a coarse way to compare arguments. In this paper, we propose a counting approach for a…
Abstract ArgumentationStability in Abstract Argumentation
The notion of stability in a structured argumentation setup characterizes situations where the acceptance status associated with a given literal will not be impacted by any future evolution of this setup. In this paper, …
Abstract ArgumentationStructure-Aware Encodings of Argumentation Properties for Clique-width
Structural measures of graphs, such as treewidth, are central tools in computational complexity resulting in efficient algorithms when exploiting the parameter. It is even known that modern SAT solvers work efficiently o…