[Zurück]

V. Ramaswamy, S. Szeider:
"MaxSAT-Based Postprocessing for Treedepth";
Vortrag: International Conference on Principles and Practice of Constraint Programming (CP), Louvain-la-Neuve, Belgium; 07.09.2020 - 11.09.2020; in: "CP 2020: Principles and Practice of Constraint Programming", LNCS, 12333 (2020), ISBN: 978-3-030-58474-0; S. 478 - 495.

Treedepth is an increasingly popular graph invariant. Many
NP-hard combinatorial problems can be solved efficiently on graphs of
bounded treedepth. Since the exact computation of treedepth is itself
NP-hard, recent research has focused on the development of heuristics
that compute good upper bounds on the treedepth.
In this paper, we introduce a novel MaxSAT-based approach for
improving a heuristically obtained treedepth decomposition. At the core
of our approach is an efficient MaxSAT encoding of a weighted generalization
of treedepth arising naturally due to subtree contractions.
The encoding is applied locally to the given treedepth decomposition
to reduce its depth, in conjunction with the collapsing of subtrees. We
show the local improvement method´s correctness and provide an extensive
experimental evaluation with some encouraging results.

http://dx.doi.org/10.1007/978-3-030-58475-7_28

https://publik.tuwien.ac.at/files/publik_292406.pdf