htd
A small but efficient C++ library for computing
(customized) tree and hypertree decompositions
About
htd is a software library which does not only compute tree decompositions, it also allows to fully customize them via (custom) manipulations, labelings and optimize them based on a user-provided fitness function. The library provides efficient implementations of several well-established techniques for computing tree decompositions (like bucket-elimination based on a vertex elimination ordering of the input graph) and it is optimized for large (hyper)graphs. At the current stage, htd is able to decompose graphs containing millions of vertices and several hundreds of thousands of (hyper)edges efficiently.
For almost each class used in the library, htd provides an interface and a corresponding factory class allowing to directly influence the process of generating decompositions without having to re-invent the wheel at any place. That is, if one for instance develops a new heuristic for vertex elimination orderings there is absolutely no need to change anything in the remainder of the library in order to test its influence on the quality of bucket-elimination. (In fact, one does not even need to re-compile htd for such a modification as long as all interfaces are implemented properly by the new algorithm and as long as the algorithm is made available to htd via the corresponding factory class.)
A small example application demonstrating the usage of htd, the source code of the framework as well as further documentation are provided at Github .
Related Projects
Currently, htd is used successfully in the following projects:Awards
- In a close race for podium positions, htd achieved the third place in the "heuristic treewidth" track of the 1st PACE challenge
Downloads
Releases:
Evaluation Instances:
References
2017
- Tailored Tree Decompositions for Efficient Problem Solving Ph.D. Thesis, TU Wien, 2017.
Supervision: Stefan Woltran and Nysret Musliu
[ Abstract | BibTeX ] - htd - A Free, Open-Source Framework for (Customized) Tree Decompositions and Beyond In Proceedings of the 14th International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming (CPAIOR 2017), 2017.
To appear.
[ Abstract | BibTeX ]