Decomposition-Guided Reductions for Argumentation and Treewidth

Publikation: Beitrag in Buch/Bericht/Sammelwerk/KonferenzbandAufsatz in KonferenzbandForschungPeer-Review

Autoren

  • Johannes Klaus Fichte
  • Markus Hecher
  • Yasir Mahmood
  • Arne Meier

Externe Organisationen

  • University of California at Berkeley
  • Technische Universität Wien (TUW)
  • Universität Potsdam
Forschungs-netzwerk anzeigen

Details

OriginalspracheEnglisch
Titel des SammelwerksProceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI 2021, Virtual Event / Montreal, Canada, 19-27 August 2021.
Herausgeber/-innenZhi-Hua Zhou
Seiten1880-1886
Seitenumfang7
ISBN (elektronisch)9780999241196
PublikationsstatusVeröffentlicht - 2021
VeranstaltungThirty-Fifth AAAI Conference on Artificial Intelligence - online
Dauer: 2 Feb. 20219 Feb. 2021

Publikationsreihe

NameIJCAI International Joint Conference on Artificial Intelligence
ISSN (Print)1045-0823

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.

ASJC Scopus Sachgebiete

Zitieren

Decomposition-Guided Reductions for Argumentation and Treewidth. / Fichte, Johannes Klaus; Hecher, Markus; Mahmood, Yasir et al.
Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI 2021, Virtual Event / Montreal, Canada, 19-27 August 2021.. Hrsg. / Zhi-Hua Zhou. 2021. S. 1880-1886 (IJCAI International Joint Conference on Artificial Intelligence).

Publikation: Beitrag in Buch/Bericht/Sammelwerk/KonferenzbandAufsatz in KonferenzbandForschungPeer-Review

Fichte, JK, Hecher, M, Mahmood, Y & Meier, A 2021, Decomposition-Guided Reductions for Argumentation and Treewidth. in Z-H Zhou (Hrsg.), Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI 2021, Virtual Event / Montreal, Canada, 19-27 August 2021.. IJCAI International Joint Conference on Artificial Intelligence, S. 1880-1886, Thirty-Fifth AAAI Conference on Artificial Intelligence, 2 Feb. 2021. https://doi.org/10.24963/ijcai.2021/259
Fichte, J. K., Hecher, M., Mahmood, Y., & Meier, A. (2021). Decomposition-Guided Reductions for Argumentation and Treewidth. In Z.-H. Zhou (Hrsg.), Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI 2021, Virtual Event / Montreal, Canada, 19-27 August 2021. (S. 1880-1886). (IJCAI International Joint Conference on Artificial Intelligence). https://doi.org/10.24963/ijcai.2021/259
Fichte JK, Hecher M, Mahmood Y, Meier A. Decomposition-Guided Reductions for Argumentation and Treewidth. in Zhou ZH, Hrsg., Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI 2021, Virtual Event / Montreal, Canada, 19-27 August 2021.. 2021. S. 1880-1886. (IJCAI International Joint Conference on Artificial Intelligence). doi: 10.24963/ijcai.2021/259
Fichte, Johannes Klaus ; Hecher, Markus ; Mahmood, Yasir et al. / Decomposition-Guided Reductions for Argumentation and Treewidth. Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI 2021, Virtual Event / Montreal, Canada, 19-27 August 2021.. Hrsg. / Zhi-Hua Zhou. 2021. S. 1880-1886 (IJCAI International Joint Conference on Artificial Intelligence).
Download
@inproceedings{89423eacb0514727b876afe3f46d6dac,
title = "Decomposition-Guided Reductions for Argumentation and Treewidth",
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.",
author = "Fichte, {Johannes Klaus} and Markus Hecher and Yasir Mahmood and Arne Meier",
note = "Funding Information: ∗The work is supported by Austrian Science Fund (FWF), Grants Y698 and P32830, the Vienna Science and Technology Fund, Grant WWTF ICT19-065, and the DFG (ME4279/1-2) under 247444366.; Thirty-Fifth AAAI Conference on Artificial Intelligence ; Conference date: 02-02-2021 Through 09-02-2021",
year = "2021",
doi = "10.24963/ijcai.2021/259",
language = "English",
series = "IJCAI International Joint Conference on Artificial Intelligence",
pages = "1880--1886",
editor = "Zhi-Hua Zhou",
booktitle = "Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI 2021, Virtual Event / Montreal, Canada, 19-27 August 2021.",

}

Download

TY - GEN

T1 - Decomposition-Guided Reductions for Argumentation and Treewidth

AU - Fichte, Johannes Klaus

AU - Hecher, Markus

AU - Mahmood, Yasir

AU - Meier, Arne

N1 - Funding Information: ∗The work is supported by Austrian Science Fund (FWF), Grants Y698 and P32830, the Vienna Science and Technology Fund, Grant WWTF ICT19-065, and the DFG (ME4279/1-2) under 247444366.

PY - 2021

Y1 - 2021

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

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

UR - http://www.scopus.com/inward/record.url?scp=85125493639&partnerID=8YFLogxK

U2 - 10.24963/ijcai.2021/259

DO - 10.24963/ijcai.2021/259

M3 - Conference contribution

T3 - IJCAI International Joint Conference on Artificial Intelligence

SP - 1880

EP - 1886

BT - Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI 2021, Virtual Event / Montreal, Canada, 19-27 August 2021.

A2 - Zhou, Zhi-Hua

T2 - Thirty-Fifth AAAI Conference on Artificial Intelligence

Y2 - 2 February 2021 through 9 February 2021

ER -

Von denselben Autoren