On the Parallel Parameterized Complexity of MaxSAT Variants
Authors: Max Bannach, Malte Skambath, Till Tantau
JAIR 2023 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the parallel parameterized complexity of various versions of max-sat and provide the first constant-time algorithms parameterized either by the solution size or by the allowed excess relative to some guarantee. For the dual parameterized version where the parameter is the number of clauses we are allowed to leave unsatisfied, we present the first parallel algorithm for max-2sat (known as almost-2sat). The difficulty in solving almost-2sat in parallel comes from the fact that the iterative compression method, originally developed to prove that the problem is fixed-parameter tractable at all, is inherently sequential. |
| Researcher Affiliation | Academia | Max Bannach EMAIL European Space Agency, Advanced Concepts Team, Noordwijk, The Netherlands; Malte Skambath EMAIL Department of Computer Science, Kiel University, Kiel, Germany; Till Tantau EMAIL Institute for Theoretical Computer Science, Universität zu Lübeck, Lübeck, Germany |
| Pseudocode | Yes | Listing 1: An algorithm that outputs an optimal partial-max-sat solution on input of a weighted cnf (φ, ω) and a depth-k treedepth decomposition F of the incidencegraph of φ. |
| Open Source Code | No | The paper does not provide an explicit statement about releasing code or a link to a source-code repository for the described methodology. |
| Open Datasets | No | The paper primarily focuses on theoretical aspects of MAX-SAT variants and their parallel parameterized complexity. It uses abstract propositional formulas (cnf φ) as problem instances for analysis rather than specific, named experimental datasets, and thus does not discuss open datasets. |
| Dataset Splits | No | The paper is theoretical and analyzes the complexity of algorithms for MAX-SAT variants. It does not describe experiments using specific datasets that would require training, testing, or validation splits. |
| Hardware Specification | No | The paper is theoretical and discusses parallel parameterized complexity classes and algorithms. It does not describe any experiments or their computational execution environments, and therefore does not specify hardware. |
| Software Dependencies | No | The paper is theoretical and presents algorithms and complexity analysis. It does not describe any software implementations or list specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical, focusing on the parallel parameterized complexity of Max SAT variants and developing algorithms. It does not describe any practical experiments, and therefore provides no details on an experimental setup, hyperparameters, or system-level training settings. |