Towards fixed-parameter tractable algorithms for abstract argumentation

DOI10.1016/j.artint.2012.03.005zbMath1251.68226OpenAlexW2042586976MaRDI QIDQ1761281

Stefan Woltran, Reinhard Pichler, Wolfgang Dvořák

Publication date: 15 November 2012

Published in: Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.artint.2012.03.005

zbMATH Keywords

complexitydynamic programmingfixed-parameter tractabilitytree-widthabstract argumentation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Logic in artificial intelligence (68T27)

Related Items

Efficient Problem Solving on Tree Decompositions Using Binary Decision Diagrams ⋮ Toward incremental computation of argumentation semantics: a decomposition-based approach ⋮ Weighted argumentation for analysis of discussions in Twitter ⋮ RAFDivider  : a distributed algorithm for computing semantics in higher-order abstract argumentation frameworks ⋮ The complexity landscape of claim-augmented argumentation frameworks ⋮ A practical account into counting Dung's extensions by dynamic programming ⋮ Algorithms and complexity results for persuasive argumentation ⋮ Treewidth in Non-Ground Answer Set Solving and Alliance Problems in Graphs ⋮ Complexity-sensitive decision procedures for abstract argumentation ⋮ Algorithms for decision problems in argument systems under preferred semantics ⋮ Acceptance in incomplete argumentation frameworks ⋮ Augmenting tractable fragments of abstract argumentation ⋮ How we designed winning algorithms for abstract argumentation and which insight we attained ⋮ Graph-classes of argumentation frameworks with collective attacks ⋮ Incremental Computation of Deterministic Extensions for Dynamic Argumentation Frameworks ⋮ A general notion of equivalence for abstract argumentation ⋮ Complexity of abstract argumentation under a claim-centric view ⋮ Methods for solving reasoning problems in abstract argumentation -- a survey

Uses Software

• ComputeTW

Cites Work

• Unnamed Item
• Unnamed Item
• Complexity of semi-stable and stage semantics in argumentation frameworks
• Graph theoretical structures in logic programs and default theories
• Safe separators for treewidth
• Approximation algorithms for treewidth
• Safe reduction rules for weighted treewidth
• Digraph measures: Kelly decompositions, games, and orderings
• Treewidth computations. I: Upper bounds
• Computing ideal sceptical argumentation
• Computational properties of argument systems satisfying graph-theoretic constraints
• The computational complexity of ideal semantics
• Treewidth. Computations and approximations
• Directed tree-width
• Coherence in finite argument systems.
• On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and \(n\)-person games
• Linear time solvable optimization problems on graphs of bounded clique-width
• A logical account of formal argumentation
• Handle-rewriting hypergraph grammars
• SCC-recursiveness: a general schema for argumentation semantics
• Parametrized complexity theory.
• Directed path-width and monotonicity in digraph searching
• Transition graphs and the star-height of regular events
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
• An Iterative Heuristic Algorithm for Tree Decomposition
• Graph minors. II. Algorithmic aspects of tree-width
• The Complexity of Enumeration and Reliability Problems
• DAG-Width and Parity Games
• Symbolic and Quantitative Approaches to Reasoning with Uncertainty
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth