Turbocharging twin-width heuristics with SAT

Abstract

Twin-Width ist eine neuartige Graphinvariante, die in mancher Hinsicht Tree Width und Rank Width ähnelt. Sie misst in gewisser Weise, wie weit ein Graph davon entfernt ist, ein Cograph zu sein. Dafür werden iterativ zwei Knoten kontrahiert und die Differenz ihrer Nachbarschaften wird mit roten Kanten aufgezeichnet. Liegt ein Zertifikat über begrenzte Twin-Width eines Graphen vor, werden darauf viele NP-schwere Probleme handhabbar. Das Finden solch eines Zertifikats ist jedoch auch NP-schwer. In dieser Arbeit verbesseren wir Greedy-Heuristiken für Obergrenzen für Twin-Width durch Turbocharging. Dabei wird ein exakter Algorithmus, der Turbocharging Algorithmus, auf ein Unterproblem angewendet, wodurch der Heuristik geholfen wird, wenn die Qualität der Lösung zu niedrig wird. Wir entwickeln SAT-Encodings für den Turbocharging Algorithmus und wenden diese auf zwei Greedy-Heuristiken an.In unseren Experimenten ist unsere Methode in der Lage, die Obergrenzen der Grundheuristiken für Graphen verschiedenster Größen zu verbessern. Wir vergleichen sie auch mit einer randomisierten Methode von Berthe et al., um einen Vergleich zum State of the Art herzustellen. Unsere Heuristiken sind in der Lage, diesen randomisierten Algorithmus besonders bei großen Graphen signifikant zu übertreffen. Auf kleinen Graphen liefert der randomisierten Ansatz jedoch bessere Ergebnisse.Heuristiken für Obergrenzen für Twin-Width sind wertvoll sowohl für exakte Algorithmen, als auch zum Finden von Zertifikaten über begrenzte Twin-Width für Graphen, für die exakte Algorithmen zu langsam sind. Besonders für den zweiten Fall eignet sich unser Ansatz, da er Ergebnisse von Greedy-Heuristiken signifikant verbessern kann. Das ist besonders für größere Graphen der Fall.

Twin-width is a novel graph invariant, in some ways similar to tree width and rank width. In a way, it measures how far a graph is from being a cograph. This is done by iteratively contracting two vertices and keeping track of the edges that separate them from having the same neighborhood using red edges. Given a certificate for bounded twin-width of a graph, many NP-hard problems become tractable on it. However, determining the twin-width and obtaining a certificate is an NP-hard problem itself.In this thesis we improve greedy upper bound heuristics for twin-width using turbocharging. This involves using an exact approach for a subproblem, the turbocharging algorithm, to aid the heuristic if the solution quality gets too low at some point. We develop SAT encodings for the turbocharging algorithm and apply them to two greedy heuristics.In our experiments, our turbocharged approach was able to improve the upper bounds of the base heuristics across different instance sizes. We further compare it to a randomized approach by Berthe et al. Particularly for large instances, our turbocharged heuristic outperformed this approach significantly, while the randomized algorithm delivered better results on small instances.Upper bound heuristics for twin-width are valuable for both exact algorithms and to obtain certificates for bounded twin-width for graphs which are too large for exact algorithm to handle. Especially for the second use case, our approach is well suited, as it manages to improve upon solutions obtained by greedy heuristics significantly. This is particularly the case for larger graphs.