Talks and Poster Presentations (with Proceedings-Entry):

J. Fichte, M. Hecher, S. Szeider:
"Breaking Symmetries with RootClique and LexTopSort";
Talk: CP 2020 - 26th International Conference - Principles and Practice of Constraint Programming, Louvain-laNeuve, Belgium; 2020-09-07 - 2020-09-11; in: "Principles and Practice of Constraint Programming - 26th International Conference, {CP} 2020, Louvain-la-Neuve, Belgium, September 7-11, 2020, Proceedings", (2020), 286 - 303.

English abstract:
Bounded fractional hypertree width is the most general known structural property that guarantees polynomial-time solvability of the constraint satisfaction problem. Fichte et al. (CP 2018) presented a robust and scalable method for finding optimal fractional hypertree decompositions, based on an encoding to SAT Modulo Theory (SMT). In this paper, we provide an in-depth study of two powerful symmetry breaking predicates that allow us to further speed up the SMT-based decomposition: RootClique fixes the root of the decomposition tree; LexTopSort fixes the elimination ordering with respect to an underlying DAG. We perform an extensive empirical evaluation of both symmetry-breaking predicates with respect to the primal graph (which is known in advance) and the induced graph (which is generated during the search).

Symmetry breaking Hypergraphs Elimination orderings SAT Modulo Theory

"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)

Related Projects:
Project Head Stefan Woltran:

Project Head Stefan Woltran:

Created from the Publication Database of the Vienna University of Technology.