Counting Complexity for Reasoning in Abstract Argumentation
Authors: Johannes K. Fichte, Markus Hecher, Arne Meier
JAIR 2024 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We establish classical complexity results and parameterized complexity results when the problems are parameterized by the treewidth of the undirected argumentation graph. To obtain upper bounds for counting projected extensions, we introduce novel algorithms that exploit small treewidth of the undirected argumentation graph of the input instance by dynamic programming. Our algorithms run in double or triple exponential time in the treewidth, depending on the semantics under consideration. Finally, we establish lower bounds of bounded treewidth algorithms for counting extensions and projected extension under the exponential time hypothesis (ETH). |
| Researcher Affiliation | Academia | Johannes K. Fichte EMAIL Link oping University 58183 Link oping, Sweden Markus Hecher EMAIL MIT Computer Science & Artificial Intelligence Laboratory Massachusetts Institute of Technology 32 Vassar St Cambridge, MA 02139, USA Arne Meier EMAIL Leibniz Universit at Hannover Institut f ur Theoretische Informatik Appelstraße 4 30167 Hannover, Germany |
| Pseudocode | Yes | Listing 1: Local algorithm ADM(t, χt, , (Ft, c, ), τ1, τ2 ) Listing 2: Local algorithm STAG(t, χt, , (Ft, c, ), τ1, τ2 ) Listing 3: Local algorithm CONF(t, χt, , (Ft, c, ), τ1, τ2 ) Listing 4: Local algorithm STAB(t, χt, , (Ft, c, ), τ1, τ2 ) Listing 5: Local algorithm COMP(t, χt, , (Ft, c, ), τ1, τ2 ) Listing 6: Local algorithm PROJ(t, , νt, ( , , P), π1, π2 ) |
| Open Source Code | No | The paper describes various algorithms and their complexity but does not provide any explicit statement about making their own implementation's source code available, nor does it provide a link to a repository for the methods described in this paper. |
| Open Datasets | No | The paper focuses on theoretical aspects of abstract argumentation and computational complexity. It uses conceptual 'argumentation frameworks' for examples (e.g., Example 1 and 2) but does not describe the use of any publicly available or open datasets for empirical evaluation, nor does it provide links or citations to such datasets. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical evaluation with datasets, therefore, there are no mentions of dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical, focusing on computational complexity and algorithm design. It does not present experimental results that would require a description of specific hardware used for computation. |
| Software Dependencies | No | The paper is theoretical and describes algorithms and complexity results. It does not provide details on specific software dependencies or version numbers for any implementation of these algorithms. |
| Experiment Setup | No | The paper is theoretical and analyzes the computational complexity of abstract argumentation problems. It does not include an experimental section or details regarding specific experimental setups, hyperparameters, or training configurations. |