Htd - a free, open-source framework for (customized) tree decompositions and beyond. Decompositions of graphs play a central role in the field of parameterized complexity and are the basis for many fixed-parameter tractable algorithms for problems that are NP-hard in general. Tree decompositions are the most prominent concept in this context and several tools for computing tree decompositions recently competed in the 1st Parameterized Algorithms and Computational Experiments Challenge. However, in practice the quality of a tree decomposition cannot be judged without taking concrete algorithms that make use of tree decompositions into account. In fact, practical experience has shown that generating decompositions of small width is not the only crucial ingredient towards efficiency. To this end, we present htd, a free and open-source software library, which includes efficient implementations of several heuristic approaches for tree decomposition and offers various features for normalization and customization of decompositions. The aim of this article is to present the specifics of htd together with an experimental evaluation underlining the effectiveness and efficiency of the implementation.

References in zbMATH (referenced in 12 articles )

Showing results 1 to 12 of 12.
Sorted by year (citations)

  1. Hecher, Markus: Treewidth-aware reductions of normal \textscASPto \textscSAT- is normal \textscASPHarder than \textscSATafter all? (2022)
  2. Besin, Viktor; Hecher, Markus; Woltran, Stefan: Utilizing treewidth for quantitative reasoning on epistemic logic programs (2021)
  3. Dilkas, Paulius; Belle, Vaishak: Weighted model counting without parameter variables (2021)
  4. Dudek, Jeffrey M.; Phan, Vu H. N.; Vardi, Moshe Y.: ProCount: weighted projected model counting with graded project-join trees (2021)
  5. Bichler, Manuel; Morak, Michael; Woltran, Stefan: lpopt: a rule optimization tool for answer set programming (2020)
  6. Bichler, Manuel; Morak, Michael; Woltran, Stefan: selp: a single-shot epistemic logic program solver (2020)
  7. Davot, Tom; Chateau, Annie; Giroudeau, Rodolphe; Weller, Mathias: Linearizing genomes: exact methods and local search (2020)
  8. Hecher, Markus; Thier, Patrick; Woltran, Stefan: Taming high treewidth with abstraction, nested dynamic programming, and database technology (2020)
  9. Kangas, Kustaa; Koivisto, Mikko; Salonen, Sami: A faster tree-decomposition based algorithm for counting linear extensions (2020)
  10. Calimeri, Francesco; Perri, Simona; Zangari, Jessica: Optimizing answer set computation via heuristic-based decomposition (2019)
  11. Fichte, Johannes K.; Hecher, Markus; Woltran, Stefan; Zisser, Markus: Weighted model counting on the GPU by exploiting small treewidth (2018)
  12. Abseher, Michael; Musliu, Nysret; Woltran, Stefan: Htd - a free, open-source framework for (customized) tree decompositions and beyond (2017)