Talks and Poster Presentations (with Proceedings-Entry):
V. Ramaswamy, S. Szeider:
"MaxSAT-Based Postprocessing for Treedepth";
Talk: International Conference on Principles and Practice of Constraint Programming (CP),
Louvain-la-Neuve, Belgium;
2020-09-07
- 2020-09-11; in: "CP 2020: Principles and Practice of Constraint Programming",
LNCS,
12333
(2020),
ISBN: 978-3-030-58474-0;
478
- 495.
English abstract:
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.
"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
http://dx.doi.org/10.1007/978-3-030-58475-7_28
Electronic version of the publication:
https://publik.tuwien.ac.at/files/publik_292406.pdf
Created from the Publication Database of the Vienna University of Technology.