Counting Complexity for Reasoning in Abstract Argumentation
Authors: Johannes K. Fichte, Markus Hecher, Arne Meier2827-2834
AAAI 2019 | Conference 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 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 (DP). Our algorithms run in time double or triple exponential in the treewidth depending on the considered semantics. Finally, we take the exponential time hypothesis (ETH) into account and establish lower bounds of bounded treewidth algorithms for counting extensions and projected extension. |
| Researcher Affiliation | Academia | Johannes K. Fichte TU Dresden 01062 Dresden, Germany johannes.fichte@tu-dresden.de; Markus Hecher TU Wien Institute of Logic and Computation Favoritenstraße 9-11 / E192 1040 Vienna, Austria hecher@dbai.tuwien.ac.at; Arne Meier Leibniz Universit at Hannover Institut f ur Theoretische Informatik Appelstraße 4 30167 Hannover, Germany meier@thi.uni-hannover.de |
| 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 PROJ(t, , νt, ( , , P), π1, π2 ) |
| Open Source Code | No | The paper does not contain any statement about making its own source code available, nor does it provide links to a code repository for the described methodology. |
| Open Datasets | No | The paper is theoretical and does not involve training or evaluating models on datasets. It studies abstract argumentation frameworks as mathematical structures. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical evaluation on datasets, thus no dataset splits for training, validation, or testing are mentioned. |
| Hardware Specification | No | The paper does not mention any specific hardware used, as its focus is theoretical complexity and algorithm design rather than empirical implementation. |
| Software Dependencies | No | The paper does not specify any software dependencies with version numbers required to replicate the theoretical analysis or algorithms. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup with hyperparameters, training configurations, or other system-level settings. It focuses on the theoretical properties and runtime complexity of algorithms. |