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


Jacob, Ashwin ; Panolan, Fahad ; Raman, Venkatesh ; Sahlot, Vibha

Structural Parameterizations with Modulator Oblivion

pdf-format:
LIPIcs-IPEC-2020-19.pdf (0.6 MB)


Abstract

It is known that problems like Vertex Cover, Feedback Vertex Set and Odd Cycle Transversal are polynomial time solvable in the class of chordal graphs. We consider these problems in a graph that has at most k vertices whose deletion results in a chordal graph, when parameterized by k. While this investigation fits naturally into the recent trend of what are called "structural parameterizations", here we assume that the deletion set is not given.
One method to solve them is to compute a k-sized or an approximate (f(k) sized, for a function f) chordal vertex deletion set and then use the structural properties of the graph to design an algorithm. This method leads to at least k^O(k)n^O(1) running time when we use the known parameterized or approximation algorithms for finding a k-sized chordal deletion set on an n vertex graph.
In this work, we design 2^O(k)n^O(1) time algorithms for these problems. Our algorithms do not compute a chordal vertex deletion set (or even an approximate solution). Instead, we construct a tree decomposition of the given graph in time 2^O(k)n^O(1) where each bag is a union of four cliques and O(k) vertices. We then apply standard dynamic programming algorithms over this special tree decomposition. This special tree decomposition can be of independent interest.
Our algorithms are, what are sometimes called permissive in the sense that given an integer k, they detect whether the graph has no chordal vertex deletion set of size at most k or output the special tree decomposition and solve the problem.
We also show lower bounds for the problems we deal with under the Strong Exponential Time Hypothesis (SETH).

BibTeX - Entry

@InProceedings{jacob_et_al:LIPIcs:2020:13322,
  author =	{Ashwin Jacob and Fahad Panolan and Venkatesh Raman and Vibha Sahlot},
  title =	{{Structural Parameterizations with Modulator Oblivion}},
  booktitle =	{15th International Symposium on Parameterized and Exact Computation (IPEC 2020)},
  pages =	{19:1--19:18},
  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/13322},
  URN =		{urn:nbn:de:0030-drops-133222},
  doi =		{10.4230/LIPIcs.IPEC.2020.19},
  annote =	{Keywords: Parameterized Complexity, Chordal Graph, Tree Decomposition, Strong Exponential Time Hypothesis}
}

Keywords: Parameterized Complexity, Chordal Graph, Tree Decomposition, Strong Exponential Time Hypothesis
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