Decomposition-Guided Reductions for Argumentation and Treewidth

Fichte, Johannes; Hecher, Markus; Mahmood, Yasir; Meier, Arne

doi:10.24963/ijcai.2021/259

Decomposition-Guided Reductions for Argumentation and Treewidth

Johannes Fichte, Markus Hecher, Yasir Mahmood, Arne Meier

Download BibTeX Cite

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence. Main Track. Pages 1880-1886.

https://doi.org/10.24963/ijcai.2021/259

Keywords

Knowledge Representation and Reasoning: Computational Models of Argument
Constraints and SAT: Constraint Satisfaction
Knowledge Representation and Reasoning: Computational Complexity of Reasoning

Abstract

Argumentation is a widely applied framework for modeling and evaluating arguments and its reasoning with various applications. Popular frameworks are abstract argumentation (Dung’s framework) or logic-based argumentation (Besnard-Hunter’s framework). Their computational complexity has been studied quite in-depth. Incorporating treewidth into the complexity analysis is particularly interesting, as solvers oftentimes employ SAT-based solvers, which can solve instances of low treewidth fast. In this paper, we address whether one can design reductions from argumentation problems to SAT-problems while linearly preserving the treewidth, which results in decomposition-guided (DG) reductions. It turns out that the linear treewidth overhead caused by our DG reductions, cannot be significantly improved under reasonable assumptions. Finally, we consider logic-based argumentation and establish new upper bounds using DG reductions and lower bounds.

Johannes Fichte, Markus Hecher, Yasir Mahmood, and Arne Meier. 2021. Decomposition-Guided Reductions for Argumentation and Treewidth. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21. IJCAI, 1880–1886. https://doi.org/10.24963/ijcai.2021/259

@inproceedings{ijcai2021p259,
  title     = {Decomposition-Guided Reductions for Argumentation and Treewidth},
  author    = {Fichte, Johannes and Hecher, Markus and Mahmood, Yasir and Meier, Arne},
  booktitle = {Proceedings of the Thirtieth International Joint Conference on
               Artificial Intelligence, {IJCAI-21}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {Prof. Zhi-Hua Zhou},
  pages     = {1880--1886},
  year      = {2021},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2021/259},
  url       = {https://doi.org/10.24963/ijcai.2021/259},
}

TY  - CPAPER
TI  - Decomposition-Guided Reductions for Argumentation and Treewidth
AU  - Fichte, Johannes
AU  - Hecher, Markus
AU  - Mahmood, Yasir
AU  - Meier, Arne
T2  - Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2021
SP  - 1880
EP  - 1886
DO  - 10.24963/ijcai.2021/259
UR  - https://doi.org/10.24963/ijcai.2021/259
ER  -