DROPS

Document

DOI: 10.4230/LIPIcs.FSTTCS.2014.73

Connecting Vertices by Independent Trees

Authors: Manu Basavaraju, Fedor V. Fomin, Petr A. Golovach, and Saket Saurabh

Published in: LIPIcs, Volume 29, 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)

Abstract

We study the paramereteized complexity of the following connectivity problem. For a vertex subset U of a graph G, trees T_1,...,T_s of G are completely independent spanning trees of U if each of them contains U, and for every two distinct vertices u,v in U, the paths from u to v in T_1,...,T_s are pairwise vertex disjoint except for end-vertices u and v. Then for a given s >= 2 and a parameter k, the task is to decide if a given n-vertex graph G contains a set U of size at least k such that there are s completely independent spanning trees of U. The problem is known to be NP-complete already for s=2. We prove the following results: (*) For s=2 the problem is solvable in time 2^{O(k)}*n^{O(1)}. (*) For s=2 the problem does not admit a polynomial kernel unless NP subseteq coNP/poly. (*) For arbitrary s, we show that the problem is solvable in time f(s,k)n^{O(1)} for some function f of s and k only.

Cite as

Manu Basavaraju, Fedor V. Fomin, Petr A. Golovach, and Saket Saurabh. Connecting Vertices by Independent Trees. In 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 29, pp. 73-84, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{basavaraju_et_al:LIPIcs.FSTTCS.2014.73,
  author =	{Basavaraju, Manu and Fomin, Fedor V. and Golovach, Petr A. and Saurabh, Saket},
  title =	{{Connecting Vertices by Independent Trees}},
  booktitle =	{34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)},
  pages =	{73--84},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-77-4},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{29},
  editor =	{Raman, Venkatesh and Suresh, S. P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2014.73},
  URN =		{urn:nbn:de:0030-drops-48340},
  doi =		{10.4230/LIPIcs.FSTTCS.2014.73},
  annote =	{Keywords: Parameterized complexity, FPT-algorithms, completely independent spanning trees}
}

Document

DOI: 10.4230/LIPIcs.FSTTCS.2013.67

Partially Polynomial Kernels for Set Cover and Test Cover

Authors: Manu Basavaraju, Mathew C. Francis, M. S. Ramanujan, and Saket Saurabh

Published in: LIPIcs, Volume 24, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)

Abstract

In a typical covering problem we are given a universe U of size n, a family S (S could be given implicitly) of size m and an integer k and the objective is to check whether there exists a subfamily S' \subseteq S of size at most k satisfying some desired properties. If S' is required to contain all the elements of U then it corresponds to the classical Set Cover problem. On the other hand if we require S' to satisfy the property that for every pair of elements x,y \in U there exists a set S \in S' such that |S \cap {x,y}|=1 then it corresponds to the Test Cover problem. In this paper we consider a natural parameterization of Set Cover and Test Cover. More precisely, we study the (n-k)-Set Cover and (n-k)-Test Cover problems, where the objective is to find a subfamily S' of size at most n-k satisfying the respective properties, from the kernelization perspective. It is known in the literature that both (n-k)-Set Cover and (n-k)-Test Cover do not admit polynomial kernels (under some well known complexity theoretic assumptions). However, in this paper we show that they do admit "partially polynomial kernels". More precisely, we give polynomial time algorithms that take as input an instance (U,S,k) of (n-k)-Set Cover (n-k)-Test Cover) and return an equivalent instance (~U,~S,~k) of (n-k)-Set Cover (respectively (n-k)-Test Cover) with ~k <= k and |~U|= O(k^2) (|~U|=O(k^7)). These results allow us to generalize, improve and unify several results known in the literature. For example, these immediately imply traditional kernels when input instances satisfy certain "sparsity properties". Using a part of our kernelization algorithm for (n-k)-Set Cover, we also get an improved FPT algorithm for this problem which runs in time O(4^k*k^{\O(1)}*(m+n)) improving over the previous best of O(8^{k+o(k)}*(m+n)^{O(1)}). On the other hand the partially polynomial kernel for (n-k)-Test Cover implies the first single exponential FPT algorithm, an algorithm with running time O(2^{O(k^2)}*(m+n)^{O(1)}). We believe such an approach will also be useful for other covering problems as well.

Cite as

Manu Basavaraju, Mathew C. Francis, M. S. Ramanujan, and Saket Saurabh. Partially Polynomial Kernels for Set Cover and Test Cover. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 67-78, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{basavaraju_et_al:LIPIcs.FSTTCS.2013.67,
  author =	{Basavaraju, Manu and Francis, Mathew C. and Ramanujan, M. S. and Saurabh, Saket},
  title =	{{Partially Polynomial Kernels for Set Cover and Test Cover}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
  pages =	{67--78},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-64-4},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{24},
  editor =	{Seth, Anil and Vishnoi, Nisheeth K.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.67},
  URN =		{urn:nbn:de:0030-drops-43621},
  doi =		{10.4230/LIPIcs.FSTTCS.2013.67},
  annote =	{Keywords: Set Cover, Test Cover, Kernelization, Parameterized Algorithms}
}

Search Results

Documents authored by Basavaraju, Manu

Connecting Vertices by Independent Trees

Abstract

Cite as

Partially Polynomial Kernels for Set Cover and Test Cover

Abstract

Cite as

Thanks for your feedback!

Could not send message