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 (18)

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

This page was built for publication: Towards fixed-parameter tractable algorithms for abstract argumentation