sallow

A heuristic algorithm for finding treedepth decompositions.

This is a submission for the PACE 2020 challenge. The algorithm relies on:

• a variety of greedy elimination algorithms, and
• Divide & Conquer along cuts obtained using a from-scratch reimplementation of Ben Strasser's 2016 FlowCutter, which is excellently described in the paper Graph Bisection with Pareto Optimization.

The short paper Sallow – a heuristic algorithm for treedepth decompositions gives a more detailed overview. Cite as, e.g.:

@misc{Wrochna20sallow,
  author        = {Marcin Wrochna},
  title         = {Sallow -- a heuristic algorithm for treedepth decompositions},
  year          = {2020},
  archivePrefix = {arXiv},
  eprint        = {2006.07050}
}

Sallows (such as Salix caprea) are willows, a kind of shrub/small tree.

(Photo by AnRo0002)

Git

This repo uses submodules:

• clone with git clone --recurse-submodules git@github.com:marcinwrochna/sallow.git
• if you want, update all submodules with git submodule update --remote --rebase (this fetches to master and tries to rebase your existing changes within each submodule)

Currently the only dependency used is Microsoft's implementation of the C++ Guidelines Support Library.

Building

Standard CMake:

• mkdir build && cd build (or wherever you want the build files to be, instead of build/)
• cmake --config Release .. (or whatever the path to the root CMakeLists.txt is, instead of ..)
• make
• Or just open the directory in MSVS Code with the CMake extension installed, and allow it to configure itself.
• CMake ≥ 3.13 and g++ ≥ 7 or clang ≥ 4 (that is, supporting C++17) are required.
• Change -march=ivybridge to native or remove, if needed, in CMakeLists.txt.

Running

• sallow input.gr
• Interrupt (ctrl+c or SIGINT) to stop and print the best decomposition we have.
• If it hangs (e.g. you ran it in debug mode on extremely large graphs), you need to pkill -9 sallow.
• Input and output format as specified here (DIMACS-like).
• See there also for test instances.

Acknowledgements

The author is very grateful to the PACE 2020 organizers at the University of Warsaw and the OPTIL.io team at the Poznań University of Technology for making this challenge possible. This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 714532, PI: Stanislav Živný).