Search Results

Documents authored by Raman, Venkatesh

Document
DOI: 10.4230/LIPIcs.IPEC.2020.18
Parameterized Complexity of Deletion to Scattered Graph Classes

Authors: Ashwin Jacob, Diptapriyo Majumdar, and Venkatesh Raman

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

Abstract
Graph-modification problems, where we add/delete a small number of vertices/edges to make the given graph to belong to a simpler graph class, is a well-studied optimization problem in all algorithmic paradigms including classical, approximation and parameterized complexity. Specifically, graph-deletion problems, where one needs to delete at most k vertices to place it in a given non-trivial hereditary (closed under induced subgraphs) graph class, captures several well-studied problems including Vertex Cover, Feedback Vertex Set, Odd Cycle Transveral, Cluster Vertex Deletion, and Perfect Deletion. Investigation into these problems in parameterized complexity has given rise to powerful tools and techniques. While a precise characterization of the graph classes for which the problem is fixed-parameter tractable (FPT) is elusive, it has long been known that if the graph class is characterized by a finite set of forbidden graphs, then the problem is FPT. In this paper, we initiate a study of a natural variation of the problem of deletion to scattered graph classes where we need to delete at most k vertices so that in the resulting graph, each connected component belongs to one of a constant number of graph classes. A simple hitting set based approach is no longer feasible even if each of the graph classes is characterized by finite forbidden sets. As our main result, we show that this problem (in the case where each graph class has a finite forbidden set) is fixed-parameter tractable by a O^*(2^(k^O(1))) algorithm, using a combination of the well-known techniques in parameterized complexity - iterative compression and important separators. Our approach follows closely that of a related problem in the context of satisfiability [Ganian, Ramanujan, Szeider, TAlg 2017], where one wants to find a small backdoor set so that the resulting CSP (constraint satisfaction problem) instance belongs to one of several easy instances of satisfiability. While we follow the main idea from this work, there are some challenges for our problem which we needed to overcome. When there are two graph classes with finite forbidden sets to get to, and if one of the forbidden sets has a path, then we show that the problem has a (better) singly exponential algorithm and a polynomial sized kernel. We also design an efficient FPT algorithm for a special case when one of the graph classes has an infinite forbidden set. Specifically, we give a O^*(4^k) algorithm to determine whether k vertices can be deleted from a given graph so that in the resulting graph, each connected component is a tree (the sparsest connected graph) or a clique (the densest connected graph).
Cite as

Ashwin Jacob, Diptapriyo Majumdar, and Venkatesh Raman. Parameterized Complexity of Deletion to Scattered Graph Classes. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 18:1-18:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{jacob_et_al:LIPIcs.IPEC.2020.18,
  author =	{Jacob, Ashwin and Majumdar, Diptapriyo and Raman, Venkatesh},
  title =	{{Parameterized Complexity of Deletion to Scattered Graph Classes}},
  booktitle =	{15th International Symposium on Parameterized and Exact Computation (IPEC 2020)},
  pages =	{18:1--18:17},
  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.18},
  URN =		{urn:nbn:de:0030-drops-133210},
  doi =		{10.4230/LIPIcs.IPEC.2020.18},
  annote =	{Keywords: Parameterized Complexity, Scattered Graph Classes, Important Separators}
}
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.2020.10
Optimal Output Sensitive Fault Tolerant Cuts

Authors: Niranka Banerjee, Venkatesh Raman, and Saket Saurabh

Published in: LIPIcs, Volume 182, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)

Abstract
In this paper we consider two classic cut-problems, Global Min-Cut and Min k-Cut, via the lens of fault tolerant network design. In particular, given a graph G on n vertices, and a positive integer f, our objective is to compute an upper bound on the size of the sparsest subgraph H of G that preserves edge connectivity of G (denoted by λ(G)) in the case of Global Min-Cut, and λ(G,k) (denotes the minimum number of edges whose removal would partition the graph into at least k connected components) in the case of Min k-Cut, upon failure of any f edges of G. The subgraph H corresponding to Global Min-Cut and Min k-Cut is called f-FTCS and f-FT-k-CS, respectively. We obtain the following results about the sizes of f-FTCS and f-FT-k-CS. - There exists an f-FTCS with (n-1)(f+λ(G)) edges. We complement this upper bound with a matching lower bound, by constructing an infinite family of graphs where any f-FTCS must have at least ((n-λ(G)-1)(λ(G)+f-1))/2+(n-λ(G)-1)+/λ(G)(λ(G)+1))/2 edges. - There exists an f-FT-k-CS with min{(2f+λ(G,k)-(k-1))(n-1), (f+λ(G,k))(n-k)+𝓁} edges. We complement this upper bound with a lower bound, by constructing an infinite family of graphs where any f-FT-k-CS must have at least ((n-λ(G,k)-1)(λ(G,k)+f-k+1))/2)+n-λ(G,k)+k-3+((λ(G,k)-k+3)(λ(G,k)-k+2))/2 edges. Our upper bounds exploit the structural properties of k-connectivity certificates. On the other hand, for our lower bounds we construct an infinite family of graphs, such that for any graph in the family any f-FTCS (or f-FT-k-CS) must contain all its edges. We also add that our upper bounds are constructive. That is, there exist polynomial time algorithms that construct H with the aforementioned number of edges.
Cite as

Niranka Banerjee, Venkatesh Raman, and Saket Saurabh. Optimal Output Sensitive Fault Tolerant Cuts. In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 182, pp. 10:1-10:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{banerjee_et_al:LIPIcs.FSTTCS.2020.10,
  author =	{Banerjee, Niranka and Raman, Venkatesh and Saurabh, Saket},
  title =	{{Optimal Output Sensitive Fault Tolerant Cuts}},
  booktitle =	{40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)},
  pages =	{10:1--10:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-174-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{182},
  editor =	{Saxena, Nitin and Simon, Sunil},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2020.10},
  URN =		{urn:nbn:de:0030-drops-132515},
  doi =		{10.4230/LIPIcs.FSTTCS.2020.10},
  annote =	{Keywords: Fault tolerant, minimum cuts, upper bound, lower bound}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2020.16
Approximation in (Poly-) Logarithmic Space

Authors: Arindam Biswas, Venkatesh Raman, and Saket Saurabh

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Abstract
We develop new approximation algorithms for classical graph and set problems in the RAM model under space constraints. As one of our main results, we devise an algorithm for d–Hitting Set that runs in time n^{O(d² + (d / ε))}, uses O(d² + (d / ε) log n) bits of space, and achieves an approximation ratio of O((d / ε) n^ε) for any positive ε ≤ 1 and any constant d ∈ ℕ. In particular, this yields a factor-O(d log n) approximation algorithm which uses O(log² n) bits of space. As a corollary, we obtain similar bounds on space and approximation ratio for Vertex Cover and several graph deletion problems. For graphs with maximum degree Δ, one can do better. We give a factor-2 approximation algorithm for Vertex Cover which runs in time n^{O(Δ)} and uses O(Δ log n) bits of space. For Independent Set on graphs with average degree d, we give a factor-(2d) approximation algorithm which runs in polynomial time and uses O(log n) bits of space. We also devise a factor-O(d²) approximation algorithm for Dominating Set on d-degenerate graphs which runs in time n^{O(log n)} and uses O(log² n) bits of space. For d-regular graphs, we observe that a known randomized algorithm which achieves an approximation ratio of O(log d) can be derandomized to run in polynomial time and use O(log n) bits of space. Our results use a combination of ideas from the theory of kernelization, distributed algorithms and randomized algorithms.
Cite as

Arindam Biswas, Venkatesh Raman, and Saket Saurabh. Approximation in (Poly-) Logarithmic Space. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 16:1-16:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{biswas_et_al:LIPIcs.MFCS.2020.16,
  author =	{Biswas, Arindam and Raman, Venkatesh and Saurabh, Saket},
  title =	{{Approximation in (Poly-) Logarithmic Space}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{16:1--16:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.16},
  URN =		{urn:nbn:de:0030-drops-126852},
  doi =		{10.4230/LIPIcs.MFCS.2020.16},
  annote =	{Keywords: approximation, logspace, logarithmic, log, space, small, limited, memory, ROM, read-only}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2019.8
Parameterized Streaming Algorithms for Min-Ones d-SAT

Authors: Akanksha Agrawal, Arindam Biswas, Édouard Bonnet, Nick Brettell, Radu Curticapean, Dániel Marx, Tillmann Miltzow, Venkatesh Raman, and Saket Saurabh

Published in: LIPIcs, Volume 150, 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)

Abstract
In this work, we initiate the study of the Min-Ones d-SAT problem in the parameterized streaming model. An instance of the problem consists of a d-CNF formula F and an integer k, and the objective is to determine if F has a satisfying assignment which sets at most k variables to 1. In the parameterized streaming model, input is provided as a stream, just as in the usual streaming model. A key difference is that the bound on the read-write memory available to the algorithm is O(f(k) log n) (f: N -> N, a computable function) as opposed to the O(log n) bound of the usual streaming model. The other important difference is that the number of passes the algorithm makes over its input must be a (preferably small) function of k. We design a (k + 1)-pass parameterized streaming algorithm that solves Min-Ones d-SAT (d >= 2) using space O((kd^(ck) + k^d)log n) (c > 0, a constant) and a (d + 1)^k-pass algorithm that uses space O(k log n). We also design a streaming kernelization for Min-Ones 2-SAT that makes (k + 2) passes and uses space O(k^6 log n) to produce a kernel with O(k^6) clauses. To complement these positive results, we show that any k-pass algorithm for or Min-Ones d-SAT (d >= 2) requires space Omega(max{n^(1/k) / 2^k, log(n / k)}) on instances (F, k). This is achieved via a reduction from the streaming problem POT Pointer Chasing (Guha and McGregor [ICALP 2008]), which might be of independent interest. Given this, our (k + 1)-pass parameterized streaming algorithm is the best possible, inasmuch as the number of passes is concerned. In contrast to the results of Fafianie and Kratsch [MFCS 2014] and Chitnis et al. [SODA 2015], who independently showed that there are 1-pass parameterized streaming algorithms for Vertex Cover (a restriction of Min-Ones 2-SAT), we show using lower bounds from Communication Complexity that for any d >= 1, a 1-pass streaming algorithm for Min-Ones d-SAT requires space Omega(n). This excludes the possibility of a 1-pass parameterized streaming algorithm for the problem. Additionally, we show that any p-pass algorithm for the problem requires space Omega(n/p).
Cite as

Akanksha Agrawal, Arindam Biswas, Édouard Bonnet, Nick Brettell, Radu Curticapean, Dániel Marx, Tillmann Miltzow, Venkatesh Raman, and Saket Saurabh. Parameterized Streaming Algorithms for Min-Ones d-SAT. In 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 150, pp. 8:1-8:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:LIPIcs.FSTTCS.2019.8,
  author =	{Agrawal, Akanksha and Biswas, Arindam and Bonnet, \'{E}douard and Brettell, Nick and Curticapean, Radu and Marx, D\'{a}niel and Miltzow, Tillmann and Raman, Venkatesh and Saurabh, Saket},
  title =	{{Parameterized Streaming Algorithms for Min-Ones d-SAT}},
  booktitle =	{39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)},
  pages =	{8:1--8:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-131-3},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{150},
  editor =	{Chattopadhyay, Arkadev and Gastin, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2019.8},
  URN =		{urn:nbn:de:0030-drops-115708},
  doi =		{10.4230/LIPIcs.FSTTCS.2019.8},
  annote =	{Keywords: min, ones, sat, d-sat, parameterized, kernelization, streaming, space, efficient, algorithm, parameter}
}
Document
DOI: 10.4230/LIPIcs.ESA.2018.13
A Framework for In-place Graph Algorithms

Authors: Sankardeep Chakraborty, Anish Mukherjee, Venkatesh Raman, and Srinivasa Rao Satti

Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)

Abstract
Read-only memory (ROM) model is a classical model of computation to study time-space tradeoffs of algorithms. A classical result on the ROM model is that any algorithm to sort n numbers using O(s) words of extra space requires Omega (n^2/s) comparisons for lg n <= s <= n/lg n and the bound has also been recently matched by an algorithm. However, if we relax the model, we do have sorting algorithms (say Heapsort) that can sort using O(n lg n) comparisons using O(lg n) bits of extra space, even keeping a permutation of the given input sequence at anytime during the algorithm. We address similar relaxations for graph algorithms. We show that a simple natural relaxation of ROM model allows us to implement fundamental graph search methods like BFS and DFS more space efficiently than in ROM. By simply allowing elements in the adjacency list of a vertex to be permuted, we show that, on an undirected or directed connected graph G having n vertices and m edges, the vertices of G can be output in a DFS or BFS order using O(lg n) bits of extra space and O(n^3 lg n) time. Thus we obtain similar bounds for reachability and shortest path distance (both for undirected and directed graphs). With a little more (but still polynomial) time, we can also output vertices in the lex-DFS order. As reachability in directed graphs (even in DAGs) and shortest path distance (even in undirected graphs) are NL-complete, and lex-DFS is P-complete, our results show that our model is more powerful than ROM if L != P. En route, we also introduce and develop algorithms for another relaxation of ROM where the adjacency lists of the vertices are circular lists and we can modify only the heads of the lists. Here we first show a linear time DFS implementation using n + O(lg n) bits of extra space. Improving the extra space exponentially to only O(lg n) bits, we also obtain BFS and DFS albeit with a slightly slower running time. Both the models we propose maintain the graph structure throughout the algorithm, only the order of vertices in the adjacency list changes. In sharp contrast, for BFS and DFS, to the best of our knowledge, there are no algorithms in ROM that use even O(n^{1-epsilon}) bits of extra space; in fact, implementing DFS using cn bits for c<1 has been mentioned as an open problem. Furthermore, DFS (BFS, respectively) algorithms using n+o(n) (o(n), respectively) bits of extra use Reingold's [JACM, 2008] or Barnes et al's reachability algorithm [SICOMP, 1998] and hence have high runtime. Our results can be contrasted with the recent result of Buhrman et al. [STOC, 2014] which gives an algorithm for directed st-reachability on catalytic Turing machines using O(lg n) bits with catalytic space O(n^2 lg n) and time O(n^9).
Cite as

Sankardeep Chakraborty, Anish Mukherjee, Venkatesh Raman, and Srinivasa Rao Satti. A Framework for In-place Graph Algorithms. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 13:1-13:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{chakraborty_et_al:LIPIcs.ESA.2018.13,
  author =	{Chakraborty, Sankardeep and Mukherjee, Anish and Raman, Venkatesh and Satti, Srinivasa Rao},
  title =	{{A Framework for In-place Graph Algorithms}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{13:1--13:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Azar, Yossi and Bast, Hannah and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.13},
  URN =		{urn:nbn:de:0030-drops-94760},
  doi =		{10.4230/LIPIcs.ESA.2018.13},
  annote =	{Keywords: DFS, BFS, in-place algorithm, space-efficient graph algorithms, logspace}
}
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}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2016.22
Biconnectivity, Chain Decomposition and st-Numbering Using O(n) Bits

Authors: Sankardeep Chakraborty, Venkatesh Raman, and Srinivasa Rao Satti

Published in: LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016)

Abstract
Recent work by Elmasry et al. (STACS 2015) and Asano et al. (ISAAC 2014) reconsidered classical fundamental graph algorithms focusing on improving the space complexity. Elmasry et al. gave, among others, an implementation of depth first search (DFS) of a graph on n vertices and m edges, taking O(m lg lg n) time using O(n) bits of space improving on the time bound of O(m lg n) due to Asano et al. Subsequently Banerjee et al. (COCOON 2016) gave an O(m + n) time implementation using O(m+n) bits, for DFS and its classical applications (including testing for biconnectivity, and finding cut vertices and cut edges). Recently, Kammer et al. (MFCS 2016) gave an algorithm for testing biconnectivity using O(n + min{m, n lg lg n}) bits in linear time. In this paper, we consider O(n) bits implementations of the classical applications of DFS. These include the problem of finding cut vertices, and biconnected components, chain decomposition and st-numbering. Classical algorithms for them typically use DFS and some Omega(lg n) bits of information at each node. Our O(n)-bit implementations for these problems take O(m lg^c n lg lg n) time for some small constant c (c leq 3). Central to our implementation is a succinct representation of the DFS tree and a space efficient partitioning of the DFS tree into connected subtrees, which maybe of independent interest for space efficient graph algorithms.
Cite as

Sankardeep Chakraborty, Venkatesh Raman, and Srinivasa Rao Satti. Biconnectivity, Chain Decomposition and st-Numbering Using O(n) Bits. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 22:1-22:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{chakraborty_et_al:LIPIcs.ISAAC.2016.22,
  author =	{Chakraborty, Sankardeep and Raman, Venkatesh and Satti, Srinivasa Rao},
  title =	{{Biconnectivity, Chain Decomposition and st-Numbering Using O(n) Bits}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{22:1--22:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Hong, Seok-Hee},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.22},
  URN =		{urn:nbn:de:0030-drops-67927},
  doi =		{10.4230/LIPIcs.ISAAC.2016.22},
  annote =	{Keywords: biconnectivity, st-number, chain decomposition, tree cover, space efficient algorithms, read-only memory}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2016.75
Parameterized Algorithms on Perfect Graphs for Deletion to (r,l)-Graphs

Authors: Sudeshna Kolay, Fahad Panolan, Venkatesh Raman, and Saket Saurabh

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

Abstract
For fixed integers r,l >= 0, a graph G is called an (r,l)-graph if the vertex set V(G) can be partitioned into r independent sets and l cliques. Such a graph is also said to have cochromatic number r+l. The class of (r,l) graphs generalizes r-colourable graphs (when l=0) and hence not surprisingly, determining whether a given graph is an (r,l)-graph is NP-hard even when r >= 3 or l >= 3 in general graphs. When r and ell are part of the input, then the recognition problem is NP-hard even if the input graph is a perfect graph (where the Chromatic Number problem is solvable in polynomial time). It is also known to be fixed-parameter tractable (FPT) on perfect graphs when parameterized by r and l. I.e. there is an f(r+l) n^O(1) algorithm on perfect graphs on n vertices where f is a function of r and l. Observe that such an algorithm is unlikely on general graphs as the problem is NP-hard even for constant r and l. In this paper, we consider the parameterized complexity of the following problem, which we call Vertex Partization. Given a perfect graph G and positive integers r,l,k decide whether there exists a set S subset or equal to V(G) of size at most k such that the deletion of S from G results in an (r,l)-graph. This problem generalizes well studied problems such as Vertex Cover (when r=1 and l=0), Odd Cycle Transversal (when r=2, l=0) and Split Vertex Deletion (when r=1=l). 1. Vertex Partization on perfect graphs is FPT when parameterized by k+r+l. 2. The problem, when parameterized by k+r+l, does not admit any polynomial sized kernel, under standard complexity theoretic assumptions. In other words, in polynomial time, the input graph cannot be compressed to an equivalent instance of size polynomial in k+r+l. In fact, our result holds even when k=0. 3. When r,ell are universal constants, then Vertex Partization on perfect graphs, parameterized by k, has a polynomial sized kernel.
Cite as

Sudeshna Kolay, Fahad Panolan, Venkatesh Raman, and Saket Saurabh. Parameterized Algorithms on Perfect Graphs for Deletion to (r,l)-Graphs. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 75:1-75:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{kolay_et_al:LIPIcs.MFCS.2016.75,
  author =	{Kolay, Sudeshna and Panolan, Fahad and Raman, Venkatesh and Saurabh, Saket},
  title =	{{Parameterized Algorithms on Perfect Graphs for Deletion to (r,l)-Graphs}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{75:1--75:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.75},
  URN =		{urn:nbn:de:0030-drops-64846},
  doi =		{10.4230/LIPIcs.MFCS.2016.75},
  annote =	{Keywords: graph deletion, FPT algorithms, polynomial kernels}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2015.331
Kernels for Structural Parameterizations of Vertex Cover - Case of Small Degree Modulators

Authors: Diptapriyo Majumdar, Venkatesh Raman, and Saket Saurabh

Published in: LIPIcs, Volume 43, 10th International Symposium on Parameterized and Exact Computation (IPEC 2015)

Abstract
Vertex Cover is one of the most well studied problems in the realm of parameterized algorithms and admits a kernel with O(l^2) edges and 2*l vertices. Here, l denotes the size of a vertex cover we are seeking for. A natural question is whether Vertex Cover admits a polynomial kernel (or a parameterized algorithm) with respect to a parameter k, that is, provably smaller than the size of the vertex cover. Jansen and Bodlaender [STACS 2011, TOCS 2013] raised this question and gave a kernel for Vertex Cover of size O(f^3), where f is the size of a feedback vertex set of the input graph. We continue this line of work and study Vertex Cover with respect to a parameter that is always smaller than the solution size and incomparable to the size of the feedback vertex set of the input graph. Our parameter is the number of vertices whose removal results in a graph of maximum degree two. While vertex cover with this parameterization can easily be shown to be fixed-parameter tractable (FPT), we show that it has a polynomial sized kernel. The input to our problem consists of an undirected graph G, S \subseteq V(G) such that |S| = k and G[V(G)\S] has maximum degree at most 2 and a positive integer l. Given (G,S,l), in polynomial time we output an instance (G',S',l') such that |V(G')|<= O(k^5), |E(G')|<= O(k^6) and G has a vertex cover of size at most l if and only if G' has a vertex cover of size at most l'. When G[V(G)\S] has maximum degree at most 1, we improve the known kernel bound from O(k^3) vertices to O(k^2) vertices (and O(k^3) edges). In general, if G[V(G)\S] is simply a collection of cliques of size at most d, then we transform the graph in polynomial time to an equivalent hypergraph with O(k^d) vertices and show that, for d >= 3, a kernel with O(k^{d-epsilon}) vertices is unlikely to exist for any epsilon >0 unless NP is a subset of coNO/poly.
Cite as

Diptapriyo Majumdar, Venkatesh Raman, and Saket Saurabh. Kernels for Structural Parameterizations of Vertex Cover - Case of Small Degree Modulators. In 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 43, pp. 331-342, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{majumdar_et_al:LIPIcs.IPEC.2015.331,
  author =	{Majumdar, Diptapriyo and Raman, Venkatesh and Saurabh, Saket},
  title =	{{Kernels for Structural Parameterizations of Vertex Cover - Case of Small Degree Modulators}},
  booktitle =	{10th International Symposium on Parameterized and Exact Computation (IPEC 2015)},
  pages =	{331--342},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-92-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{43},
  editor =	{Husfeldt, Thore and Kanj, Iyad},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2015.331},
  URN =		{urn:nbn:de:0030-drops-55943},
  doi =		{10.4230/LIPIcs.IPEC.2015.331},
  annote =	{Keywords: Parameterized Complexity, Kernelization, expansion lemma, vertex cover, structural parameterization}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.FSTTCS.2014
LIPIcs, Volume 29, FSTTCS'14, Complete Volume

Authors: Venkatesh Raman and S. P. Suresh

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

Abstract
LIPIcs, Volume 29, FSTTCS'14, Complete Volume
Cite as

34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@Proceedings{raman_et_al:LIPIcs.FSTTCS.2014,
  title =	{{LIPIcs, Volume 29, FSTTCS'14, Complete Volume}},
  booktitle =	{34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)},
  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},
  URN =		{urn:nbn:de:0030-drops-48795},
  doi =		{10.4230/LIPIcs.FSTTCS.2014},
  annote =	{Keywords: Software/Program Verification, Models of Computation, Modes of Computation, Complexity Measures and Classes, Nonnumerical Algorithms and Problems, Specifying and Verifying and Reasoning about Programs, Mathematical Logic, Formal Languages}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.FSTTCS.2014.i
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Venkatesh Raman and S. P. Suresh

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

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 29, pp. i-xiv, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{raman_et_al:LIPIcs.FSTTCS.2014.i,
  author =	{Raman, Venkatesh and Suresh, S. P.},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)},
  pages =	{i--xiv},
  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.i},
  URN =		{urn:nbn:de:0030-drops-48258},
  doi =		{10.4230/LIPIcs.FSTTCS.2014.i},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
DOI: 10.4230/LIPIcs.STACS.2012.338
LP can be a cure for Parameterized Problems

Authors: N.S. Narayanaswamy, Venkatesh Raman, M.S. Ramanujan, and Saket Saurabh

Published in: LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)

Abstract
We investigate the parameterized complexity of Vertex Cover parameterized above the optimum value of the linear programming (LP) relaxation of the integer linear programming formulation of the problem. By carefully analyzing the change in the LP value in the branching steps, we argue that even the most straightforward branching algorithm (after some preprocessing) results in an O^*(2.6181^r) algorithm for the problem where r is the excess of the vertex cover size over the LP optimum. We write O^*(f(k)) for a time complexity of the form O(f(k)n^{O(1)}), where f(k) grows exponentially with k. Then, using known and new reductions, we give O^*(2.6181^k) algorithms for the parameterized versions of Above Guarantee Vertex Cover, Odd Cycle Transversal, Split Vertex Deletion and Almost 2-SAT, and an O^*(1.6181^k) algorithm for Konig Vertex Deletion, Vertex Cover Param by OCT and Vertex Cover Param by KVD. These algorithms significantly improve the best known bounds for these problems. The notable improvement is the bound for Odd Cycle Transversal for which this is the first major improvement after the first algorithm that showed it fixed-parameter tractable in 2003. We also observe that using our algorithm, one can obtain a simple kernel for the classical vertex cover problem with at most 2k-O(log k) vertices.
Cite as

N.S. Narayanaswamy, Venkatesh Raman, M.S. Ramanujan, and Saket Saurabh. LP can be a cure for Parameterized Problems. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 338-349, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{narayanaswamy_et_al:LIPIcs.STACS.2012.338,
  author =	{Narayanaswamy, N.S. and Raman, Venkatesh and Ramanujan, M.S. and Saurabh, Saket},
  title =	{{LP can be a cure for Parameterized Problems}},
  booktitle =	{29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
  pages =	{338--349},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-35-4},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{14},
  editor =	{D\"{u}rr, Christoph and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.338},
  URN =		{urn:nbn:de:0030-drops-34291},
  doi =		{10.4230/LIPIcs.STACS.2012.338},
  annote =	{Keywords: Algorithms and data structures. Graph Algorithms, Parameterized Algorithms.}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2010.96
The effect of girth on the kernelization complexity of Connected Dominating Set

Authors: Neeldhara Misra, Geevarghese Philip, Venkatesh Raman, and Saket Saurabh

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

Abstract
In the Connected Dominating Set problem we are given as input a graph $G$ and a positive integer $k$, and are asked if there is a set $S$ of at most $k$ vertices of $G$ such that $S$ is a dominating set of $G$ and the subgraph induced by $S$ is connected. This is a basic connectivity problem that is known to be NP-complete, and it has been extensively studied using several algorithmic approaches. In this paper we study the effect of excluding short cycles, as a subgraph, on the kernelization complexity of Connected Dominating Set. Kernelization algorithms are polynomial-time algorithms that take an input and a positive integer $k$ (the parameter) and output an equivalent instance where the size of the new instance and the new parameter are both bounded by some function $g(k)$. The new instance is called a $g(k)$ kernel for the problem. If $g(k)$ is a polynomial in $k$ then we say that the problem admits polynomial kernels. The girth of a graph $G$ is the length of a shortest cycle in $G$. It turns out that Connected Dominating Set is ``hard'' on graphs with small cycles, and becomes progressively easier as the girth increases. More specifically, we obtain the following interesting trichotomy: Connected Dominating Set (a) does not have a kernel of any size on graphs of girth $3$ or $4$ (since the problem is W[2]-hard); (b) admits a $g(k)$ kernel, where $g(k)$ is $k^{O(k)}$, on graphs of girth $5$ or $6$ but has no polynomial kernel (unless the Polynomial Hierarchy (PH) collapses to the third level) on these graphs; (c) has a cubic ($O(k^3)$) kernel on graphs of girth at least $7$. While there is a large and growing collection of parameterized complexity results available for problems on graph classes characterized by excluded minors, our results add to the very few known in the field for graph classes characterized by excluded subgraphs.
Cite as

Neeldhara Misra, Geevarghese Philip, Venkatesh Raman, and Saket Saurabh. The effect of girth on the kernelization complexity of Connected Dominating Set. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). Leibniz International Proceedings in Informatics (LIPIcs), Volume 8, pp. 96-107, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{misra_et_al:LIPIcs.FSTTCS.2010.96,
  author =	{Misra, Neeldhara and Philip, Geevarghese and Raman, Venkatesh and Saurabh, Saket},
  title =	{{The effect of girth on the kernelization complexity of Connected Dominating Set}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)},
  pages =	{96--107},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-23-1},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{8},
  editor =	{Lodaya, Kamal and Mahajan, Meena},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2010.96},
  URN =		{urn:nbn:de:0030-drops-28567},
  doi =		{10.4230/LIPIcs.FSTTCS.2010.96},
  annote =	{Keywords: Connected Dominating Set, parameterized complexity, kernelization, girth}
}
Document
DOI: 10.4230/LIPIcs.STACS.2010.2459
Beyond Bidimensionality: Parameterized Subexponential Algorithms on Directed Graphs

Authors: Frederic Dorn, Fedor V. Fomin, Daniel Lokshtanov, Venkatesh Raman, and Saket Saurabh

Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)

Abstract
In this paper we make the first step beyond bidimensionality by obtaining subexponential time algorithms for problems on directed graphs. We develop two different methods to achieve subexponential time parameterized algorithms for problems on sparse directed graphs. We exemplify our approaches with two well studied problems. For the first problem, $k$-Leaf Out-Branching, which is to find an oriented spanning tree with at least $k$ leaves, we obtain an algorithm solving the problem in time $2^{\cO(\sqrt{k} \log k)} n+ n^{\cO(1)}$ on directed graphs whose underlying undirected graph excludes some fixed graph $H$ as a minor. For the special case when the input directed graph is planar, the running time can be improved to $2^{\cO(\sqrt{k} )}n + n^{\cO(1)}$. The second example is a generalization of the {\sc Directed Hamiltonian Path} problem, namely $k$-Internal Out-Branching, which is to find an oriented spanning tree with at least $k$ internal vertices. We obtain an algorithm solving the problem in time $2^{\cO(\sqrt{k} \log k)} + n^{\cO(1)}$ on directed graphs whose underlying undirected graph excludes some fixed apex graph $H$ as a minor. Finally, we observe that for any $\ve>0$, the $k$-Directed Path problem is solvable in time $\cO((1+\ve)^k n^{f(\ve)})$, where $f$ is some function of $\ve$. Our methods are based on non-trivial combinations of obstruction theorems for undirected graphs, kernelization, problem specific combinatorial structures and a layering technique similar to the one employed by Baker to obtain PTAS for planar graphs.
Cite as

Frederic Dorn, Fedor V. Fomin, Daniel Lokshtanov, Venkatesh Raman, and Saket Saurabh. Beyond Bidimensionality: Parameterized Subexponential Algorithms on Directed Graphs. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 251-262, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{dorn_et_al:LIPIcs.STACS.2010.2459,
  author =	{Dorn, Frederic and Fomin, Fedor V. and Lokshtanov, Daniel and Raman, Venkatesh and Saurabh, Saket},
  title =	{{Beyond Bidimensionality: Parameterized Subexponential Algorithms on Directed Graphs}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{251--262},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Marion, Jean-Yves and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2459},
  URN =		{urn:nbn:de:0030-drops-24599},
  doi =		{10.4230/LIPIcs.STACS.2010.2459},
  annote =	{Keywords: Parameterized Subexponential Algorithms, Directed Graphs, Out-Branching, Internal Out-Branching}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2009.2318
Subexponential Algorithms for Partial Cover Problems

Authors: Fedor V. Fomin, Daniel Lokshtanov, Venkatesh Raman, and Saket Saurabh

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

Abstract
Partial Cover problems are optimization versions of fundamental and well studied problems like {\sc Vertex Cover} and {\sc Dominating Set}. Here one is interested in covering (or dominating) the maximum number of edges (or vertices) using a given number ($k$) of vertices, rather than covering all edges (or vertices). In general graphs, these problems are hard for parameterized complexity classes when parameterized by $k$. It was recently shown by Amini et. al. [{\em FSTTCS 08}\,] that {\sc Partial Vertex Cover} and {\sc Partial Dominating Set} are fixed parameter tractable on large classes of sparse graphs, namely $H$-minor free graphs, which include planar graphs and graphs of bounded genus. In particular, it was shown that on planar graphs both problems can be solved in time $2^{\cO(k)}n^{\cO(1)}$.
Cite as

Fedor V. Fomin, Daniel Lokshtanov, Venkatesh Raman, and Saket Saurabh. Subexponential Algorithms for Partial Cover Problems. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 4, pp. 193-201, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{fomin_et_al:LIPIcs.FSTTCS.2009.2318,
  author =	{Fomin, Fedor V. and Lokshtanov, Daniel and Raman, Venkatesh and Saurabh, Saket},
  title =	{{Subexponential  Algorithms for Partial Cover Problems}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
  pages =	{193--201},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-13-2},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{4},
  editor =	{Kannan, Ravi and Narayan Kumar, K.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2009.2318},
  URN =		{urn:nbn:de:0030-drops-23186},
  doi =		{10.4230/LIPIcs.FSTTCS.2009.2318},
  annote =	{Keywords: Partial cover problems, parameterized complexity, subexponential time algorithms, irrelevant vertex technique}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact