2026-08-01T04:27:36Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19456 2024-03-06T11:04:06Z ddc:004 open_access

PACE Solver Description: Exact (GUTHMI) and Heuristic (GUTHM) Leonhardt, Alexander Dell, Holger Haak, Anselm Kammer, Frank Meintrup, Johannes Meyer, Ulrich Penschuck, Manuel PACE 2023 Challenge Heuristic Exact Twin-Width Twin-width (tww) is a parameter measuring the similarity of an undirected graph to a co-graph [Édouard Bonnet et al., 2022]. It is useful to analyze the parameterized complexity of various graph problems. This paper presents two algorithms to compute the twin-width and to provide a contraction sequence as witness. The two algorithms are motivated by the PACE 2023 challenge, one for the exact track and one for the heuristic track. Each algorithm produces a contraction sequence witnessing (i) the minimal twin-width admissible by the graph in the exact track (ii) an upper bound on the twin-width as tight as possible in the heuristic track. Our heuristic algorithm relies on several greedy approaches with different performance characteristics to find and improve solutions. For large graphs we use locality sensitive hashing to approximately identify suitable contraction candidates. The exact solver follows a branch-and-bound design. It relies on the heuristic algorithm to provide initial upper bounds, and uses lower bounds via contraction sequences to show the optimality of a heuristic solution found in some branch. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Alexander Leonhardt and Holger Dell and Anselm Haak and Frank Kammer and Johannes Meintrup and Ulrich Meyer and Manuel Penschuck 2023 Is Part Of LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2023.37 urn:nbn:de:0030-drops-194563 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.37 eng https://creativecommons.org/licenses/by/4.0/legalcode