Details
| Original language | English |
|---|---|
| Article number | 26 |
| Pages (from-to) | 26:1-26:25 |
| Number of pages | 25 |
| Journal | ACM Trans. Comput. Log. |
| Volume | 24 |
| Issue number | 3 |
| Early online date | 31 Jan 2023 |
| Publication status | Published - 10 May 2023 |
Abstract
Argumentation is a well-established formalism dealing with conflicting information by generating and comparing arguments. It has been playing a major role in AI for decades. In logic-based argumentation, we explore the internal structure of an argument. Informally, a set of formulas is the support for a given claim if it is consistent, subset-minimal, and implies the claim. In such a case, the pair of the support and the claim together is called an argument. In this article, we study the propositional variants of the following three computational tasks studied in argumentation: ARG (exists a support for a given claim with respect to a given set of formulas), ARG-Check (is a given set a support for a given claim), and ARG-Rel (similarly as ARG plus requiring an additionally given formula to be contained in the support). ARG-Check is complete for the complexity class DP, and the other two problems are known to be complete for the second level of the polynomial hierarchy (Creignou et al. 2014 and Parson et al., 2003) and, accordingly, are highly intractable. Analyzing the reason for this intractability, we perform a two-dimensional classification: First, we consider all possible propositional fragments of the problem within Schaefer's framework (STOC 1978) and then study different parameterizations for each of the fragments. We identify a list of reasonable structural parameters (size of the claim, support, knowledge base) that are connected to the aforementioned decision problems. Eventually, we thoroughly draw a fine border of parameterized intractability for each of the problems showing where the problems are fixed-parameter tractable and when this exactly stops. Surprisingly, several cases are of very high intractability (para-NP and beyond).
Keywords
- logic-based argumentation, Parameterized complexity, Schaefer's framework
ASJC Scopus subject areas
- Mathematics(all)
- Computational Mathematics
- Mathematics(all)
- Theoretical Computer Science
- Mathematics(all)
- Logic
- Computer Science(all)
- General Computer Science
Cite this
- Standard
- Harvard
- Apa
- Vancouver
- BibTeX
- RIS
In: ACM Trans. Comput. Log., Vol. 24, No. 3, 26, 10.05.2023, p. 26:1-26:25.
Research output: Contribution to journal › Article › Research › peer review
}
TY - JOUR
T1 - Parameterized Complexity of Logic-based Argumentation in Schaefer's Framework
AU - Mahmood, Yasir
AU - Meier, Arne
AU - Schmidt, Johannes
N1 - Funding Information: Yasir Mahmood and Arne Meier appreciate funding by the German Research Foundation (DFG) under the project ME4279/ 1-2.
PY - 2023/5/10
Y1 - 2023/5/10
N2 - Argumentation is a well-established formalism dealing with conflicting information by generating and comparing arguments. It has been playing a major role in AI for decades. In logic-based argumentation, we explore the internal structure of an argument. Informally, a set of formulas is the support for a given claim if it is consistent, subset-minimal, and implies the claim. In such a case, the pair of the support and the claim together is called an argument. In this article, we study the propositional variants of the following three computational tasks studied in argumentation: ARG (exists a support for a given claim with respect to a given set of formulas), ARG-Check (is a given set a support for a given claim), and ARG-Rel (similarly as ARG plus requiring an additionally given formula to be contained in the support). ARG-Check is complete for the complexity class DP, and the other two problems are known to be complete for the second level of the polynomial hierarchy (Creignou et al. 2014 and Parson et al., 2003) and, accordingly, are highly intractable. Analyzing the reason for this intractability, we perform a two-dimensional classification: First, we consider all possible propositional fragments of the problem within Schaefer's framework (STOC 1978) and then study different parameterizations for each of the fragments. We identify a list of reasonable structural parameters (size of the claim, support, knowledge base) that are connected to the aforementioned decision problems. Eventually, we thoroughly draw a fine border of parameterized intractability for each of the problems showing where the problems are fixed-parameter tractable and when this exactly stops. Surprisingly, several cases are of very high intractability (para-NP and beyond).
AB - Argumentation is a well-established formalism dealing with conflicting information by generating and comparing arguments. It has been playing a major role in AI for decades. In logic-based argumentation, we explore the internal structure of an argument. Informally, a set of formulas is the support for a given claim if it is consistent, subset-minimal, and implies the claim. In such a case, the pair of the support and the claim together is called an argument. In this article, we study the propositional variants of the following three computational tasks studied in argumentation: ARG (exists a support for a given claim with respect to a given set of formulas), ARG-Check (is a given set a support for a given claim), and ARG-Rel (similarly as ARG plus requiring an additionally given formula to be contained in the support). ARG-Check is complete for the complexity class DP, and the other two problems are known to be complete for the second level of the polynomial hierarchy (Creignou et al. 2014 and Parson et al., 2003) and, accordingly, are highly intractable. Analyzing the reason for this intractability, we perform a two-dimensional classification: First, we consider all possible propositional fragments of the problem within Schaefer's framework (STOC 1978) and then study different parameterizations for each of the fragments. We identify a list of reasonable structural parameters (size of the claim, support, knowledge base) that are connected to the aforementioned decision problems. Eventually, we thoroughly draw a fine border of parameterized intractability for each of the problems showing where the problems are fixed-parameter tractable and when this exactly stops. Surprisingly, several cases are of very high intractability (para-NP and beyond).
KW - logic-based argumentation
KW - Parameterized complexity
KW - Schaefer's framework
UR - http://www.scopus.com/inward/record.url?scp=85164301929&partnerID=8YFLogxK
U2 - 10.1145/3582499
DO - 10.1145/3582499
M3 - Article
VL - 24
SP - 26:1-26:25
JO - ACM Trans. Comput. Log.
JF - ACM Trans. Comput. Log.
SN - 1529-3785
IS - 3
M1 - 26
ER -