Computing Twin-width with SAT and Branch & Bound
Authors: André Schidler, Stefan Szeider
IJCAI 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We evaluate our algorithms on two classes of benchmark graphs, structured graphs and graphs from the treewidth lib benchmark suite. The results show that our new SAT encoding scales better than the previous encodings, particularly for structured graphs. Furthermore, BB-CCH solves more instances in a shorter amount of time than any of the SAT encodings. |
| Researcher Affiliation | Academia | Andr e Schidler , Stefan Szeider Algorithms and Complexity Group, TU Wien, Vienna, Austria {aschidler, sz}@ac.tuwien.ac.at |
| Pseudocode | Yes | Algorithm 1 Branch & Bound Algorithm for Twin-Width Input: A graph G Output: The twin-width of the graph. |
| Open Source Code | Yes | The source code is available under https://doi.org/10.5281/ zenodo.7944399 and https://github.com/ASchidler/tww-bb. |
| Open Datasets | Yes | We expand our comparison to the Treewidth Lib instances. These instances are used as benchmarks for computing treewidth, a related width measure, and give a wider variety of graphs. ... 6http://www.cs.uu.nl/research/projects/treewidthlib/ |
| Dataset Splits | No | The paper evaluates its algorithms on benchmark graph instances (Treewidth Lib) but does not specify any train/validation/test splits for these instances. |
| Hardware Specification | Yes | We ran the experiments on servers with two AMD EPYC 7402 CPUs, each with 24 cores running at 2.8 GHz, and using Ubuntu 18.04. |
| Software Dependencies | Yes | We implemented SAT-CPT and BB-CCH in C++ compiled with GCC 7.5.02. We used nauty 2.8.6 [Mc Kay and Piperno, 2014]3 as a libary for detecting trigraph isomorphisms and automorphisms, as well as Cadical [Biere et al., 2020]4 as a SAT solver. |
| Experiment Setup | Yes | We ran the experiments on servers with two AMD EPYC 7402 CPUs, each with 24 cores running at 2.8 GHz, and using Ubuntu 18.04. ... We used all instances with 20 to 200 vertices and tested them using a 6-hour time limit and 32 GB memory limit. |