2026-07-24T08:00:49Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18569 2024-03-06T11:02:09Z ddc:004 open_access

Tight Algorithmic Applications of Clique-Width Generalizations Chekan, Vera Kratsch, Stefan Parameterized complexity connectivity problems clique-width In this work, we study two natural generalizations of clique-width introduced by Martin Fürer. Multi-clique-width (mcw) allows every vertex to hold multiple labels [ITCS 2017], while for fusion-width (fw) we have a possibility to merge all vertices of a certain label [LATIN 2014]. Fürer has shown that both parameters are upper-bounded by treewidth thus making them more appealing from an algorithmic perspective than clique-width and asked for applications of these parameters for problem solving. First, we determine the relation between these two parameters by showing that mcw ≤ fw + 1. Then we show that when parameterized by multi-clique-width, many problems (e.g., Connected Dominating Set) admit algorithms with the same running time as for clique-width despite the exponential gap between these two parameters. For some problems (e.g., Hamiltonian Cycle) we show an analogous result for fusion-width: For this we present an alternative view on fusion-width by introducing so-called glue-expressions which might be interesting on their own. All algorithms obtained in this work are tight up to (Strong) Exponential Time Hypothesis. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Vera Chekan and Stefan Kratsch 2023 Is Part Of LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2023.35 urn:nbn:de:0030-drops-185699 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.35 eng https://creativecommons.org/licenses/by/4.0/legalcode