Decomposition-Guided Reductions for Argumentation and Treewidth

J. Fichte, M. Hecher, Y. Mahmood, A. Meier, in: Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, International Joint Conferences on Artificial Intelligence Organization, 2021.

Download
No fulltext has been uploaded.
Conference Paper | Published | English
Author
Fichte, Johannes; Hecher, Markus; Mahmood, YasirLibreCat; Meier, Arne
Abstract
<jats:p>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.</jats:p>
Publishing Year
Proceedings Title
Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence
LibreCat-ID

Cite this

Fichte J, Hecher M, Mahmood Y, Meier A. Decomposition-Guided Reductions for Argumentation and Treewidth. In: Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence. International Joint Conferences on Artificial Intelligence Organization; 2021. doi:10.24963/ijcai.2021/259
Fichte, J., Hecher, M., Mahmood, Y., & Meier, A. (2021). Decomposition-Guided Reductions for Argumentation and Treewidth. Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence. https://doi.org/10.24963/ijcai.2021/259
@inproceedings{Fichte_Hecher_Mahmood_Meier_2021, title={Decomposition-Guided Reductions for Argumentation and Treewidth}, DOI={10.24963/ijcai.2021/259}, booktitle={Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence}, publisher={International Joint Conferences on Artificial Intelligence Organization}, author={Fichte, Johannes and Hecher, Markus and Mahmood, Yasir and Meier, Arne}, year={2021} }
Fichte, Johannes, Markus Hecher, Yasir Mahmood, and Arne Meier. “Decomposition-Guided Reductions for Argumentation and Treewidth.” In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence. International Joint Conferences on Artificial Intelligence Organization, 2021. https://doi.org/10.24963/ijcai.2021/259.
J. Fichte, M. Hecher, Y. Mahmood, and A. Meier, “Decomposition-Guided Reductions for Argumentation and Treewidth,” 2021, doi: 10.24963/ijcai.2021/259.
Fichte, Johannes, et al. “Decomposition-Guided Reductions for Argumentation and Treewidth.” Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, International Joint Conferences on Artificial Intelligence Organization, 2021, doi:10.24963/ijcai.2021/259.

Export

Marked Publications

Open Data LibreCat

Search this title in

Google Scholar