arboretum is a graph library and CLI for computing tree decompositions. Various state of the art preprocessing, graph reductions, exact and heuristic algorithms for obtaining tree decompositions are implemented.

Features

• Well known fast heuristics such as min-degree and min-fill [1]
• Metaheuristics such as tabu-local search [3]
• Minor-min-width lowerbound heuristic [4]
• Rule-based preprocessing for reducing graphs and obtaining tree-decompositions of graphs of treewidth ≤ 3 [5]
• Graph decomposition based on the notion of safe separators [6]
• A state-of-the-art exact algorithm [8]

The CLI

Build

As arboretum is implemented in rust, the CLI can simply be built via cargo

cargo build --release --features="cli"

Usage

Using a graph in .gr format the program can be used as follows

cargo run --release --features="cli" < <graph.gr>

or

./target/release/arboretum-cli < <graph.gr>

The CLI makes automated choices about which algorithms to use based on the input graph, but without the heuristic flag will always try to find an exact solution.

Available CLI arguments:

USAGE:
    arboretum-cli [OPTIONS] [ARGS]

FLAGS:
    -h, --help       Prints help information
    -V, --version    Prints version information

OPTIONS:
    -m, --mode <mode>          Mode. 'heuristic', 'exact' or 'auto'. Defaults to Exact. Any invalid input fails silently
                               to 'heuristic'
    -s, --seed <seed>          Seed used for all rng. Unsigned 64bit integer value. Defaults to '0' if missing
    -t, --timeout <timeout>    Optional timeout value for heuristic algorithm. In heuristic mode the CLI stops on ctrl+c
                               and outputs the current best solution. This might take a few seconds or minutes depending
                               on the size of the input graph. When timeout is set, the algorithm tries to optimize a
                               solution until the timeout is reached

cargo build --release

The Library

Usage

Simply add arboretum-td to your projects cargo.toml under dependencies and get started. For documentation refer to the docs.rs.

References

[1] Hans L. Bodlaender and Arie M. C. A. Koster. 2010. Treewidth computations I. Upper bounds. Inf. Comput. 208, 3 (March, 2010), 259–275. DOI:https://doi.org/10.1016/j.ic.2009.03.008

[2] Bannach, Max & Berndt, Sebastian & Ehlers, Thorsten. (2017). Jdrasil: A Modular Library for Computing Tree Decompositions. 10.4230/LIPIcs.SEA.2017.28.

[3] Hammerl T., Musliu N., Schafhauser W. (2015) Metaheuristic Algorithms and Tree Decomposition. In: Kacprzyk J., Pedrycz W. (eds) Springer Handbook of Computational Intelligence. Springer Handbooks. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-43505-2_64

[4] Bodlaender H.L., Koster A.M.C.A., Wolle T. (2004) Contraction and Treewidth Lower Bounds. In: Albers S., Radzik T. (eds) Algorithms – ESA 2004. ESA 2004. Lecture Notes in Computer Science, vol 3221. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-30140-0_56

[5] Eijkhof, Frank & Bodlaender, Hans. (2002). Safe Reduction Rules for Weighted Treewidth. 176-185.

[6] Hans L. Bodlaender, Arie M.C.A. Koster, Safe separators for treewidth, Discrete Mathematics, Volume 306, Issue 3, 2006, Pages 337-350, ISSN 0012-365X, https://doi.org/10.1016/j.disc.2005.12.017.

[7] Dell, Holger, Komusiewicz, Christian, Talmon, Nimrod, Weller, Mathias "The PACE 2017 Parameterized Algorithms and Computational Experiments Challenge: The Second Iteration" (2018) DOI: 10.4230/LIPIcs.IPEC.2017.30

[8] Tamaki, H.. “Positive-instance driven dynamic programming for treewidth.” ESA (2017).

[9] Bannach, Max and Sebastian Berndt. “Positive-Instance Driven Dynamic Programming for Graph Searching.” WADS (2019).

License

This Software is licensed under the MIT-License which can be found in the LICENSE file in this repository.