Faster Algorithms for Weak Backdoors
Authors: Serge Gaspers, Andrew Kaploun3741-3748
AAAI 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We design a new algorithm for WB(3CNF, 0-VAL) by reducing it to a local search variant of 3-SAT. We show that our algorithm runs in time O (2.562k), improving on the previous state-of-the-art of O (2.85k). Here, the O notation is a variant of the big-O notation that allows to omit polynomial factors in the input size. Next, we look at WB(3CNF, NULL), where NULL is the class consisting of the empty formula. This problem was known to have a trivial running time upper bound of O (6k) and can easily be solved in O (3k) time. We use a reduction to CONFLICT FREE d-HITTING SET to prove an upper bound of O (2.2738k), and also prove a lower bound of 2o(k) assuming the Exponential Time Hypothesis. Finally, HORN is the class of formulae with at most one positive literal per clause. We improve the previous O (4.54k) running time for WB(3CNF, HORN) problem to O (4.17k), by exploiting the structure of the SAT instance to give a novel proof of the non-existence of the slowest cases after a slight restructuring of the branching priorities. |
| Researcher Affiliation | Academia | School of Computer Science and Engineering, UNSW Sydney serge.gaspers@unsw.edu.au, andrewkaploun0@gmail.com |
| Pseudocode | Yes | Apply the following branching rules exhaustively: Branching Rule 1.( ) If there is a positive 3-clause (x, y, z), branch into the following cases: x = 1 y = 1 z = 1 x = 0, y = 0 x = 0, z = 0 y = 0, z = 0 |
| Open Source Code | No | The paper does not provide concrete access to source code for the methodology described. |
| Open Datasets | No | The paper is theoretical and does not use datasets for empirical evaluation. |
| Dataset Splits | No | The paper is theoretical and does not involve experimental validation with dataset splits. |
| Hardware Specification | No | The paper is theoretical and does not report on experiments, thus no hardware specifications are provided. |
| Software Dependencies | No | The paper is theoretical and does not report on experiments, thus no specific software dependencies with version numbers are mentioned. |
| Experiment Setup | No | The paper is theoretical and does not report on experiments, thus no experimental setup details such as hyperparameters are provided. |