Threshold Treewidth and Hypertree Width
Authors: Robert Ganian, Andre Schidler, Manuel Sorge, Stefan Szeider
JAIR 2022 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We complement our theoretical results with experimental evaluations in terms of heuristics as well as exact methods based on SAT/SMT encodings. |
| Researcher Affiliation | Academia | Robert Ganian EMAIL Andre Schidler EMAIL Manuel Sorge EMAIL Stefan Szeider EMAIL Algorithms and Complexity Group Faculty of Informatics TU Wien Vienna, Austria |
| Pseudocode | No | The paper describes algorithms in text, particularly in the proofs of theorems and in Section 7 'Implemented Algorithms', but it does not present any clearly labeled pseudocode or algorithm blocks. |
| Open Source Code | Yes | Our code is freely available.9 9. See https://github.com/ASchidler/htdsmt/tree/weighted and https://github.com/ASchidler/tw-sv. |
| Open Datasets | Yes | For threshold-d load-c tree decompositions we used 2788 instances from the twlib10 benchmark set. 10. http://www.cs.uu.nl/research/projects/treewidthlib/ For generalized threshold-d load-c hypertree decompositions we used the 3071 hyperbench (Fischl, Gottlob, Longo, & Pichler, 2019)11 instances after removing self-loops and subsumed hyperedges. 11. http://hyperbench.dbai.tuwien.ac.at/ |
| Dataset Splits | No | The paper mentions generating instances by marking a percentage of vertices/hyperedges as heavy ('a ratio of 30% heavy vertices/hyperedges'), and filtering instances based on width ('disregarded instances of width below 13 and below 4'), but it does not describe traditional training/test/validation splits for datasets. |
| Hardware Specification | Yes | We ran our experiments on a cluster, where each node consists of two Xeon E52640 CPUs, each running 10 cores at 2.4 GHz and 160 GB memory. |
| Software Dependencies | Yes | As solvers for the SAT and SMT instances we used minisat 2.2.0 (E en & S orensson, 2003)7 and optimathsat 1.6.2 (Sebastiani & Trentin, 2020)8. The control code and heuristics use Python 3.8.0. |
| Experiment Setup | Yes | We used a 8 GB memory limit and a 2 hour time limit per instance. We created our loaded instances by marking a certain percentage of all vertices or hyperedges as heavy. We ran experiments for diļ¬erent ratios, but since the outcomes did not deviate too much, here we only present the results for a ratio of 30% heavy vertices/hyperedges (same as by Kask et al. (2011)). In particular, for treewidth and generalized hypertree width, we disregarded instances of width below 13 and below 4, respectively. We used minisat 2.2.0 (E en & S orensson, 2003)7 and optimathsat 1.6.2 (Sebastiani & Trentin, 2020)8. The control code and heuristics use Python 3.8.0. |