This project includes a library of tools to analyze hypergraph properties and algorithms to detect the (generalized/fractional) hypertree width.
These instructions will get you a copy of the project up and running on your local machine for development and testing purposes.
In order to compile NewDetKDecomp you need a C++ compiler supporting C++14 and the Cbc mixed integer programming solver.
First download and install coinor-cbc as explained on their web page. E.g., in Ubuntu install the package: coinor-libclp-dev, which downloads already all needed packages.
Compile the programs by running make in the root directory.
make
This creates the binaries hg-tools, detkdecomp, globalbipkdecomp, localbipkdecomp, balsepkdecomp, fracimprovehd and rankfhdecomp in the bin directory.
- Wolfgang Fischl - Algorithms on LocalBip, GlobalBip, BalSep, FracImproveHD and RankFHDecomp
- Davide Longo - Algorithms on FracImproveHD
- A website with benchmark results using these tools can be found here: HyperBench
- Thanks to Marko Samer for the Initial work on the DetKDecomp Algorithm
- Georg Gottlob and Reinhard Pichler for their help on the theoretical underpinnings of the algorithms
[1] W. Fischl, G. Gottlob, R. Pichler: General and Fractional Hypertree Decompositions: Hard and Easy cases. accepted for PODS'18.
[2] W. Fischl, G. Gottlob, D. M. Longo, R. Pichler: HyperBench: A Benchmark and Tool for Hypergraphs and Empirical Findings. Submitted to PODS'18.