---
title: "Decomposition-Guided Reductions for Argumentation and Treewidth"
authors:
  - "Johannes Fichte"
  - "Markus Hecher"
  - "Yasir Mahmood"
  - "Arne Meier"
doi: "10.24963/ijcai.2021/259"
url: "https://ijcai.org/proceedings/2021/259"
pdf: "https://ijcai.org/proceedings/2021/0259.pdf"
venue: "Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence"
year: 2021
pages: "1880-1886"
track: "Main Track"
keywords:
  - "Knowledge Representation and Reasoning: Computational Models of Argument"
  - "Constraints and SAT: Constraint Satisfaction"
  - "Knowledge Representation and Reasoning: Computational Complexity of Reasoning"
---

# Decomposition-Guided Reductions for Argumentation and Treewidth

Johannes Fichte, Markus Hecher, Yasir Mahmood, Arne Meier

*Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence*, pages 1880-1886. DOI: [10.24963/ijcai.2021/259](https://doi.org/10.24963/ijcai.2021/259)

## 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.