License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2023.35
URN: urn:nbn:de:0030-drops-185699
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18569/
Go to the corresponding LIPIcs Volume Portal

Chekan, Vera ; Kratsch, Stefan

Tight Algorithmic Applications of Clique-Width Generalizations

pdf-format:
LIPIcs-MFCS-2023-35.pdf (0.7 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{chekan_et_al:LIPIcs.MFCS.2023.35,
  author =	{Chekan, Vera and Kratsch, Stefan},
  title =	{{Tight Algorithmic Applications of Clique-Width Generalizations}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{35:1--35:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18569},
  URN =		{urn:nbn:de:0030-drops-185699},
  doi =		{10.4230/LIPIcs.MFCS.2023.35},
  annote =	{Keywords: Parameterized complexity, connectivity problems, clique-width}
}

Keywords: Parameterized complexity, connectivity problems, clique-width
Collection: 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)
Issue Date: 2023
Date of publication: 21.08.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI