Decomposition-Guided Reductions for Argumentation and Treewidth
Authors: Johannes Fichte, Markus Hecher, Yasir Mahmood, Arne Meier
IJCAI 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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. ... Our results (summarized in Table 1) provide new theoretical insights and strengthen the applicability of solvers that implicitly solve instances by means of tree decompositions. |
| Researcher Affiliation | Academia | Johannes Fichte1 , Markus Hecher2,3 , Yasir Mahmood4 , Arne Meier4 1UC Berkeley, Berkeley, USA 2TU Wien, Vienna, Austria 3University of Potsdam, Germany 4 Leibniz Universit at Hannover, Germany |
| Pseudocode | No | The paper describes algorithms and reductions in prose and with mathematical formulas, but it does not include any clearly labeled 'Pseudocode' or 'Algorithm' blocks or structured code-like procedures. |
| Open Source Code | No | The paper does not provide any links to a code repository, nor does it explicitly state that the source code for the described methodology is being released or is available in supplementary materials. |
| Open Datasets | No | The paper is theoretical and does not involve empirical experiments with datasets; therefore, it does not specify any training datasets or their public availability. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments; therefore, it does not provide details on training, validation, or test dataset splits. |
| Hardware Specification | No | The paper is theoretical and does not report on computational experiments that would require specific hardware specifications. |
| Software Dependencies | No | The paper is theoretical and does not detail the implementation of algorithms or experiments that would require specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and focuses on complexity analysis and algorithm design rather than empirical experiments, so it does not provide details about an experimental setup or hyperparameters. |