A heuristic approach to the treedepth decomposition problem for large graphs
[ 1 ] Instytut Informatyki, Wydział Informatyki i Telekomunikacji, Politechnika Poznańska | [ P ] employee
2021
chapter in monograph / paper
english
- treedepth decomposition
- elimination tree
- separator
EN In this article, we describe algorithms and techniques used in the method ExTREEm for the treedepth decomposition problem. ExTREEm won the heuristic track of the 5th Parameterized Algorithms and Computational Experiments Challenge (PACE 2020). It searches for a minimum-height treedepth decomposition of a graph via computing graph separators. Among concepts that are incorporated into the approach, we can distinguish a new objective function for evaluating separators, preprocessing based on finding treedepth decompositions in cactus subgraphs and on identification of graphlets, five algorithms for finding separators, a separator minimization method for a refinement of found separators, and a refinement of an obtained treedepth decomposition by merging techniques of tree rotations. This approach enables us to quickly obtain low-depth decompositions of very large graphs.
20.09.2021
169 - 181
20
140