License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2019.17
URN: urn:nbn:de:0030-drops-111383
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11138/
Go to the corresponding LIPIcs Volume Portal

Bergougnoux, Benjamin ; Kanté, Mamadou Moustapha

More Applications of the d-Neighbor Equivalence: Connectivity and Acyclicity Constraints

pdf-format:
LIPIcs-ESA-2019-17.pdf (0.6 MB)

Abstract

In this paper, we design a framework to obtain efficient algorithms for several problems with a global constraint (acyclicity or connectivity) such as Connected Dominating Set, Node Weighted Steiner Tree, Maximum Induced Tree, Longest Induced Path, and Feedback Vertex Set. For all these problems, we obtain 2^O(k)* n^O(1), 2^O(k log(k))* n^O(1), 2^O(k^2) * n^O(1) and n^O(k) time algorithms parameterized respectively by clique-width, Q-rank-width, rank-width and maximum induced matching width. Our approach simplifies and unifies the known algorithms for each of the parameters and match asymptotically also the running time of the best algorithms for basic NP-hard problems such as Vertex Cover and Dominating Set. Our framework is based on the d-neighbor equivalence defined in [Bui-Xuan, Telle and Vatshelle, TCS 2013]. The results we obtain highlight the importance and the generalizing power of this equivalence relation on width measures. We also prove that this equivalence relation could be useful for Max Cut: a W[1]-hard problem parameterized by clique-width. For this latter problem, we obtain n^O(k), n^O(k) and n^(2^O(k)) time algorithm parameterized by clique-width, Q-rank-width and rank-width.

BibTeX - Entry

@InProceedings{bergougnoux_et_al:LIPIcs:2019:11138,
  author =	{Benjamin Bergougnoux and Mamadou Moustapha Kant{\'e}},
  title =	{{More Applications of the d-Neighbor Equivalence: Connectivity and Acyclicity Constraints}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{17:1--17:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Michael A. Bender and Ola Svensson and Grzegorz Herman},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/11138},
  URN =		{urn:nbn:de:0030-drops-111383},
  doi =		{10.4230/LIPIcs.ESA.2019.17},
  annote =	{Keywords: connectivity problem, feedback vertex set, d-neighbor equivalence, {sigma,rho}-domination, clique-width, rank-width, mim-width}
}

Keywords: connectivity problem, feedback vertex set, d-neighbor equivalence, {sigma,rho}-domination, clique-width, rank-width, mim-width
Collection: 27th Annual European Symposium on Algorithms (ESA 2019)
Issue Date: 2019
Date of publication: 06.09.2019

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