DROPS

Document

DOI: 10.4230/LIPIcs.IPEC.2020.19

Structural Parameterizations with Modulator Oblivion

Authors: Ashwin Jacob, Fahad Panolan, Venkatesh Raman, and Vibha Sahlot

Published in: LIPIcs, Volume 180, 15th International Symposium on Parameterized and Exact Computation (IPEC 2020)

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).

Cite as

Ashwin Jacob, Fahad Panolan, Venkatesh Raman, and Vibha Sahlot. Structural Parameterizations with Modulator Oblivion. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 19:1-19:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{jacob_et_al:LIPIcs.IPEC.2020.19,
  author =	{Jacob, Ashwin and Panolan, Fahad and Raman, Venkatesh and Sahlot, Vibha},
  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 =	{Cao, Yixin and Pilipczuk, Marcin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2020.19},
  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}
}

Document

DOI: 10.4230/LIPIcs.FSTTCS.2016.32

Fréchet Distance Between a Line and Avatar Point Set

Authors: Aritra Banik, Fahad Panolan, Venkatesh Raman, and Vibha Sahlot

Published in: LIPIcs, Volume 65, 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)

Abstract

Frechet distance is an important geometric measure that captures the distance between two curves or more generally point sets. In this paper, we consider a natural variant of Frechet distance problem with multiple choice, provide an approximation algorithm and address its parameterized and kernelization complexity. A multiple choice problem consists of a set of color classes Q={Q_1,Q_2,...,Q_n}, where each class Q_i consists of a pair of points Q_i = {q_i, bar{q_i}}. We call a subset A subset {q_i , bar{q_i}:1 <= i <= n} conflict free if A contains at most one point from each color class. The standard objective in multiple choice problem is to select a conflict free subset that optimizes a given function. Given a line segment l and set Q of a pair of points in R^2, our objective is to find a conflict free subset that minimizes the Frechet distance between l and the point set, where the minimum is taken over all possible conflict free subsets. We first show that this problem is NP-hard, and provide a 3-approximation algorithm. Then we develop a simple randomized FPT algorithm which is later derandomized using universal family of sets. We believe that this technique can be of independent interest, and can be used to solve other parameterized multiple choice problems. The randomized algorithm runs in O(2^k * n * log^2(n)) time, and the derandomized deterministic algorithm runs in O(2^k * k^{O(log(k))} * n * log^2(n)) time, where k, the parameter, is the number of elements in the conflict free subset solution. Finally we present a simple branching algorithm for the problem running in O(2^k * n^{2} *log(n)) time. We also show that the problem is unlikely to have a polynomial sized kernel under standard complexity theoretic assumption.

Cite as

Aritra Banik, Fahad Panolan, Venkatesh Raman, and Vibha Sahlot. Fréchet Distance Between a Line and Avatar Point Set. In 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 65, pp. 32:1-32:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{banik_et_al:LIPIcs.FSTTCS.2016.32,
  author =	{Banik, Aritra and Panolan, Fahad and Raman, Venkatesh and Sahlot, Vibha},
  title =	{{Fr\'{e}chet Distance Between a Line and Avatar Point Set}},
  booktitle =	{36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)},
  pages =	{32:1--32:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-027-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{65},
  editor =	{Lal, Akash and Akshay, S. and Saurabh, Saket and Sen, Sandeep},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2016.32},
  URN =		{urn:nbn:de:0030-drops-68676},
  doi =		{10.4230/LIPIcs.FSTTCS.2016.32},
  annote =	{Keywords: Frechet Distance, Avatar Problems, Multiple Choice, FPT}
}

Search Results

Documents authored by Sahlot, Vibha

Structural Parameterizations with Modulator Oblivion

Abstract

Cite as

Fréchet Distance Between a Line and Avatar Point Set

Abstract

Cite as

Thanks for your feedback!

Could not send message