2026-07-28T23:06:17Z https://drops.dagstuhl.de/oai

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

PACE Solver Description: Hydra Prime Mizutani, Yosuke Dursteler, David Sullivan, Blair D. Twin-width PACE 2023 This note describes our submission to the 2023 PACE Challenge on the computation of twin-width. Our solver Hydra Prime combines modular decomposition with a collection of upper- and lower-bound algorithms, which are alternatingly applied on the prime graphs resulting from the modular decomposition. We introduce two novel approaches which contributed to the solver’s winning performance in the Exact Track: timeline encoding and hydra decomposition. Timeline encoding is a new data structure for computing the width of a given contraction sequence, enabling faster local search; the hydra decomposition is an iterative refinement strategy featuring a small vertex separator. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yosuke Mizutani and David Dursteler and Blair D. Sullivan 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.36 urn:nbn:de:0030-drops-194552 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.36 eng https://creativecommons.org/licenses/by/4.0/legalcode