Bute: A Bottom-Up Exact Solver for Treedepth (Submitted to PACE 2020 under username peaty)
share
This note introduces the exact solver Bute for the exact treedepth problem, along with two variants of the solver. Each of these solvers computes an elimination tree in a bottom-up fashion by finding sets of vertices that induce subgraphs of small treedepth, then combining sets of vertices together with a root vertex to produce larger sets. The algorithms make use of a trie data structure to reduce the effort required to determine acceptable combinations of subtrees. Bute-Plus and Bute-Plus-Plus add a heuristic presolve step, which can quickly find a treedepth decomposition of optimal depth for many instances.
READ FULL TEXT