2026-07-23T22:19:41Z https://drops.dagstuhl.de/oai

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

PACE Solver Description: Zygosity Arrighi, Emmanuel Drange, Pål Grønås Langedal, Kenneth Vadiee, Farhad Vatshelle, Martin Wolf, Petra Twin-width randomized greedy algorithm The graph parameter twin-width was recently introduced by Bonnet et al. Twin-width is a parameter that measures a graph’s similarity to a cograph, which is a graph that can be reduced to a single vertex by repeatedly contracting twins. This brief description introduces Zygosity, a heuristic for computing a low-width contraction sequence that achieved second place in the 2023 edition of Parameterized Algorithms and Computational Experiments Challenge (PACE). Zygosity starts by repeatedly contracting twins. Then, any attached trees are contracted down to a single pendant vertex. The remaining graph is then contracted using a randomized greedy algorithm. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Emmanuel Arrighi and Pål Grønås Drange and Kenneth Langedal and Farhad Vadiee and Martin Vatshelle and Petra Wolf 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.39 urn:nbn:de:0030-drops-194583 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.39 eng https://creativecommons.org/licenses/by/4.0/legalcode