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.IPEC.2020.3
URN: urn:nbn:de:0030-drops-133066
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/13306/
Go to the corresponding LIPIcs Volume Portal

Bergougnoux, Benjamin ; Bonnet, Édouard ; Brettell, Nick ; Kwon, O-joung

Close Relatives of Feedback Vertex Set Without Single-Exponential Algorithms Parameterized by Treewidth

pdf-format:
LIPIcs-IPEC-2020-3.pdf (0.7 MB)

Abstract

The Cut & Count technique and the rank-based approach have lead to single-exponential FPT algorithms parameterized by treewidth, that is, running in time 2^?(tw)n^?(1), for Feedback Vertex Set and connected versions of the classical graph problems (such as Vertex Cover and Dominating Set). We show that Subset Feedback Vertex Set, Subset Odd Cycle Transversal, Restricted Edge-Subset Feedback Edge Set, Node Multiway Cut, and Multiway Cut are unlikely to have such running times. More precisely, we match algorithms running in time 2^?(tw log tw)n^?(1) with tight lower bounds under the Exponential Time Hypothesis, ruling out 2^o(tw log tw)n^?(1), where n is the number of vertices and tw is the treewidth of the input graph. Our algorithms extend to the weighted case, while our lower bounds also hold for the larger parameter pathwidth and do not require weights. We also show that, in contrast to Odd Cycle Transversal, there is no 2^o(tw log tw)n^?(1)-time algorithm for Even Cycle Transversal.

BibTeX - Entry

@InProceedings{bergougnoux_et_al:LIPIcs:2020:13306,
  author =	{Benjamin Bergougnoux and {\'E}douard Bonnet and Nick Brettell and O-joung Kwon},
  title =	{{Close Relatives of Feedback Vertex Set Without Single-Exponential Algorithms Parameterized by Treewidth}},
  booktitle =	{15th International Symposium on Parameterized and Exact Computation (IPEC 2020)},
  pages =	{3:1--3:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-172-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{180},
  editor =	{Yixin Cao and Marcin Pilipczuk},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/13306},
  URN =		{urn:nbn:de:0030-drops-133066},
  doi =		{10.4230/LIPIcs.IPEC.2020.3},
  annote =	{Keywords: Subset Feedback Vertex Set, Multiway Cut, Parameterized Algorithms, Treewidth, Graph Modification, Vertex Deletion Problems}
}

Keywords: Subset Feedback Vertex Set, Multiway Cut, Parameterized Algorithms, Treewidth, Graph Modification, Vertex Deletion Problems
Collection: 15th International Symposium on Parameterized and Exact Computation (IPEC 2020)
Issue Date: 2020
Date of publication: 04.12.2020

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