[Back]

M. Abseher, N. Musliu, S. Woltran:
"htd -- A Free, Open-Source Framework for Tree Decompositions and Beyond";
Report No. DBAI-TR-2016-96, 2016; 52 pages.

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. Practical experience showed that generating decompositions of small width is not the only crucial ingredient towards efficiency. In fact, additional features of tree decompositions are very important for good performance in practice. To turn the theoretical potential of structural decomposition into successful applications, we thus require implementations of decomposition methods which allow for a smooth integration and moreover are easily extendible and adaptable to the domain-specific needs. To this end, we present htd, a free and open-source library for graph decomposition. The current version of htd includes efficient implementations of several heuristic approaches for tree decomposition and offers various features for normalization and customization of the decomposition. The aim of this report is to present the main features of htd together with an experimental evaluation underlining the effectiveness and efficiency of the implementation.

Project Head Stefan Woltran:
START