# Search Results

### Documents authored by Saurabh, Saket

Document
Track A: Algorithms, Complexity and Games
##### Satisfiability to Coverage in Presence of Fairness, Matroid, and Global Constraints

Authors: Tanmay Inamdar, Pallavi Jain, Daniel Lokshtanov, Abhishek Sahu, Saket Saurabh, and Anannya Upasana

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

##### Abstract
In the MaxSAT with Cardinality Constraint problem (CC-MaxSAT), we are given a CNF-formula Φ, and a positive integer k, and the goal is to find an assignment β with at most k variables set to true (also called a weight k-assignment) such that the number of clauses satisfied by β is maximized. Maximum Coverage can be seen as a special case of CC-MaxSat, where the formula Φ is monotone, i.e., does not contain any negative literals. CC-MaxSat and Maximum Coverage are extremely well-studied problems in the approximation algorithms as well as the parameterized complexity literature. Our first conceptual contribution is that CC-MaxSat and Maximum Coverage are equivalent to each other in the context of FPT-Approximation parameterized by k (here, the approximation is in terms of the number of clauses satisfied/elements covered). In particular, we give a randomized reduction from CC-MaxSat to Maximum Coverage running in time 𝒪(1/ε)^{k} ⋅ (m+n)^{𝒪(1)} that preserves the approximation guarantee up to a factor of (1-ε). Furthermore, this reduction also works in the presence of "fairness" constraints on the satisfied clauses, as well as matroid constraints on the set of variables that are assigned true. Here, the "fairness" constraints are modeled by partitioning the clauses of the formula Φ into r different colors, and the goal is to find an assignment that satisfies at least t_j clauses of each color 1 ≤ j ≤ r. Armed with this reduction, we focus on designing FPT-Approximation schemes (FPT-ASes) for Maximum Coverage and its generalizations. Our algorithms are based on a novel combination of a variety of ideas, including a carefully designed probability distribution that exploits sparse coverage functions. These algorithms substantially generalize the results in Jain et al. [SODA 2023] for CC-MaxSat and Maximum Coverage for K_{d,d}-free set systems (i.e., no d sets share d elements), as well as a recent FPT-AS for Matroid Constrained Maximum Coverage by Sellier [ESA 2023] for frequency-d set systems.

##### Cite as

Tanmay Inamdar, Pallavi Jain, Daniel Lokshtanov, Abhishek Sahu, Saket Saurabh, and Anannya Upasana. Satisfiability to Coverage in Presence of Fairness, Matroid, and Global Constraints. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 88:1-88:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

@InProceedings{inamdar_et_al:LIPIcs.ICALP.2024.88,
author =	{Inamdar, Tanmay and Jain, Pallavi and Lokshtanov, Daniel and Sahu, Abhishek and Saurabh, Saket and Upasana, Anannya},
title =	{{Satisfiability to Coverage in Presence of Fairness, Matroid, and Global Constraints}},
booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
pages =	{88:1--88:18},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-322-5},
ISSN =	{1868-8969},
year =	{2024},
volume =	{297},
editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.88},
URN =		{urn:nbn:de:0030-drops-202318},
doi =		{10.4230/LIPIcs.ICALP.2024.88},
annote =	{Keywords: Partial Vertex Cover, Max SAT, FPT Approximation, Matroids}
}
Document
##### A 1.9999-Approximation Algorithm for Vertex Cover on String Graphs

Authors: Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Jie Xue, and Meirav Zehavi

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

##### Abstract
Vertex Cover is a fundamental optimization problem, and is among Karp’s 21 NP-complete problems. The problem aims to compute, for a given graph G, a minimum-size set S of vertices of G such that G - S contains no edge. Vertex Cover admits a simple polynomial-time 2-approximation algorithm, which is the best approximation ratio one can achieve in polynomial time, assuming the Unique Game Conjecture. However, on many restrictive graph classes, it is possible to obtain better-than-2 approximation in polynomial time (or even PTASes) for Vertex Cover. In the club of geometric intersection graphs, examples of such graph classes include unit-disk graphs, disk graphs, pseudo-disk graphs, rectangle graphs, etc. In this paper, we study Vertex Cover on the broadest class of geometric intersection graphs in the plane, known as string graphs, which are intersection graphs of any connected geometric objects in the plane. Our main result is a polynomial-time 1.9999-approximation algorithm for Vertex Cover on string graphs, breaking the natural 2 barrier. Prior to this work, no better-than-2 approximation (in polynomial time) was known even for special cases of string graphs, such as intersection graphs of segments. Our algorithm is simple, robust (in the sense that it does not require the geometric realization of the input string graph to be given), and also works for the weighted version of Vertex Cover. Due to a connection between approximation for Independent Set and approximation for Vertex Cover observed by Har-Peled, our result can be viewed as a first step towards obtaining constant-approximation algorithms for Independent Set on string graphs.

##### Cite as

Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Jie Xue, and Meirav Zehavi. A 1.9999-Approximation Algorithm for Vertex Cover on String Graphs. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 72:1-72:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

@InProceedings{lokshtanov_et_al:LIPIcs.SoCG.2024.72,
author =	{Lokshtanov, Daniel and Panolan, Fahad and Saurabh, Saket and Xue, Jie and Zehavi, Meirav},
title =	{{A 1.9999-Approximation Algorithm for Vertex Cover on String Graphs}},
booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
pages =	{72:1--72:11},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-316-4},
ISSN =	{1868-8969},
year =	{2024},
volume =	{293},
editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.72},
URN =		{urn:nbn:de:0030-drops-200174},
doi =		{10.4230/LIPIcs.SoCG.2024.72},
annote =	{Keywords: vertex cover, geometric intersection graphs, approximation algorithms}
}
Document
##### Eliminating Crossings in Ordered Graphs

Authors: Akanksha Agrawal, Sergio Cabello, Michael Kaufmann, Saket Saurabh, Roohani Sharma, Yushi Uno, and Alexander Wolff

Published in: LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)

##### Abstract
Drawing a graph in the plane with as few crossings as possible is one of the central problems in graph drawing and computational geometry. Another option is to remove the smallest number of vertices or edges such that the remaining graph can be drawn without crossings. We study both problems in a book-embedding setting for ordered graphs, that is, graphs with a fixed vertex order. In this setting, the vertices lie on a straight line, called the spine, in the given order, and each edge must be drawn on one of several pages of a book such that every edge has at most a fixed number of crossings. In book embeddings, there is another way to reduce or avoid crossings; namely by using more pages. The minimum number of pages needed to draw an ordered graph without any crossings is its (fixed-vertex-order) page number. We show that the page number of an ordered graph with n vertices and m edges can be computed in 2^m ⋅ n^𝒪(1) time. An 𝒪(log n)-approximation of this number can be computed efficiently. We can decide in 2^𝒪(d √k log (d+k)) ⋅ n^𝒪(1) time whether it suffices to delete k edges of an ordered graph to obtain a d-planar layout (where every edge crosses at most d other edges) on one page. As an additional parameter, we consider the size h of a hitting set, that is, a set of points on the spine such that every edge, seen as an open interval, contains at least one of the points. For h = 1, we can efficiently compute the minimum number of edges whose deletion yields fixed-vertex-order page number p. For h > 1, we give an XP algorithm with respect to h+p. Finally, we consider spine+t-track drawings, where some but not all vertices lie on the spine. The vertex order on the spine is given; we must map every vertex that does not lie on the spine to one of t tracks, each of which is a straight line on a separate page, parallel to the spine. In this setting, we can minimize in 2ⁿ ⋅ n^𝒪(1) time either the number of crossings or, if we disallow crossings, the number of tracks.

##### Cite as

Akanksha Agrawal, Sergio Cabello, Michael Kaufmann, Saket Saurabh, Roohani Sharma, Yushi Uno, and Alexander Wolff. Eliminating Crossings in Ordered Graphs. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 294, pp. 1:1-1:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

@InProceedings{agrawal_et_al:LIPIcs.SWAT.2024.1,
author =	{Agrawal, Akanksha and Cabello, Sergio and Kaufmann, Michael and Saurabh, Saket and Sharma, Roohani and Uno, Yushi and Wolff, Alexander},
title =	{{Eliminating Crossings in Ordered Graphs}},
booktitle =	{19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)},
pages =	{1:1--1:19},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-318-8},
ISSN =	{1868-8969},
year =	{2024},
volume =	{294},
editor =	{Bodlaender, Hans L.},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.1},
URN =		{urn:nbn:de:0030-drops-200417},
doi =		{10.4230/LIPIcs.SWAT.2024.1},
annote =	{Keywords: Ordered graphs, book embedding, edge deletion, d-planar, hitting set}
}
Document
##### Stability in Graphs with Matroid Constraints

Authors: Fedor V. Fomin, Petr A. Golovach, Tuukka Korhonen, and Saket Saurabh

Published in: LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)

##### Abstract
We study the following INDEPENDENT STABLE SET problem. Let G be an undirected graph and ℳ = (V(G), ℐ) be a matroid whose elements are the vertices of G. For an integer k ≥ 1, the task is to decide whether G contains a set S ⊆ V(G) of size at least k which is independent (stable) in G and independent in ℳ. This problem generalizes several well-studied algorithmic problems, including RAINBOW INDEPENDENT SET, RAIBOW MATCHING, and BIPARTITE MATCHING WITH SEPARATION. We show that - When the matroid ℳ is represented by the independence oracle, then for any computable function f, no algorithm can solve INDEPENDENT STABLE SET using f(k)⋅n^o(k) calls to the oracle. - On the other hand, when the graph G is of degeneracy d, then the problem is solvable in time 𝒪((d+1)^k ⋅ n), and hence is FPT parameterized by d+k. Moreover, when the degeneracy d is a constant (which is not a part of the input), the problem admits a kernel polynomial in k. More precisely, we prove that for every integer d ≥ 0, the problem admits a kernelization algorithm that in time n^𝒪(d) outputs an equivalent framework with a graph on dk^{𝒪(d)} vertices. A lower bound complements this when d is part of the input: INDEPENDENT STABLE SET does not admit a polynomial kernel when parameterized by k+d unless NP ⊆ coNP/poly. This lower bound holds even when ℳ is a partition matroid. - Another set of results concerns the scenario when the graph G is chordal. In this case, our computational lower bound excludes an FPT algorithm when the input matroid is given by its independence oracle. However, we demonstrate that INDEPENDENT STABLE SET can be solved in 2^𝒪(k)⋅‖ℳ‖^𝒪(1) time when ℳ is a linear matroid given by its representation. In the same setting, INDEPENDENT STABLE SET does not have a polynomial kernel when parameterized by k unless NP ⊆ coNP/poly.

##### Cite as

Fedor V. Fomin, Petr A. Golovach, Tuukka Korhonen, and Saket Saurabh. Stability in Graphs with Matroid Constraints. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 294, pp. 22:1-22:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

@InProceedings{fomin_et_al:LIPIcs.SWAT.2024.22,
author =	{Fomin, Fedor V. and Golovach, Petr A. and Korhonen, Tuukka and Saurabh, Saket},
title =	{{Stability in Graphs with Matroid Constraints}},
booktitle =	{19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)},
pages =	{22:1--22:16},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-318-8},
ISSN =	{1868-8969},
year =	{2024},
volume =	{294},
editor =	{Bodlaender, Hans L.},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.22},
URN =		{urn:nbn:de:0030-drops-200629},
doi =		{10.4230/LIPIcs.SWAT.2024.22},
annote =	{Keywords: frameworks, independent stable sets, parameterized complexity, kernelization}
}
Document
##### Exponential-Time Approximation Schemes via Compression

Authors: Tanmay Inamdar, Madhumita Kundu, Pekka Parviainen, M. S. Ramanujan, and Saket Saurabh

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

##### Abstract
In this paper, we give a framework to design exponential-time approximation schemes for basic graph partitioning problems such as k-way cut, Multiway Cut, Steiner k-cut and Multicut, where the goal is to minimize the number of edges going across the parts. Our motivation to focus on approximation schemes for these problems comes from the fact that while it is possible to solve them exactly in 2^nn^{{𝒪}(1)} time (note that this is already faster than brute-forcing over all partitions or edge sets), it is not known whether one can do better. Using our framework, we design the first (1+ε)-approximation algorithms for the above problems that run in time 2^{f(ε)n} (for f(ε) < 1) for all these problems. As part of our framework, we present two compression procedures. The first of these is a "lossless" procedure, which is inspired by the seminal randomized contraction algorithm for Global Min-cut of Karger [SODA '93]. Here, we reduce the graph to an equivalent instance where the total number of edges is linearly bounded in the number of edges in an optimal solution of the original instance. Following this, we show how a careful combination of greedy choices and the best exact algorithm for the respective problems can exploit this structure and lead to our approximation schemes. Our first compression procedure bounds the number of edges linearly in the optimal solution, but this could still leave a dense graph as the solution size could be superlinear in the number of vertices. However, for several problems, it is known that they admit significantly faster algorithms on instances where solution size is linear in the number of vertices, in contrast to general instances. Hence, a natural question arises here. Could one reduce the solution size to linear in the number of vertices, at least in the case where we are willing to settle for a near-optimal solution, so that the aforementioned faster algorithms could be exploited? In the second compression procedure, using cut sparsifiers (this time, inspired by Benczúr and Karger [STOC '96]) we introduce "solution linearization" as a methodology to give an approximation-preserving reduction to the regime where solution size is linear in the number of vertices for certain cut problems. Using this, we obtain the first polynomial-space approximation schemes faster than 2^nn^{{𝒪}(1)} for Minimum bisection and Edge Bipartization. Along the way, we also design the first polynomial-space exact algorithms for these problems that run in time faster than 2^nn^{{𝒪}(1)}, in the regime where solution size is linear in the number of vertices. The use of randomized contraction and cut sparsifiers in the exponential-time setting is novel to the best of our knowledge and forms our conceptual contribution.

##### Cite as

Tanmay Inamdar, Madhumita Kundu, Pekka Parviainen, M. S. Ramanujan, and Saket Saurabh. Exponential-Time Approximation Schemes via Compression. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 64:1-64:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

@InProceedings{inamdar_et_al:LIPIcs.ITCS.2024.64,
author =	{Inamdar, Tanmay and Kundu, Madhumita and Parviainen, Pekka and Ramanujan, M. S. and Saurabh, Saket},
title =	{{Exponential-Time Approximation Schemes via Compression}},
booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
pages =	{64:1--64:22},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-309-6},
ISSN =	{1868-8969},
year =	{2024},
volume =	{287},
editor =	{Guruswami, Venkatesan},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.64},
URN =		{urn:nbn:de:0030-drops-195920},
doi =		{10.4230/LIPIcs.ITCS.2024.64},
annote =	{Keywords: Exponential-Time Algorithms, Approximation Algorithms, Graph Algorithms, Cut Problems}
}
Document
##### Kernelization of Counting Problems

Authors: Daniel Lokshtanov, Pranabendu Misra, Saket Saurabh, and Meirav Zehavi

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

##### Abstract
We introduce a new framework for the analysis of preprocessing routines for parameterized counting problems. Existing frameworks that encapsulate parameterized counting problems permit the usage of exponential (rather than polynomial) time either explicitly or by implicitly reducing the counting problems to enumeration problems. Thus, our framework is the only one in the spirit of classic kernelization (as well as lossy kernelization). Specifically, we define a compression of a counting problem P into a counting problem Q as a pair of polynomial-time procedures: reduce and lift. Given an instance of P, reduce outputs an instance of Q whose size is bounded by a function f of the parameter, and given the number of solutions to the instance of Q, lift outputs the number of solutions to the instance of P. When P = Q, compression is termed kernelization, and when f is polynomial, compression is termed polynomial compression. Our technical (and other conceptual) contributions can be classified into two categories: Upper Bounds. We prove two theorems: (i) The #Vertex Cover problem parameterized by solution size admits a polynomial kernel; (ii) Every problem in the class of #Planar F-Deletion problems parameterized by solution size admits a polynomial compression. Lower Bounds. We introduce two new concepts of cross-compositions: EXACT-cross-composition and SUM-cross-composition. We prove that if a #P-hard counting problem P EXACT-cross-composes into a parameterized counting problem Q, then Q does not admit a polynomial compression unless the polynomial hierarchy collapses. We conjecture that the same statement holds for SUM-cross-compositions. Then, we prove that: (i) #Min (s,t)-Cut parameterized by treewidth does not admit a polynomial compression unless the polynomial hierarchy collapses; (ii) #Min (s,t)-Cut parameterized by minimum cut size, #Odd Cycle Transversal parameterized by solution size, and #Vertex Cover parameterized by solution size minus maximum matching size, do not admit polynomial compressions unless our conjecture is false.

##### Cite as

Daniel Lokshtanov, Pranabendu Misra, Saket Saurabh, and Meirav Zehavi. Kernelization of Counting Problems. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 77:1-77:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

@InProceedings{lokshtanov_et_al:LIPIcs.ITCS.2024.77,
author =	{Lokshtanov, Daniel and Misra, Pranabendu and Saurabh, Saket and Zehavi, Meirav},
title =	{{Kernelization of Counting Problems}},
booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
pages =	{77:1--77:23},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-309-6},
ISSN =	{1868-8969},
year =	{2024},
volume =	{287},
editor =	{Guruswami, Venkatesan},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.77},
URN =		{urn:nbn:de:0030-drops-196059},
doi =		{10.4230/LIPIcs.ITCS.2024.77},
annote =	{Keywords: Kernelization, Counting Problems}
}
Document
##### Difference Determines the Degree: Structural Kernelizations of Component Order Connectivity

Authors: Sriram Bhyravarapu, Satyabrata Jana, Saket Saurabh, and Roohani Sharma

Published in: LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)

##### Abstract
We consider the question of polynomial kernelization of a generalization of the classical Vertex Cover problem parameterized by a parameter that is provably smaller than the solution size. In particular, we focus on the c-Component Order Connectivity problem (c-COC) where given an undirected graph G and a non-negative integer t, the objective is to test whether there exists a set S of size at most t such that every component of G-S contains at most c vertices. Such a set S is called a c-coc set. It is known that c-COC admits a kernel with {O}(ct) vertices. Observe that for c = 1, this corresponds to the Vertex Cover problem. We study the c-Component Order Connectivity problem parameterized by the size of a d-coc set (c-COC/d-COC), where c,d ∈ ℕ with c ≤ d. In particular, the input is an undirected graph G, a positive integer t and a set M of at most k vertices of G, such that the size of each connected component in G - M is at most d. The question is to find a set S of vertices of size at most t, such that the size of each connected component in G - S is at most c. In this paper, we give a kernel for c-COC/d-COC with O(k^{d-c+1}) vertices and O(k^{d-c+2}) edges. Our result exhibits that the difference in d and c, and not their absolute values, determines the exact degree of the polynomial in the kernel size. When c = d = 1, the c-COC/d-COC problem is exactly the Vertex Cover problem parameterized by the solution size, which has a kernel with O(k) vertices and O(k²) edges, and this is asymptotically tight [Dell & Melkebeek, JACM 2014]. We also show that the dependence of d-c in the exponent of the kernel size cannot be avoided under reasonable complexity assumptions.

##### Cite as

Sriram Bhyravarapu, Satyabrata Jana, Saket Saurabh, and Roohani Sharma. Difference Determines the Degree: Structural Kernelizations of Component Order Connectivity. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 5:1-5:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

@InProceedings{bhyravarapu_et_al:LIPIcs.IPEC.2023.5,
author =	{Bhyravarapu, Sriram and Jana, Satyabrata and Saurabh, Saket and Sharma, Roohani},
title =	{{Difference Determines the Degree: Structural Kernelizations of Component Order Connectivity}},
booktitle =	{18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
pages =	{5:1--5:14},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-305-8},
ISSN =	{1868-8969},
year =	{2023},
volume =	{285},
editor =	{Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.5},
URN =		{urn:nbn:de:0030-drops-194241},
doi =		{10.4230/LIPIcs.IPEC.2023.5},
annote =	{Keywords: Kernelization, Component Order Connectivity, Vertex Cover, Structural Parameterizations}
}
Document
##### FPT Approximations for Packing and Covering Problems Parameterized by Elimination Distance and Even Less

Authors: Tanmay Inamdar, Lawqueen Kanesh, Madhumita Kundu, M. S. Ramanujan, and Saket Saurabh

Published in: LIPIcs, Volume 284, 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)

##### Abstract
For numerous graph problems in the realm of parameterized algorithms, using the size of a smallest deletion set (called a modulator) into well-understood graph families as parameterization has led to a long and successful line of research. Recently, however, there has been an extensive study of structural parameters that are potentially much smaller than the modulator size. In particular, recent papers [Jansen et al. STOC 2021; Agrawal et al. SODA 2022] have studied parameterization by the size of the modulator to a graph family ℋ(mod_ℋ(⋅)), elimination distance to ℋ(ed_ℋ(⋅)), and ℋ-treewidth (tw_ℋ(⋅)). These parameters are related by the fact that tw_ℋ lower bounds ed_ℋ, which in turn lower bounds mod_ℋ. While these new parameters have been successfully exploited to design fast exact algorithms their utility (especially that of ed_ℋ and tw_ℋ) in the context of approximation algorithms is mostly unexplored. The conceptual contribution of this paper is to present novel algorithmic meta-theorems that expand the impact of these structural parameters to the area of FPT Approximation, mirroring their utility in the design of exact FPT algorithms. Precisely, we show that if a covering or packing problem is definable in Monadic Second Order Logic and has a property called Finite Integer Index (FII), then the existence of an FPT Approximation Scheme (FPT-AS, i.e., (1±ε)-approximation) parameterized by mod_ℋ(⋅), ed_ℋ(⋅), and tw_ℋ(⋅) is in fact equivalent. As a consequence, we obtain FPT-ASes for a wide range of covering, packing, and domination problems on graphs with respect to these parameters. In the process, we show that several graph problems, that are W[1]-hard parameterized by mod_ℋ, admit FPT-ASes not only when parameterized by mod_ℋ, but even when parameterized by the potentially much smaller parameter tw_ℋ(⋅). In the spirit of [Agrawal et al. SODA 2022], our algorithmic results highlight a broader connection between these parameters in the world of approximation. As concrete exemplifications of our meta-theorems, we obtain FPT-ASes for well-studied graph problems such as Vertex Cover, Feedback Vertex Set, Cycle Packing and Dominating Set, parameterized by tw_ℋ(⋅) (and hence, also by mod_ℋ(⋅) or ed_ℋ(⋅)), where ℋ is any family of minor free graphs.

##### Cite as

Tanmay Inamdar, Lawqueen Kanesh, Madhumita Kundu, M. S. Ramanujan, and Saket Saurabh. FPT Approximations for Packing and Covering Problems Parameterized by Elimination Distance and Even Less. In 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 284, pp. 28:1-28:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

@InProceedings{inamdar_et_al:LIPIcs.FSTTCS.2023.28,
author =	{Inamdar, Tanmay and Kanesh, Lawqueen and Kundu, Madhumita and Ramanujan, M. S. and Saurabh, Saket},
title =	{{FPT Approximations for Packing and Covering Problems Parameterized by Elimination Distance and Even Less}},
booktitle =	{43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)},
pages =	{28:1--28:16},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-304-1},
ISSN =	{1868-8969},
year =	{2023},
volume =	{284},
editor =	{Bouyer, Patricia and Srinivasan, Srikanth},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2023.28},
URN =		{urn:nbn:de:0030-drops-194013},
doi =		{10.4230/LIPIcs.FSTTCS.2023.28},
annote =	{Keywords: FPT-AS, F-Deletion, Packing, Elimination Distance, Elimination Treewidth}
}
Document
##### On the Complexity of the Eigenvalue Deletion Problem

Authors: Neeldhara Misra, Harshil Mittal, Saket Saurabh, and Dhara Thakkar

Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)

##### Abstract
For any fixed positive integer r and a given budget k, the r-Eigenvalue Vertex Deletion (r-EVD) problem asks if a graph G admits a subset S of at most k vertices such that the adjacency matrix of G⧵S has at most r distinct eigenvalues. The edge deletion, edge addition, and edge editing variants are defined analogously. For r = 1, r-EVD is equivalent to the Vertex Cover problem. For r = 2, it turns out that r-EVD amounts to removing a subset S of at most k vertices so that G⧵ S is a cluster graph where all connected components have the same size. We show that r-EVD is NP-complete even on bipartite graphs with maximum degree four for every fixed r > 2, and FPT when parameterized by the solution size and the maximum degree of the graph. We also establish several results for the special case when r = 2. For the vertex deletion variant, we show that 2-EVD is NP-complete even on triangle-free and 3d-regular graphs for any d ≥ 2, and also NP-complete on d-regular graphs for any d ≥ 8. The edge deletion, addition, and editing variants are all NP-complete for r = 2. The edge deletion problem admits a polynomial time algorithm if the input is a cluster graph, while - in contrast - the edge addition variant is hard even when the input is a cluster graph. We show that the edge addition variant has a quadratic kernel. The edge deletion and vertex deletion variants admit a single-exponential FPT algorithm when parameterized by the solution size alone. Our main contribution is to develop the complexity landscape for the problem of modifying a graph with the aim of reducing the number of distinct eigenvalues in the spectrum of its adjacency matrix. It turns out that this captures, apart from Vertex Cover, also a natural variation of the problem of modifying to a cluster graph as a special case, which we believe may be of independent interest.

##### Cite as

Neeldhara Misra, Harshil Mittal, Saket Saurabh, and Dhara Thakkar. On the Complexity of the Eigenvalue Deletion Problem. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 53:1-53:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

@InProceedings{misra_et_al:LIPIcs.ISAAC.2023.53,
author =	{Misra, Neeldhara and Mittal, Harshil and Saurabh, Saket and Thakkar, Dhara},
title =	{{On the Complexity of the Eigenvalue Deletion Problem}},
booktitle =	{34th International Symposium on Algorithms and Computation (ISAAC 2023)},
pages =	{53:1--53:17},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-289-1},
ISSN =	{1868-8969},
year =	{2023},
volume =	{283},
editor =	{Iwata, Satoru and Kakimura, Naonori},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.53},
URN =		{urn:nbn:de:0030-drops-193555},
doi =		{10.4230/LIPIcs.ISAAC.2023.53},
annote =	{Keywords: Graph Modification, Rank Reduction, Eigenvalues}
}
Document
##### A Parameterized Algorithm for Vertex Connectivity Survivable Network Design Problem with Uniform Demands

Authors: Jørgen Bang-Jensen, Kristine Vitting Klinkby, Pranabendu Misra, and Saket Saurabh

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

##### Abstract
In the Vertex Connectivity Survivable Network Design (VC-SNDP) problem, the input is a graph G and a function d: V(G) × V(G) → ℕ that encodes the vertex-connectivity demands between pairs of vertices. The objective is to find the smallest subgraph H of G that satisfies all these demands. It is a well-studied NP-complete problem that generalizes several network design problems. We consider the case of uniform demands, where for every vertex pair (u,v) the connectivity demand d(u,v) is a fixed integer κ. It is an important problem with wide applications. We study this problem in the realm of Parameterized Complexity. In this setting, in addition to G and d we are given an integer 𝓁 as the parameter and the objective is to determine if we can remove at least 𝓁 edges from G without violating any connectivity constraints. This was posed as an open problem by Bang-Jansen et.al. [SODA 2018], who studied the edge-connectivity variant of the problem under the same settings. Using a powerful classification result of Lokshtanov et al. [ICALP 2018], Gutin et al. [JCSS 2019] recently showed that this problem admits a (non-uniform) FPT algorithm where the running time was unspecified. Further they also gave an (uniform) FPT algorithm for the case of κ = 2. In this paper we present a (uniform) FPT algorithm any κ that runs in time 2^{O(κ² 𝓁⁴ log 𝓁)}⋅ |V(G)|^O(1). Our algorithm is built upon new insights on vertex connectivity in graphs. Our main conceptual contribution is a novel graph decomposition called the Wheel decomposition. Informally, it is a partition of the edge set of a graph G, E(G) = X₁ ∪ X₂ … ∪ X_r, with the parts arranged in a cyclic order, such that each vertex v ∈ V(G) either has edges in at most two consecutive parts, or has edges in every part of this partition. The first kind of vertices can be thought of as the rim of the wheel, while the second kind form the hub. Additionally, the vertex cuts induced by these edge-sets in G have highly symmetric properties. Our main technical result, informally speaking, establishes that "nearly edge-minimal’’ κ-vertex connected graphs admit a wheel decomposition - a fact that can be exploited for designing algorithms. We believe that this decomposition is of independent interest and it could be a useful tool in resolving other open problems.

##### Cite as

Jørgen Bang-Jensen, Kristine Vitting Klinkby, Pranabendu Misra, and Saket Saurabh. A Parameterized Algorithm for Vertex Connectivity Survivable Network Design Problem with Uniform Demands. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 13:1-13:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

@InProceedings{bangjensen_et_al:LIPIcs.ESA.2023.13,
author =	{Bang-Jensen, J{\o}rgen and Klinkby, Kristine Vitting and Misra, Pranabendu and Saurabh, Saket},
title =	{{A Parameterized Algorithm for Vertex Connectivity Survivable Network Design Problem with Uniform Demands}},
booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
pages =	{13:1--13:15},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-295-2},
ISSN =	{1868-8969},
year =	{2023},
volume =	{274},
editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.13},
URN =		{urn:nbn:de:0030-drops-186663},
doi =		{10.4230/LIPIcs.ESA.2023.13},
annote =	{Keywords: Parameterized Complexity, Vertex Connectivity, Network Design}
}
Document

Authors: Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, Saket Saurabh, and Meirav Zehavi

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

##### Abstract
We consider the following problem about dispersing points. Given a set of points in the plane, the task is to identify whether by moving a small number of points by small distance, we can obtain an arrangement of points such that no pair of points is "close" to each other. More precisely, for a family of n points, an integer k, and a real number d > 0, we ask whether at most k points could be relocated, each point at distance at most d from its original location, such that the distance between each pair of points is at least a fixed constant, say 1. A number of approximation algorithms for variants of this problem, under different names like distant representatives, disk dispersing, or point spreading, are known in the literature. However, to the best of our knowledge, the parameterized complexity of this problem remains widely unexplored. We make the first step in this direction by providing a kernelization algorithm that, in polynomial time, produces an equivalent instance with 𝒪(d²k³) points. As a byproduct of this result, we also design a non-trivial fixed-parameter tractable (FPT) algorithm for the problem, parameterized by k and d. Finally, we complement the result about polynomial kernelization by showing a lower bound that rules out the existence of a kernel whose size is polynomial in k alone, unless NP ⊆ coNP/poly.

##### Cite as

Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, Saket Saurabh, and Meirav Zehavi. Kernelization for Spreading Points. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 48:1-48:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

@InProceedings{fomin_et_al:LIPIcs.ESA.2023.48,
author =	{Fomin, Fedor V. and Golovach, Petr A. and Inamdar, Tanmay and Saurabh, Saket and Zehavi, Meirav},
title =	{{Kernelization for Spreading Points}},
booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
pages =	{48:1--48:16},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-295-2},
ISSN =	{1868-8969},
year =	{2023},
volume =	{274},
editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.48},
URN =		{urn:nbn:de:0030-drops-187017},
doi =		{10.4230/LIPIcs.ESA.2023.48},
annote =	{Keywords: parameterized algorithms, kernelization, spreading points, distant representatives, unit disk packing}
}
Document
##### Lossy Kernelization for (Implicit) Hitting Set Problems

Authors: Fedor V. Fomin, Tien-Nam Le, Daniel Lokshtanov, Saket Saurabh, Stéphan Thomassé, and Meirav Zehavi

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

##### Abstract
We re-visit the complexity of polynomial time pre-processing (kernelization) for the d-Hitting Set problem. This is one of the most classic problems in Parameterized Complexity by itself, and, furthermore, it encompasses several other of the most well-studied problems in this field, such as Vertex Cover, Feedback Vertex Set in Tournaments (FVST) and Cluster Vertex Deletion (CVD). In fact, d-Hitting Set encompasses any deletion problem to a hereditary property that can be characterized by a finite set of forbidden induced subgraphs. With respect to bit size, the kernelization complexity of d-Hitting Set is essentially settled: there exists a kernel with 𝒪(k^d) bits (𝒪(k^d) sets and 𝒪(k^{d-1}) elements) and this it tight by the result of Dell and van Melkebeek [STOC 2010, JACM 2014]. Still, the question of whether there exists a kernel for d-Hitting Set with fewer elements has remained one of the most major open problems in Kernelization. In this paper, we first show that if we allow the kernelization to be lossy with a qualitatively better loss than the best possible approximation ratio of polynomial time approximation algorithms, then one can obtain kernels where the number of elements is linear for every fixed d. Further, based on this, we present our main result: we show that there exist approximate Turing kernelizations for d-Hitting Set that even beat the established bit-size lower bounds for exact kernelizations - in fact, we use a constant number of oracle calls, each with "near linear" (𝒪(k^{1+ε})) bit size, that is, almost the best one could hope for. Lastly, for two special cases of implicit 3-Hitting set, namely, FVST and CVD, we obtain the "best of both worlds" type of results - (1+ε)-approximate kernelizations with a linear number of vertices. In terms of size, this substantially improves the exact kernels of Fomin et al. [SODA 2018, TALG 2019], with simpler arguments.

##### Cite as

Fedor V. Fomin, Tien-Nam Le, Daniel Lokshtanov, Saket Saurabh, Stéphan Thomassé, and Meirav Zehavi. Lossy Kernelization for (Implicit) Hitting Set Problems. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 49:1-49:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

@InProceedings{fomin_et_al:LIPIcs.ESA.2023.49,
author =	{Fomin, Fedor V. and Le, Tien-Nam and Lokshtanov, Daniel and Saurabh, Saket and Thomass\'{e}, St\'{e}phan and Zehavi, Meirav},
title =	{{Lossy Kernelization for (Implicit) Hitting Set Problems}},
booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
pages =	{49:1--49:14},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-295-2},
ISSN =	{1868-8969},
year =	{2023},
volume =	{274},
editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.49},
URN =		{urn:nbn:de:0030-drops-187020},
doi =		{10.4230/LIPIcs.ESA.2023.49},
annote =	{Keywords: Hitting Set, Lossy Kernelization}
}
Document
##### Parameterized Complexity of Fair Bisection: (FPT-Approximation meets Unbreakability)

Authors: Tanmay Inamdar, Daniel Lokshtanov, Saket Saurabh, and Vaishali Surianarayanan

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

##### Abstract
In the Minimum Bisection problem input is a graph G and the goal is to partition the vertex set into two parts A and B, such that ||A|-|B|| ≤ 1 and the number k of edges between A and B is minimized. The problem is known to be NP-hard, and assuming the Unique Games Conjecture even NP-hard to approximate within a constant factor [Khot and Vishnoi, J.ACM'15]. On the other hand, a 𝒪(log n)-approximation algorithm [Räcke, STOC'08] and a parameterized algorithm [Cygan et al., ACM Transactions on Algorithms'20] running in time k^𝒪(k) n^𝒪(1) is known. The Minimum Bisection problem can be viewed as a clustering problem where edges represent similarity and the task is to partition the vertices into two equally sized clusters while minimizing the number of pairs of similar objects that end up in different clusters. Motivated by a number of egregious examples of unfair bias in AI systems, many fundamental clustering problems have been revisited and re-formulated to incorporate fairness constraints. In this paper we initiate the study of the Minimum Bisection problem with fairness constraints. Here the input is a graph G, positive integers c and k, a function χ:V(G) → {1, …, c} that assigns a color χ(v) to each vertex v in G, and c integers r_1,r_2,⋯,r_c. The goal is to partition the vertex set of G into two almost-equal sized parts A and B with at most k edges between them, such that for each color i ∈ {1, …, c}, A has exactly r_i vertices of color i. Each color class corresponds to a group which we require the partition (A, B) to treat fairly, and the constraints that A has exactly r_i vertices of color i can be used to encode that no group is over- or under-represented in either of the two clusters. We first show that introducing fairness constraints appears to make the Minimum Bisection problem qualitatively harder. Specifically we show that unless FPT=W[1] the problem admits no f(c)n^𝒪(1) time algorithm even when k = 0. On the other hand, our main technical contribution shows that is that this hardness result is simply a consequence of the very strict requirement that each color class i has exactly r_i vertices in A. In particular we give an f(k,c,ε)n^𝒪(1) time algorithm that finds a balanced partition (A, B) with at most k edges between them, such that for each color i ∈ [c], there are at most (1±ε)r_i vertices of color i in A. Our approximation algorithm is best viewed as a proof of concept that the technique introduced by [Lampis, ICALP'18] for obtaining FPT-approximation algorithms for problems of bounded tree-width or clique-width can be efficiently exploited even on graphs of unbounded width. The key insight is that the technique of Lampis is applicable on tree decompositions with unbreakable bags (as introduced in [Cygan et al., SIAM Journal on Computing'14]). An important ingredient of our approximation scheme is a combinatorial result that may be of independent interest, namely that for every k, every graph G admits a tree decomposition with adhesions of size at most 𝒪(k), unbreakable bags, and logarithmic depth.

##### Cite as

Tanmay Inamdar, Daniel Lokshtanov, Saket Saurabh, and Vaishali Surianarayanan. Parameterized Complexity of Fair Bisection: (FPT-Approximation meets Unbreakability). In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 63:1-63:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

@InProceedings{inamdar_et_al:LIPIcs.ESA.2023.63,
author =	{Inamdar, Tanmay and Lokshtanov, Daniel and Saurabh, Saket and Surianarayanan, Vaishali},
title =	{{Parameterized Complexity of Fair Bisection: (FPT-Approximation meets Unbreakability)}},
booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
pages =	{63:1--63:17},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-295-2},
ISSN =	{1868-8969},
year =	{2023},
volume =	{274},
editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.63},
URN =		{urn:nbn:de:0030-drops-187167},
doi =		{10.4230/LIPIcs.ESA.2023.63},
annote =	{Keywords: FPT Approximation, Minimum Bisection, Unbreakable Tree Decomposition, Treewidth}
}
Document
##### Fixed-Parameter Algorithms for Fair Hitting Set Problems

Authors: Tanmay Inamdar, Lawqueen Kanesh, Madhumita Kundu, Nidhi Purohit, and Saket Saurabh

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

##### Abstract
Selection of a group of representatives satisfying certain fairness constraints, is a commonly occurring scenario. Motivated by this, we initiate a systematic algorithmic study of a fair version of Hitting Set. In the classical Hitting Set problem, the input is a universe 𝒰, a family ℱ of subsets of 𝒰, and a non-negative integer k. The goal is to determine whether there exists a subset S ⊆ 𝒰 of size k that hits (i.e., intersects) every set in ℱ. Inspired by several recent works, we formulate a fair version of this problem, as follows. The input additionally contains a family ℬ of subsets of 𝒰, where each subset in ℬ can be thought of as the group of elements of the same type. We want to find a set S ⊆ 𝒰 of size k that (i) hits all sets of ℱ, and (ii) does not contain too many elements of each type. We call this problem Fair Hitting Set, and chart out its tractability boundary from both classical as well as multivariate perspective. Our results use a multitude of techniques from parameterized complexity including classical to advanced tools, such as, methods of representative sets for matroids, FO model checking, and a generalization of best known kernels for Hitting Set.

##### Cite as

Tanmay Inamdar, Lawqueen Kanesh, Madhumita Kundu, Nidhi Purohit, and Saket Saurabh. Fixed-Parameter Algorithms for Fair Hitting Set Problems. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 55:1-55:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

@InProceedings{inamdar_et_al:LIPIcs.MFCS.2023.55,
author =	{Inamdar, Tanmay and Kanesh, Lawqueen and Kundu, Madhumita and Purohit, Nidhi and Saurabh, Saket},
title =	{{Fixed-Parameter Algorithms for Fair Hitting Set Problems}},
booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
pages =	{55:1--55:14},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-292-1},
ISSN =	{1868-8969},
year =	{2023},
volume =	{272},
editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.55},
URN =		{urn:nbn:de:0030-drops-185897},
doi =		{10.4230/LIPIcs.MFCS.2023.55},
annote =	{Keywords: Fairness, Parameterized Algorithms, Hitting Set}
}
Document
##### Parameterized Approximation Scheme for Feedback Vertex Set

Authors: Satyabrata Jana, Daniel Lokshtanov, Soumen Mandal, Ashutosh Rai, and Saket Saurabh

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

##### Abstract
Feedback Vertex Set (FVS) is one of the most studied vertex deletion problems in the field of graph algorithms. In the decision version of the problem, given a graph G and an integer k, the question is whether there exists a set S of at most k vertices in G such that G-S is acyclic. It is one of the first few problems which were shown to be NP-complete, and has been extensively studied from the viewpoint of approximation and parameterized algorithms. The best-known polynomial time approximation algorithm for FVS is a 2-factor approximation, while the best known deterministic and randomized FPT algorithms run in time 𝒪^*(3.460^k) and 𝒪^*(2.7^k) respectively. In this paper, we contribute to the newly established area of parameterized approximation, by studying FVS in this paradigm. In particular, we combine the approaches of parameterized and approximation algorithms for the study of FVS, and achieve an approximation guarantee with a factor better than 2 in randomized FPT running time, that improves over the best known parameterized algorithm for FVS. We give three simple randomized (1+ε) approximation algorithms for FVS, running in times 𝒪^*(2^{εk}⋅ 2.7^{(1-ε)k}), 𝒪^*(({(4/(1+ε))^{(1+ε)}}⋅{(ε/3)^ε})^k), and 𝒪^*(4^{(1-ε)k}) respectively for every ε ∈ (0,1). Combining these three algorithms, we obtain a factor (1+ε) approximation algorithm for FVS, which has better running time than the best-known (randomized) FPT algorithm for every ε ∈ (0, 1). This is the first attempt to look at a parameterized approximation of FVS to the best of our knowledge. Our algorithms are very simple, and they rely on some well-known reduction rules used for arriving at FPT algorithms for FVS.

##### Cite as

Satyabrata Jana, Daniel Lokshtanov, Soumen Mandal, Ashutosh Rai, and Saket Saurabh. Parameterized Approximation Scheme for Feedback Vertex Set. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 56:1-56:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

@InProceedings{jana_et_al:LIPIcs.MFCS.2023.56,
author =	{Jana, Satyabrata and Lokshtanov, Daniel and Mandal, Soumen and Rai, Ashutosh and Saurabh, Saket},
title =	{{Parameterized Approximation Scheme for Feedback Vertex Set}},
booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
pages =	{56:1--56:15},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-292-1},
ISSN =	{1868-8969},
year =	{2023},
volume =	{272},
editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.56},
URN =		{urn:nbn:de:0030-drops-185902},
doi =		{10.4230/LIPIcs.MFCS.2023.56},
annote =	{Keywords: Feedback Vertex Set, Parameterized Approximation}
}
Document
Track A: Algorithms, Complexity and Games
##### Breaking the All Subsets Barrier for Min k-Cut

Authors: Daniel Lokshtanov, Saket Saurabh, and Vaishali Surianarayanan

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

##### Abstract
In the Min k-Cut problem, the input is a graph G and an integer k. The task is to find a partition of the vertex set of G into k parts, while minimizing the number of edges that go between different parts of the partition. The problem is NP-complete, and admits a simple 3ⁿ⋅n^𝒪(1) time dynamic programming algorithm, which can be improved to a 2ⁿ⋅n^𝒪(1) time algorithm using the fast subset convolution framework by Björklund et al. [STOC'07]. In this paper we give an algorithm for Min k-Cut with running time 𝒪((2-ε)ⁿ), for ε > 10^{-50}. This is the first algorithm for Min k-Cut with running time 𝒪(cⁿ) for c < 2.

##### Cite as

Daniel Lokshtanov, Saket Saurabh, and Vaishali Surianarayanan. Breaking the All Subsets Barrier for Min k-Cut. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 90:1-90:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

@InProceedings{lokshtanov_et_al:LIPIcs.ICALP.2023.90,
author =	{Lokshtanov, Daniel and Saurabh, Saket and Surianarayanan, Vaishali},
title =	{{Breaking the All Subsets Barrier for Min k-Cut}},
booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
pages =	{90:1--90:19},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-278-5},
ISSN =	{1868-8969},
year =	{2023},
volume =	{261},
editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.90},
URN =		{urn:nbn:de:0030-drops-181422},
doi =		{10.4230/LIPIcs.ICALP.2023.90},
annote =	{Keywords: Exact algorithms, min k-cut, exponential algorithms, graph algorithms, k-way cut}
}
Document
##### Minimum-Membership Geometric Set Cover, Revisited

Authors: Sayan Bandyapadhyay, William Lochet, Saket Saurabh, and Jie Xue

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

##### Abstract
We revisit a natural variant of the geometric set cover problem, called minimum-membership geometric set cover (MMGSC). In this problem, the input consists of a set S of points and a set ℛ of geometric objects, and the goal is to find a subset ℛ^* ⊆ ℛ to cover all points in S such that the membership of S with respect to ℛ^*, denoted by memb(S,ℛ^*), is minimized, where memb(S,ℛ^*) = max_{p ∈ S} |{R ∈ ℛ^*: p ∈ R}|. We give the first polynomial-time approximation algorithms for MMGSC in ℝ². Specifically, we achieve the following two main results. - We give the first polynomial-time constant-approximation algorithm for MMGSC with unit squares. This answers a question left open since the work of Erlebach and Leeuwen [SODA'08], who gave a constant-approximation algorithm with running time n^{O(opt)} where opt is the optimum of the problem (i.e., the minimum membership). - We give the first polynomial-time approximation scheme (PTAS) for MMGSC with halfplanes. Prior to this work, it was even unknown whether the problem can be approximated with a factor of o(log n) in polynomial time, while it is well-known that the minimum-size set cover problem with halfplanes can be solved in polynomial time. We also consider a problem closely related to MMGSC, called minimum-ply geometric set cover (MPGSC), in which the goal is to find ℛ^* ⊆ ℛ to cover S such that the ply of ℛ^* is minimized, where the ply is defined as the maximum number of objects in ℛ^* which have a nonempty common intersection. Very recently, Durocher et al. gave the first constant-approximation algorithm for MPGSC with unit squares which runs in O(n^{12}) time. We give a significantly simpler constant-approximation algorithm with near-linear running time.

##### Cite as

Sayan Bandyapadhyay, William Lochet, Saket Saurabh, and Jie Xue. Minimum-Membership Geometric Set Cover, Revisited. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 11:1-11:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

@InProceedings{bandyapadhyay_et_al:LIPIcs.SoCG.2023.11,
author =	{Bandyapadhyay, Sayan and Lochet, William and Saurabh, Saket and Xue, Jie},
title =	{{Minimum-Membership Geometric Set Cover, Revisited}},
booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
pages =	{11:1--11:14},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-273-0},
ISSN =	{1868-8969},
year =	{2023},
volume =	{258},
editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.11},
URN =		{urn:nbn:de:0030-drops-178610},
doi =		{10.4230/LIPIcs.SoCG.2023.11},
annote =	{Keywords: geometric set cover, geometric optimization, approximation algorithms}
}
Document
##### FPT Constant-Approximations for Capacitated Clustering to Minimize the Sum of Cluster Radii

Authors: Sayan Bandyapadhyay, William Lochet, and Saket Saurabh

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

##### Abstract
Clustering with capacity constraints is a fundamental problem that attracted significant attention throughout the years. In this paper, we give the first FPT constant-factor approximation algorithm for the problem of clustering points in a general metric into k clusters to minimize the sum of cluster radii, subject to non-uniform hard capacity constraints (Capacitated Sum of Radii ). In particular, we give a (15+ε)-approximation algorithm that runs in 2^𝒪(k²log k) ⋅ n³ time. When capacities are uniform, we obtain the following improved approximation bounds. - A (4 + ε)-approximation with running time 2^𝒪(klog(k/ε)) n³, which significantly improves over the FPT 28-approximation of Inamdar and Varadarajan [ESA 2020]. - A (2 + ε)-approximation with running time 2^𝒪(k/ε² ⋅log(k/ε)) dn³ and a (1+ε)-approxim- ation with running time 2^𝒪(kdlog ((k/ε))) n³ in the Euclidean space. Here d is the dimension. - A (1 + ε)-approximation in the Euclidean space with running time 2^𝒪(k/ε² ⋅log(k/ε)) dn³ if we are allowed to violate the capacities by (1 + ε)-factor. We complement this result by showing that there is no (1 + ε)-approximation algorithm running in time f(k)⋅ n^𝒪(1), if any capacity violation is not allowed.

##### Cite as

Sayan Bandyapadhyay, William Lochet, and Saket Saurabh. FPT Constant-Approximations for Capacitated Clustering to Minimize the Sum of Cluster Radii. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 12:1-12:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

@InProceedings{bandyapadhyay_et_al:LIPIcs.SoCG.2023.12,
author =	{Bandyapadhyay, Sayan and Lochet, William and Saurabh, Saket},
title =	{{FPT Constant-Approximations for Capacitated Clustering to Minimize the Sum of Cluster Radii}},
booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
pages =	{12:1--12:14},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-273-0},
ISSN =	{1868-8969},
year =	{2023},
volume =	{258},
editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.12},
URN =		{urn:nbn:de:0030-drops-178628},
doi =		{10.4230/LIPIcs.SoCG.2023.12},
annote =	{Keywords: Clustering, FPT-approximation}
}
Document
##### A Finite Algorithm for the Realizabilty of a Delaunay Triangulation

Authors: Akanksha Agrawal, Saket Saurabh, and Meirav Zehavi

Published in: LIPIcs, Volume 249, 17th International Symposium on Parameterized and Exact Computation (IPEC 2022)

##### Abstract
The Delaunay graph of a point set P ⊆ ℝ² is the plane graph with the vertex-set P and the edge-set that contains {p,p'} if there exists a disc whose intersection with P is exactly {p,p'}. Accordingly, a triangulated graph G is Delaunay realizable if there exists a triangulation of the Delaunay graph of some P ⊆ ℝ², called a Delaunay triangulation of P, that is isomorphic to G. The objective of Delaunay Realization is to compute a point set P ⊆ ℝ² that realizes a given graph G (if such a P exists). Known algorithms do not solve Delaunay Realization as they are non-constructive. Obtaining a constructive algorithm for Delaunay Realization was mentioned as an open problem by Hiroshima et al. [Hiroshima et al., 2000]. We design an n^𝒪(n)-time constructive algorithm for Delaunay Realization. In fact, our algorithm outputs sets of points with integer coordinates.

##### Cite as

Akanksha Agrawal, Saket Saurabh, and Meirav Zehavi. A Finite Algorithm for the Realizabilty of a Delaunay Triangulation. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 1:1-1:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

@InProceedings{agrawal_et_al:LIPIcs.IPEC.2022.1,
author =	{Agrawal, Akanksha and Saurabh, Saket and Zehavi, Meirav},
title =	{{A Finite Algorithm for the Realizabilty of a Delaunay Triangulation}},
booktitle =	{17th International Symposium on Parameterized and Exact Computation (IPEC 2022)},
pages =	{1:1--1:16},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-260-0},
ISSN =	{1868-8969},
year =	{2022},
volume =	{249},
editor =	{Dell, Holger and Nederlof, Jesper},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2022.1},
URN =		{urn:nbn:de:0030-drops-173573},
doi =		{10.4230/LIPIcs.IPEC.2022.1},
annote =	{Keywords: Delaunay Triangulation, Delaunay Realization, Finite Algorithm, Integer Coordinate Realization}
}
Document
##### Exact Exponential Algorithms for Clustering Problems

Authors: Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, Nidhi Purohit, and Saket Saurabh

Published in: LIPIcs, Volume 249, 17th International Symposium on Parameterized and Exact Computation (IPEC 2022)

##### Abstract
In this paper we initiate a systematic study of exact algorithms for some of the well known clustering problems, namely k-MEDIAN and k-MEANS. In k-MEDIAN, the input consists of a set X of n points belonging to a metric space, and the task is to select a subset C ⊆ X of k points as centers, such that the sum of the distances of every point to its nearest center is minimized. In k-MEANS, the objective is to minimize the sum of squares of the distances instead. It is easy to design an algorithm running in time max_{k ≤ n} {n choose k} n^𝒪(1) = 𝒪^*(2ⁿ) (here, 𝒪^*(⋅) notation hides polynomial factors in n). In this paper we design first non-trivial exact algorithms for these problems. In particular, we obtain an 𝒪^*((1.89)ⁿ) time exact algorithm for k-MEDIAN that works for any value of k. Our algorithm is quite general in that it does not use any properties of the underlying (metric) space - it does not even require the distances to satisfy the triangle inequality. In particular, the same algorithm also works for k-Means. We complement this result by showing that the running time of our algorithm is asymptotically optimal, up to the base of the exponent. That is, unless the Exponential Time Hypothesis fails, there is no algorithm for these problems running in time 2^o(n)⋅n^𝒪(1). Finally, we consider the "facility location" or "supplier" versions of these clustering problems, where, in addition to the set X we are additionally given a set of m candidate centers (or facilities) F, and objective is to find a subset of k centers from F. The goal is still to minimize the k-Median/k-Means/k-Center objective. For these versions we give a 𝒪(2ⁿ (mn)^𝒪(1)) time algorithms using subset convolution. We complement this result by showing that, under the Set Cover Conjecture, the "supplier" versions of these problems do not admit an exact algorithm running in time 2^{(1-ε) n} (mn)^𝒪(1).

##### Cite as

Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, Nidhi Purohit, and Saket Saurabh. Exact Exponential Algorithms for Clustering Problems. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 13:1-13:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

@InProceedings{fomin_et_al:LIPIcs.IPEC.2022.13,
author =	{Fomin, Fedor V. and Golovach, Petr A. and Inamdar, Tanmay and Purohit, Nidhi and Saurabh, Saket},
title =	{{Exact Exponential Algorithms for Clustering Problems}},
booktitle =	{17th International Symposium on Parameterized and Exact Computation (IPEC 2022)},
pages =	{13:1--13:14},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-260-0},
ISSN =	{1868-8969},
year =	{2022},
volume =	{249},
editor =	{Dell, Holger and Nederlof, Jesper},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2022.13},
URN =		{urn:nbn:de:0030-drops-173691},
doi =		{10.4230/LIPIcs.IPEC.2022.13},
annote =	{Keywords: clustering, k-median, k-means, exact algorithms}
}
Document
##### Parameterized Complexity of Non-Separating and Non-Disconnecting Paths and Sets

Authors: Ankit Abhinav, Susobhan Bandopadhyay, Aritra Banik, Yasuaki Kobayashi, Shunsuke Nagano, Yota Otachi, and Saket Saurabh

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

##### Abstract
For a connected graph G = (V, E) and s, t ∈ V, a non-separating s-t path is a path P between s and t such that the set of vertices of P does not separate G, that is, G - V(P) is connected. An s-t path P is non-disconnecting if G - E(P) is connected. The problems of finding shortest non-separating and non-disconnecting paths are both known to be NP-hard. In this paper, we consider the problems from the viewpoint of parameterized complexity. We show that the problem of finding a non-separating s-t path of length at most k is W[1]-hard parameterized by k, while the non-disconnecting counterpart is fixed-parameter tractable (FPT) parameterized by k. We also consider the shortest non-separating path problem on several classes of graphs and show that this problem is NP-hard even on bipartite graphs, split graphs, and planar graphs. As for positive results, the shortest non-separating path problem is FPT parameterized by k on planar graphs and on unit disk graphs (where no s, t is given). Further, we give a polynomial-time algorithm on chordal graphs if k is the distance of the shortest path between s and t.

##### Cite as

Ankit Abhinav, Susobhan Bandopadhyay, Aritra Banik, Yasuaki Kobayashi, Shunsuke Nagano, Yota Otachi, and Saket Saurabh. Parameterized Complexity of Non-Separating and Non-Disconnecting Paths and Sets. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 6:1-6:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

@InProceedings{abhinav_et_al:LIPIcs.MFCS.2022.6,
author =	{Abhinav, Ankit and Bandopadhyay, Susobhan and Banik, Aritra and Kobayashi, Yasuaki and Nagano, Shunsuke and Otachi, Yota and Saurabh, Saket},
title =	{{Parameterized Complexity of Non-Separating and Non-Disconnecting Paths and Sets}},
booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages =	{6:1--6:15},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-256-3},
ISSN =	{1868-8969},
year =	{2022},
volume =	{241},
editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.6},
URN =		{urn:nbn:de:0030-drops-168041},
doi =		{10.4230/LIPIcs.MFCS.2022.6},
annote =	{Keywords: Non-separating path, Parameterized complexity}
}
Document
##### An Exact Algorithm for Knot-Free Vertex Deletion

Authors: M. S. Ramanujan, Abhishek Sahu, Saket Saurabh, and Shaily Verma

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

##### Abstract
The study of the Knot-Free Vertex Deletion problem emerges from its application in the resolution of deadlocks called knots, detected in a classical distributed computation model, that is, the OR-model. A strongly connected subgraph Q of a digraph D with at least two vertices is said to be a knot if there is no arc (u,v) of D with u ∈ V(Q) and v ∉ V(Q) (no-out neighbors of the vertices in Q). Given a directed graph D, the Knot-Free Vertex Deletion (KFVD) problem asks to compute a minimum-size subset S ⊂ V(D) such that D[V⧵S] contains no knots. There is no exact algorithm known for the KFVD problem in the literature that is faster than the trivial O^⋆(2ⁿ) brute-force algorithm. In this paper, we obtain the first non-trivial upper bound for KFVD by designing an exact algorithm running in time 𝒪^⋆(1.576ⁿ), where n is the size of the vertex set in D.

##### Cite as

M. S. Ramanujan, Abhishek Sahu, Saket Saurabh, and Shaily Verma. An Exact Algorithm for Knot-Free Vertex Deletion. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 78:1-78:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

@InProceedings{ramanujan_et_al:LIPIcs.MFCS.2022.78,
author =	{Ramanujan, M. S. and Sahu, Abhishek and Saurabh, Saket and Verma, Shaily},
title =	{{An Exact Algorithm for Knot-Free Vertex Deletion}},
booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages =	{78:1--78:15},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-256-3},
ISSN =	{1868-8969},
year =	{2022},
volume =	{241},
editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.78},
URN =		{urn:nbn:de:0030-drops-168769},
doi =		{10.4230/LIPIcs.MFCS.2022.78},
annote =	{Keywords: exact algorithm, knot-free graphs, branching algorithm}
}
Document
##### True Contraction Decomposition and Almost ETH-Tight Bipartization for Unit-Disk Graphs

Authors: Sayan Bandyapadhyay, William Lochet, Daniel Lokshtanov, Saket Saurabh, and Jie Xue

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)

##### Cite as

Daniel Lokshtanov, Amer E. Mouawad, Saket Saurabh, and Meirav Zehavi. Packing Cycles Faster Than Erdos-Posa. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 71:1-71:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

@InProceedings{lokshtanov_et_al:LIPIcs.ICALP.2017.71,
author =	{Lokshtanov, Daniel and Mouawad, Amer E. and Saurabh, Saket and Zehavi, Meirav},
title =	{{Packing Cycles Faster Than Erdos-Posa}},
booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
pages =	{71:1--71:15},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-041-5},
ISSN =	{1868-8969},
year =	{2017},
volume =	{80},
editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.71},
URN =		{urn:nbn:de:0030-drops-73857},
doi =		{10.4230/LIPIcs.ICALP.2017.71},
annote =	{Keywords: Parameterized Complexity, Graph Algorithms, Cycle Packing, Erd\"{o}s-P\'{o}sa Theorem}
}
Document
##### Exact Algorithms for Terrain Guarding

Authors: Pradeesha Ashok, Fedor V. Fomin, Sudeshna Kolay, Saket Saurabh, and Meirav Zehavi

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)

##### Abstract
Given a 1.5-dimensional terrain T, also known as an x-monotone polygonal chain, the Terrain Guarding problem seeks a set of points of minimum size on T that guards all of the points on T. Here, we say that a point p guards a point q if no point of the line segment pq is strictly below T. The Terrain Guarding problem has been extensively studied for over 20 years. In 2005 it was already established that this problem admits a constant-factor approximation algorithm [SODA 2005]. However, only in 2010 King and Krohn [SODA 2010] finally showed that Terrain Guarding is NP-hard. In spite of the remarkable developments in approximation algorithms for Terrain Guarding, next to nothing is known about its parameterized complexity. In particular, the most intriguing open questions in this direction ask whether it admits a subexponential-time algorithm and whether it is fixed-parameter tractable. In this paper, we answer the first question affirmatively by developing an n^O(sqrt{k})-time algorithm for both Discrete Terrain Guarding and Continuous Terrain Guarding. We also make non-trivial progress with respect to the second question: we show that Discrete Orthogonal Terrain Guarding, a well-studied special case of Terrain Guarding, is fixed-parameter tractable.

##### Cite as

Pradeesha Ashok, Fedor V. Fomin, Sudeshna Kolay, Saket Saurabh, and Meirav Zehavi. Exact Algorithms for Terrain Guarding. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 11:1-11:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

@InProceedings{ashok_et_al:LIPIcs.SoCG.2017.11,
author =	{Ashok, Pradeesha and Fomin, Fedor V. and Kolay, Sudeshna and Saurabh, Saket and Zehavi, Meirav},
title =	{{Exact Algorithms for Terrain Guarding}},
booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
pages =	{11:1--11:15},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-038-5},
ISSN =	{1868-8969},
year =	{2017},
volume =	{77},
editor =	{Aronov, Boris and Katz, Matthew J.},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.11},
URN =		{urn:nbn:de:0030-drops-71975},
doi =		{10.4230/LIPIcs.SoCG.2017.11},
annote =	{Keywords: Terrain Guarding, Art Gallery, Exponential-Time Algorithms}
}
Document
##### Split Contraction: The Untold Story

Authors: Akanksha Agrawal, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi

Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)

##### Abstract
The edit operation that contracts edges, which is a fundamental operation in the theory of graph minors, has recently gained substantial scientific attention from the viewpoint of Parameterized Complexity. In this paper, we examine an important family of graphs, namely the family of split graphs, which in the context of edge contractions, is proven to be significantly less obedient than one might expect. Formally, given a graph G and an integer k, the Split Contraction problem asks whether there exists a subset X of edges of G such that G/X is a split graph and X has at most k elements. Here, G/X is the graph obtained from G by contracting edges in X. It was previously claimed that the Split Contraction problem is fixed-parameter tractable. However, we show that, despite its deceptive simplicity, it is W[1]-hard. Our main result establishes the following conditional lower bound: under the Exponential Time Hypothesis, the Split Contraction problem cannot be solved in time 2^(o(l^2)) * poly(n) where l is the vertex cover number of the input graph. We also verify that this lower bound is essentially tight. To the best of our knowledge, this is the first tight lower bound of the form 2^(o(l^2)) * poly(n) for problems parameterized by the vertex cover number of the input graph. In particular, our approach to obtain this lower bound borrows the notion of harmonious coloring from Graph Theory, and might be of independent interest.

##### Cite as

Akanksha Agrawal, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. Split Contraction: The Untold Story. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 5:1-5:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

@InProceedings{agrawal_et_al:LIPIcs.STACS.2017.5,
author =	{Agrawal, Akanksha and Lokshtanov, Daniel and Saurabh, Saket and Zehavi, Meirav},
title =	{{Split Contraction: The Untold Story}},
booktitle =	{34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
pages =	{5:1--5:14},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-028-6},
ISSN =	{1868-8969},
year =	{2017},
volume =	{66},
editor =	{Vollmer, Heribert and Vall\'{e}e, Brigitte},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.5},
URN =		{urn:nbn:de:0030-drops-70297},
doi =		{10.4230/LIPIcs.STACS.2017.5},
annote =	{Keywords: Split Graph, Parameterized Complexity, Edge Contraction}
}
Document
##### Matrix Rigidity from the Viewpoint of Parameterized Complexity

Authors: Fedor V. Fomin, Daniel Lokshtanov, S. M. Meesum, Saket Saurabh, and Meirav Zehavi

Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)

##### Abstract
The rigidity of a matrix A for a target rank r over a field F is the minimum Hamming distance between A and a matrix of rank at most r. Rigidity is a classical concept in Computational Complexity Theory: constructions of rigid matrices are known to imply lower bounds of significant importance relating to arithmetic circuits. Yet, from the viewpoint of Parameterized Complexity, the study of central properties of matrices in general, and of the rigidity of a matrix in particular, has been neglected. In this paper, we conduct a comprehensive study of different aspects of the computation of the rigidity of general matrices in the framework of Parameterized Complexity. Naturally, given parameters r and k, the Matrix Rigidity problem asks whether the rigidity of A for the target rank r is at most k. We show that in case F equals the reals or F is any finite field, this problem is fixed-parameter tractable with respect to k+r. To this end, we present a dimension reduction procedure, which may be a valuable primitive in future studies of problems of this nature. We also employ central tools in Real Algebraic Geometry, which are not well known in Parameterized Complexity, as a black box. In particular, we view the output of our dimension reduction procedure as an algebraic variety. Our main results are complemented by a W[1]-hardness result and a subexponential-time parameterized algorithm for a special case of Matrix Rigidity, highlighting the different flavors of this problem.

##### Cite as

Fedor V. Fomin, Daniel Lokshtanov, S. M. Meesum, Saket Saurabh, and Meirav Zehavi. Matrix Rigidity from the Viewpoint of Parameterized Complexity. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 32:1-32:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

@InProceedings{fomin_et_al:LIPIcs.STACS.2017.32,
author =	{Fomin, Fedor V. and Lokshtanov, Daniel and Meesum, S. M. and Saurabh, Saket and Zehavi, Meirav},
title =	{{Matrix Rigidity from the Viewpoint of Parameterized Complexity}},
booktitle =	{34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
pages =	{32:1--32:14},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-028-6},
ISSN =	{1868-8969},
year =	{2017},
volume =	{66},
editor =	{Vollmer, Heribert and Vall\'{e}e, Brigitte},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.32},
URN =		{urn:nbn:de:0030-drops-70019},
doi =		{10.4230/LIPIcs.STACS.2017.32},
annote =	{Keywords: Matrix Rigidity, Parameterized Complexity, Linear Algebra}
}
Document
##### Improved Algorithms and Combinatorial Bounds for Independent Feedback Vertex Set

Authors: Akanksha Agrawal, Sushmita Gupta, Saket Saurabh, and Roohani Sharma

Published in: LIPIcs, Volume 63, 11th International Symposium on Parameterized and Exact Computation (IPEC 2016)

##### Abstract
In this paper we study the "independent" version of the classic Feedback Vertex Set problem in the realm of parameterized algorithms and moderately exponential time algorithms. More precisely, we study the Independent Feedback Vertex Set problem, where we are given an undirected graph G on n vertices and a positive integer k, and the objective is to check if there is an independent feedback vertex set of size at most k. A set S subseteq V(G) is called an independent feedback vertex set (ifvs) if S is an independent set and G\S is a forest. In this paper we design two deterministic exact algorithms for Independent Feedback Vertex Set with running times O*(4.1481^k) and O*(1.5981^n). In fact, the algorithm with O*(1.5981^n) running time finds the smallest sized ifvs, if an ifvs exists. Both the algorithms are based on interesting measures and improve the best known algorithms for the problem in their respective domains. In particular, the algorithm with running time O*(4.1481^k) is an improvement over the previous algorithm that ran in time O*(5^k). On the other hand, the algorithm with running time O*(1.5981^n) is the first moderately exponential time algorithm that improves over the naive algorithm that enumerates all the subsets of V(G). Additionally, we show that the number of minimal ifvses in any graph on n vertices is upper bounded by 1.7485^n.

##### Cite as

Akanksha Agrawal, Sushmita Gupta, Saket Saurabh, and Roohani Sharma. Improved Algorithms and Combinatorial Bounds for Independent Feedback Vertex Set. In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, pp. 2:1-2:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

@InProceedings{agrawal_et_al:LIPIcs.IPEC.2016.2,
author =	{Agrawal, Akanksha and Gupta, Sushmita and Saurabh, Saket and Sharma, Roohani},
title =	{{Improved Algorithms and Combinatorial Bounds for Independent Feedback Vertex Set}},
booktitle =	{11th International Symposium on Parameterized and Exact Computation (IPEC 2016)},
pages =	{2:1--2:14},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-023-1},
ISSN =	{1868-8969},
year =	{2017},
volume =	{63},
editor =	{Guo, Jiong and Hermelin, Danny},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2016.2},
URN =		{urn:nbn:de:0030-drops-69400},
doi =		{10.4230/LIPIcs.IPEC.2016.2},
annote =	{Keywords: independent feedback vertex set, fixed parameter tractable, exact algorithm, enumeration}
}
Document
Complete Volume
##### LIPICs, Volume 65, FSTTCS'16, Complete Volume

Authors: Akash Lal, S. Akshay, Saket Saurabh, and Sandeep Sen

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

##### Abstract
LIPICs, Volume 65, FSTTCS'16, Complete Volume

##### Cite as

36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 65, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

@Proceedings{lal_et_al:LIPIcs.FSTTCS.2016,
title =	{{LIPICs, Volume 65, FSTTCS'16, Complete Volume}},
booktitle =	{36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)},
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},
URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2016},
URN =		{urn:nbn:de:0030-drops-69074},
doi =		{10.4230/LIPIcs.FSTTCS.2016},
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

Authors: Akash Lal, S. Akshay, Saket Saurabh, and Sandeep Sen

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

##### Cite as

36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 65, pp. 0:i-0:xiv, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

@InProceedings{lal_et_al:LIPIcs.FSTTCS.2016.0,
author =	{Lal, Akash and Akshay, S. and Saurabh, Saket and Sen, Sandeep},
booktitle =	{36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)},
pages =	{0:i--0:xiv},
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},
URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2016.0},
URN =		{urn:nbn:de:0030-drops-68412},
doi =		{10.4230/LIPIcs.FSTTCS.2016.0},
}
Document
##### Simultaneous Feedback Edge Set: A Parameterized Perspective

Authors: Akanksha Agrawal, Fahad Panolan, Saket Saurabh, and Meirav Zehavi

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

##### Abstract
In a recent article Agrawal et al. (STACS 2016) studied a simultaneous variant of the classic Feedback Vertex Set problem, called Simultaneous Feedback Vertex Set (Sim-FVS). In this problem the input is an n-vertex graph G, an integer k and a coloring function col : E(G) -> 2^[alpha] , and the objective is to check whether there exists a vertex subset S of cardinality at most k in G such that for all i in [alpha], G_i - S is acyclic. Here, G_i = (V (G), {e in E(G) | i in col(e)}) and [alpha] = {1,...,alpha}. In this paper we consider the edge variant of the problem, namely, Simultaneous Feedback Edge Set (Sim-FES). In this problem, the input is same as the input of Sim-FVS and the objective is to check whether there is an edge subset S of cardinality at most k in G such that for all i in [alpha], G_i - S is acyclic. Unlike the vertex variant of the problem, when alpha = 1, the problem is equivalent to finding a maximal spanning forest and hence it is polynomial time solvable. We show that for alpha = 3 Sim-FES is NP-hard by giving a reduction from Vertex Cover on cubic-graphs. The same reduction shows that the problem does not admit an algorithm of running time O(2^o(k) n^O(1)) unless ETH fails. This hardness result is complimented by an FPT algorithm for Sim-FES running in time O(2^((omega k alpha) + (alpha log k)) n^O(1)), where omega is the exponent in the running time of matrix multiplication. The same algorithm gives a polynomial time algorithm for the case when alpha = 2. We also give a kernel for Sim-FES with (k alpha)^O(alpha) vertices. Finally, we consider the problem Maximum Simultaneous Acyclic Subgraph. Here, the input is a graph G, an integer q and, a coloring function col : E(G) -> 2^[alpha] . The question is whether there is a edge subset F of cardinality at least q in G such that for all i in [alpha], G[F_i] is acyclic. Here, F_i = {e in F | i in col(e)}. We give an FPT algorithm for Maximum Simultaneous Acyclic Subgraph running in time O(2^(omega q alpha) n^O(1) ). All our algorithms are based on parameterized version of the Matroid Parity problem.

##### Cite as

Akanksha Agrawal, Fahad Panolan, Saket Saurabh, and Meirav Zehavi. Simultaneous Feedback Edge Set: A Parameterized Perspective. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 5:1-5:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

@InProceedings{agrawal_et_al:LIPIcs.ISAAC.2016.5,
author =	{Agrawal, Akanksha and Panolan, Fahad and Saurabh, Saket and Zehavi, Meirav},
title =	{{Simultaneous Feedback Edge Set: A Parameterized Perspective}},
booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
pages =	{5:1--5: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},
URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.5},
URN =		{urn:nbn:de:0030-drops-67767},
doi =		{10.4230/LIPIcs.ISAAC.2016.5},
annote =	{Keywords: parameterized complexity, feedback edge set, alpha-matroid parity}
}
Document
##### Kernels for Deletion to Classes of Acyclic Digraphs

Authors: Akanksha Agrawal, Saket Saurabh, Roohani Sharma, and Meirav Zehavi

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

##### Abstract
In the Directed Feedback Vertex Set (DFVS) problem, we are given a digraph D on n vertices and a positive integer k and the objective is to check whether there exists a set of vertices S of size at most k such that F = D - S is a directed acyclic digraph. In a recent paper, Mnich and van Leeuwen [STACS 2016] considered the kernelization complexity of DFVS with an additional restriction on F, namely that F must be an out-forest (Out-Forest Vertex Deletion Set), an out-tree (Out-Tree Vertex Deletion Set), or a (directed) pumpkin (Pumpkin Vertex Deletion Set). Their objective was to shed some light on the kernelization complexity of the DFVS problem, a well known open problem in the area of Parameterized Complexity. In this article, we improve the kernel sizes of Out-Forest Vertex Deletion Set from O(k^3) to O(k^2) and of Pumpkin Vertex Deletion Set from O(k^18) to O(k^3). We also prove that the former kernel size is tight under certain complexity theoretic assumptions.

##### Cite as

Akanksha Agrawal, Saket Saurabh, Roohani Sharma, and Meirav Zehavi. Kernels for Deletion to Classes of Acyclic Digraphs. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 6:1-6:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

@InProceedings{agrawal_et_al:LIPIcs.ISAAC.2016.6,
author =	{Agrawal, Akanksha and Saurabh, Saket and Sharma, Roohani and Zehavi, Meirav},
title =	{{Kernels for Deletion to Classes of Acyclic Digraphs}},
booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
pages =	{6:1--6:12},
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},
URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.6},
URN =		{urn:nbn:de:0030-drops-67777},
doi =		{10.4230/LIPIcs.ISAAC.2016.6},
annote =	{Keywords: out-forest, pumpkin, parameterized complexity, kernelization}
}
Document
##### Kernelization of Cycle Packing with Relaxed Disjointness Constraints

Authors: Akanksha Agrawal, Daniel Lokshtanov, Diptapriyo Majumdar, Amer E. Mouawad, and Saket Saurabh

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

##### Abstract
A key result in the field of kernelization, a subfield of parameterized complexity, states that the classic Disjoint Cycle Packing problem, i.e. finding k vertex disjoint cycles in a given graph G, admits no polynomial kernel unless NP subseteq coNP/poly. However, very little is known about this problem beyond the aforementioned kernelization lower bound (within the parameterized complexity framework). In the hope of clarifying the picture and better understanding the types of "constraints" that separate "kernelizable" from "non-kernelizable" variants of Disjoint Cycle Packing, we investigate two relaxations of the problem. The first variant, which we call Almost Disjoint Cycle Packing, introduces a "global" relaxation parameter t. That is, given a graph G and integers k and t, the goal is to find at least k distinct cycles such that every vertex of G appears in at most t of the cycles. The second variant, Pairwise Disjoint Cycle Packing, introduces a "local" relaxation parameter and we seek at least k distinct cycles such that every two cycles intersect in at most t vertices. While the Pairwise Disjoint Cycle Packing problem admits a polynomial kernel for all t >= 1, the kernelization complexity of Almost Disjoint Cycle Packing reveals an interesting spectrum of upper and lower bounds. In particular, for t = k/c, where c could be a function of k, we obtain a kernel of size O(2^{c^{2}}*k^{7+c}*log^3(k)) whenever c in o(sqrt(k))). Thus the kernel size varies from being sub-exponential when c in o(sqrt(k)), to quasipolynomial when c in o(log^l(k)), l in R_+, and polynomial when c in O(1). We complement these results for Almost Disjoint Cycle Packing by showing that the problem does not admit a polynomial kernel whenever t in O(k^{epsilon}), for any 0 <= epsilon < 1.

##### Cite as

Akanksha Agrawal, Daniel Lokshtanov, Diptapriyo Majumdar, Amer E. Mouawad, and Saket Saurabh. Kernelization of Cycle Packing with Relaxed Disjointness Constraints. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 26:1-26:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

@InProceedings{agrawal_et_al:LIPIcs.ICALP.2016.26,
author =	{Agrawal, Akanksha and Lokshtanov, Daniel and Majumdar, Diptapriyo and Mouawad, Amer E. and Saurabh, Saket},
title =	{{Kernelization of Cycle Packing with Relaxed Disjointness Constraints}},
booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
pages =	{26:1--26:14},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-013-2},
ISSN =	{1868-8969},
year =	{2016},
volume =	{55},
editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.26},
URN =		{urn:nbn:de:0030-drops-63053},
doi =		{10.4230/LIPIcs.ICALP.2016.26},
annote =	{Keywords: parameterized complexity, cycle packing, kernelization, relaxation}
}
Document
##### 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)

@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},
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
##### Lower Bounds for Approximation Schemes for Closest String

Authors: Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh

Published in: LIPIcs, Volume 53, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)

##### Abstract
In the Closest String problem one is given a family S of equal-length strings over some fixed alphabet, and the task is to find a string y that minimizes the maximum Hamming distance between y and a string from S. While polynomial-time approximation schemes (PTASes) for this problem are known for a long time [Li et al.; J. ACM'02], no efficient polynomial-time approximation scheme (EPTAS) has been proposed so far. In this paper, we prove that the existence of an EPTAS for Closest String is in fact unlikely, as it would imply that FPT=W[1], a highly unexpected collapse in the hierarchy of parameterized complexity classes. Our proof also shows that the existence of a PTAS for Closest String with running time f(eps) n^o(1/eps), for any computable function f, would contradict the Exponential Time Hypothesis.

##### Cite as

Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Lower Bounds for Approximation Schemes for Closest String. In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 53, pp. 12:1-12:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

@InProceedings{cygan_et_al:LIPIcs.SWAT.2016.12,
author =	{Cygan, Marek and Lokshtanov, Daniel and Pilipczuk, Marcin and Pilipczuk, Michal and Saurabh, Saket},
title =	{{Lower Bounds for Approximation Schemes for Closest String}},
booktitle =	{15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)},
pages =	{12:1--12:10},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-011-8},
ISSN =	{1868-8969},
year =	{2016},
volume =	{53},
editor =	{Pagh, Rasmus},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2016.12},
URN =		{urn:nbn:de:0030-drops-60232},
doi =		{10.4230/LIPIcs.SWAT.2016.12},
annote =	{Keywords: closest string, PTAS, efficient PTAS}
}
Document
##### Subexponential Algorithms for Rectilinear Steiner Tree and Arborescence Problems

Authors: Fedor Fomin, Sudeshna Kolay, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

##### Abstract
A rectilinear Steiner tree for a set T of points in the plane is a tree which connects T using horizontal and vertical lines. In the Rectilinear Steiner Tree problem, input is a set T of n points in the Euclidean plane (R^2) and the goal is to find an rectilinear Steiner tree for T of smallest possible total length. A rectilinear Steiner arborecence for a set T of points and root r in T is a rectilinear Steiner tree S for T such that the path in S from r to any point t in T is a shortest path. In the Rectilinear Steiner Arborescense problem the input is a set T of n points in R^2, and a root r in T, the task is to find an rectilinear Steiner arborescence for T, rooted at r of smallest possible total length. In this paper, we give the first subexponential time algorithms for both problems. Our algorithms are deterministic and run in 2^{O(sqrt{n}log n)} time.

##### Cite as

Fedor Fomin, Sudeshna Kolay, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh. Subexponential Algorithms for Rectilinear Steiner Tree and Arborescence Problems. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 39:1-39:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

@InProceedings{fomin_et_al:LIPIcs.SoCG.2016.39,
author =	{Fomin, Fedor and Kolay, Sudeshna and Lokshtanov, Daniel and Panolan, Fahad and Saurabh, Saket},
title =	{{Subexponential Algorithms for Rectilinear Steiner Tree and Arborescence Problems}},
booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
pages =	{39:1--39:15},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-009-5},
ISSN =	{1868-8969},
year =	{2016},
volume =	{51},
editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.39},
URN =		{urn:nbn:de:0030-drops-59310},
doi =		{10.4230/LIPIcs.SoCG.2016.39},
annote =	{Keywords: Rectilinear graphs, Steiner arborescence, parameterized algorithms}
}
Document
##### Simultaneous Feedback Vertex Set: A Parameterized Perspective

Authors: Akanksha Agrawal, Daniel Lokshtanov, Amer E. Mouawad, and Saket Saurabh

Published in: LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)

##### Abstract
For a family of graphs F, a graph G, and a positive integer k, the F-DELETION problem asks whether we can delete at most k vertices from G to obtain a graph in F. F-DELETION generalizes many classical graph problems such as Vertex Cover, Feedback Vertex Set, and Odd Cycle Transversal. A graph G = (V, cup_{i=1}^{alpha} E_{i}), where the edge set of G is partitioned into alpha color classes, is called an alpha-edge-colored graph. A natural extension of the F-DELETION problem to edge-colored graphs is the alpha-SIMULTANEOUS F-DELETION problem. In the latter problem, we are given an alpha-edge-colored graph G and the goal is to find a set S of at most k vertices such that each graph G_i\S, where G_i = (V, E_i) and 1 <= i <= alpha, is in F. In this work, we study alpha-SIMULTANEOUS F-DELETION for F being the family of forests. In other words, we focus on the alpha-SIMULTANEOUS FEEDBACK VERTEX SET (alpha-SIMFVS) problem. Algorithmically, we show that, like its classical counterpart, alpha-SIMFVS parameterized by k is fixed-parameter tractable (FPT) and admits a polynomial kernel, for any fixed constant alpha. In particular, we give an algorithm running in 2^{O(alpha * k)} * n^{O(1)} time and a kernel with O(alpha * k^{3(alpha + 1)}) vertices. The running time of our algorithm implies that alpha-SIMFVS is FPT even when alpha in o(log(n)). We complement this positive result by showing that for alpha in O(log(n)), where n is the number of vertices in the input graph, alpha-SIMFVS becomes W[1]-hard. Our positive results answer one of the open problems posed by Cai and Ye (MFCS 2014).

##### Cite as

Akanksha Agrawal, Daniel Lokshtanov, Amer E. Mouawad, and Saket Saurabh. Simultaneous Feedback Vertex Set: A Parameterized Perspective. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 7:1-7:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

@InProceedings{agrawal_et_al:LIPIcs.STACS.2016.7,
author =	{Agrawal, Akanksha and Lokshtanov, Daniel and Mouawad, Amer E. and Saurabh, Saket},
title =	{{Simultaneous Feedback Vertex Set: A Parameterized Perspective}},
booktitle =	{33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)},
pages =	{7:1--7:15},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-001-9},
ISSN =	{1868-8969},
year =	{2016},
volume =	{47},
editor =	{Ollinger, Nicolas and Vollmer, Heribert},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2016.7},
URN =		{urn:nbn:de:0030-drops-57084},
doi =		{10.4230/LIPIcs.STACS.2016.7},
annote =	{Keywords: parameterized complexity ,feedback vertex set, kernel, edge-colored graphs}
}
Document
##### Kernelization and Sparseness: the Case of Dominating Set

Authors: Pål Grønås Drange, Markus Dregi, Fedor V. Fomin, Stephan Kreutzer, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Felix Reidl, Fernando Sánchez Villaamil, Saket Saurabh, Sebastian Siebertz, and Somnath Sikdar

Published in: LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)

##### Abstract
We prove that for every positive integer r and for every graph class G of bounded expansion, the r-DOMINATING SET problem admits a linear kernel on graphs from G. Moreover, in the more general case when G is only assumed to be nowhere dense, we give an almost linear kernel on G for the classic DOMINATING SET problem, i.e., for the case r=1. These results generalize a line of previous research on finding linear kernels for DOMINATING SET and r-DOMINATING SET (Alber et al., JACM 2004, Bodlaender et al., FOCS 2009, Fomin et al., SODA 2010, Fomin et al., SODA 2012, Fomin et al., STACS 2013). However, the approach taken in this work, which is based on the theory of sparse graphs, is radically different and conceptually much simpler than the previous approaches. We complement our findings by showing that for the closely related CONNECTED DOMINATING SET problem, the existence of such kernelization algorithms is unlikely, even though the problem is known to admit a linear kernel on H-topological-minor-free graphs (Fomin et al., STACS 2013). Also, we prove that for any somewhere dense class G, there is some r for which r-DOMINATING SET is W[2]-hard on G. Thus, our results fall short of proving a sharp dichotomy for the parameterized complexity of r-DOMINATING SET on subgraph-monotone graph classes: we conjecture that the border of tractability lies exactly between nowhere dense and somewhere dense graph classes.

##### Cite as

Pål Grønås Drange, Markus Dregi, Fedor V. Fomin, Stephan Kreutzer, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Felix Reidl, Fernando Sánchez Villaamil, Saket Saurabh, Sebastian Siebertz, and Somnath Sikdar. Kernelization and Sparseness: the Case of Dominating Set. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 31:1-31:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

@InProceedings{drange_et_al:LIPIcs.STACS.2016.31,
author =	{Drange, P\r{a}l Gr{\o}n\r{a}s and Dregi, Markus and Fomin, Fedor V. and Kreutzer, Stephan and Lokshtanov, Daniel and Pilipczuk, Marcin and Pilipczuk, Michal and Reidl, Felix and S\'{a}nchez Villaamil, Fernando and Saurabh, Saket and Siebertz, Sebastian and Sikdar, Somnath},
title =	{{Kernelization and Sparseness: the Case of Dominating Set}},
booktitle =	{33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)},
pages =	{31:1--31:14},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-001-9},
ISSN =	{1868-8969},
year =	{2016},
volume =	{47},
editor =	{Ollinger, Nicolas and Vollmer, Heribert},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2016.31},
URN =		{urn:nbn:de:0030-drops-57327},
doi =		{10.4230/LIPIcs.STACS.2016.31},
annote =	{Keywords: kernelization, dominating set, bounded expansion, nowhere dense}
}
Document
##### Editing to Connected f-Degree Graph

Authors: Fedor V. Fomin, Petr Golovach, Fahad Panolan, and Saket Saurabh

Published in: LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)

##### Abstract
In the EDGE EDITING TO CONNECTED f-DEGREE GRAPH problem we are given a graph G, an integer k and a function f assigning integers to vertices of G. The task is to decide whether there is a connected graph F on the same vertex set as G, such that for every vertex v, its degree in F is f(v) and the number of edges inthe symmetric difference of E(G) and E(F), is at most k. We show that EDGE EDITING TO CONNECTED f-DEGREE GRAPH is fixed-parameter tractable (FPT) by providing an algorithm solving the problem on an n-vertex graph in time 2^{O(k)}n^{O(1)}. Our FPT algorithm is based on a non-trivial combination of color-coding and fast computations of representative families over direct sum matroid of l-elongation of co-graphic matroid associated with G and uniform matroid over the set of non-edges of G. We believe that this combination could be useful in designing parameterized algorithms for other edge editing problems.

##### Cite as

Fedor V. Fomin, Petr Golovach, Fahad Panolan, and Saket Saurabh. Editing to Connected f-Degree Graph. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 36:1-36:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

@InProceedings{fomin_et_al:LIPIcs.STACS.2016.36,
author =	{Fomin, Fedor V. and Golovach, Petr and Panolan, Fahad and Saurabh, Saket},
title =	{{Editing to Connected f-Degree Graph}},
booktitle =	{33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)},
pages =	{36:1--36:14},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-001-9},
ISSN =	{1868-8969},
year =	{2016},
volume =	{47},
editor =	{Ollinger, Nicolas and Vollmer, Heribert},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2016.36},
URN =		{urn:nbn:de:0030-drops-57370},
doi =		{10.4230/LIPIcs.STACS.2016.36},
annote =	{Keywords: Connected f-factor, FPT, Representative Family, Color Coding}
}
Document
##### Finding Even Subgraphs Even Faster

Authors: Prachi Goyal, Pranabendu Misra, Fahad Panolan, Geevarghese Philip, and Saket Saurabh

Published in: LIPIcs, Volume 45, 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)

##### Abstract
Problems of the following kind have been the focus of much recent research in the realm of parameterized complexity: Given an input graph (digraph) on n vertices and a positive integer parameter k, find if there exist k edges(arcs) whose deletion results in a graph that satisfies some specified parity constraints. In particular, when the objective is to obtain a connected graph in which all the vertices have even degrees--where the resulting graph is Eulerian,the problem is called Undirected Eulerian Edge Deletion. The corresponding problem in digraphs where the resulting graph should be strongly connected and every vertex should have the same in-degree as its out-degree is called Directed Eulerian Edge Deletion. Cygan et al.[Algorithmica, 2014] showed that these problems are fixed parameter tractable (FPT), and gave algorithms with the running time 2^O(k log k)n^O(1). They also asked, as an open problem, whether there exist FPT algorithms which solve these problems in time 2^O(k)n^O(1). It was also posed as an open problem at the School on Parameterized Algorithms and Complexity 2014, Bedlewo, Poland. In this paper we answer their question in the affirmative: using the technique of computing representative families of co-graphic matroids we design algorithms which solve these problems in time 2^O(k)n^O(1). The crucial insight we bring to these problems is to view the solution as an independent set of a co-graphic matroid. We believe that this view-point/approach will be useful in other problems where one of the constraints that need to be satisfied is that of connectivity.

##### Cite as

Prachi Goyal, Pranabendu Misra, Fahad Panolan, Geevarghese Philip, and Saket Saurabh. Finding Even Subgraphs Even Faster. In 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 45, pp. 434-447, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

@InProceedings{goyal_et_al:LIPIcs.FSTTCS.2015.434,
author =	{Goyal, Prachi and Misra, Pranabendu and Panolan, Fahad and Philip, Geevarghese and Saurabh, Saket},
title =	{{Finding Even Subgraphs Even Faster}},
booktitle =	{35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)},
pages =	{434--447},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-939897-97-2},
ISSN =	{1868-8969},
year =	{2015},
volume =	{45},
editor =	{Harsha, Prahladh and Ramalingam, G.},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2015.434},
URN =		{urn:nbn:de:0030-drops-56336},
doi =		{10.4230/LIPIcs.FSTTCS.2015.434},
annote =	{Keywords: Eulerian Edge Deletion, FPT, Representative Family.}
}
Document
##### Quick but Odd Growth of Cacti

Authors: Sudeshna Kolay, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh

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

##### Abstract
Let F be a family of graphs. Given an input graph G and a positive integer k, testing whether G has a k-sized subset of vertices S, such that G\S belongs to F, is a prototype vertex deletion problem. These type of problems have attracted a lot of attention in recent times in the domain of parameterized complexity. In this paper, we study two such problems; when F is either a family of cactus graphs or a family of odd-cactus graphs. A graph H is called a cactus graph if every pair of cycles in H intersect on at most one vertex. Furthermore, a cactus graph H is called an odd cactus, if every cycle of H is of odd length. Let us denote by C and C_{odd}, families of cactus and odd cactus, respectively. The vertex deletion problems corresponding to C and C_{odd} are called Diamond Hitting Set and Even Cycle Transversal, respectively. In this paper we design randomized algorithms with running time 12^{k}*n^{O(1)} for both these problems. Our algorithms considerably improve the running time for Diamond Hitting Set and Even Cycle Transversal, compared to what is known about them.

##### Cite as

Sudeshna Kolay, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh. Quick but Odd Growth of Cacti. In 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 43, pp. 258-269, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

@InProceedings{kolay_et_al:LIPIcs.IPEC.2015.258,
author =	{Kolay, Sudeshna and Lokshtanov, Daniel and Panolan, Fahad and Saurabh, Saket},
title =	{{Quick but Odd Growth of Cacti}},
booktitle =	{10th International Symposium on Parameterized and Exact Computation (IPEC 2015)},
pages =	{258--269},
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},
URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2015.258},
URN =		{urn:nbn:de:0030-drops-55883},
doi =		{10.4230/LIPIcs.IPEC.2015.258},
annote =	{Keywords: Even Cycle Transversal, Diamond Hitting Set, Randomized Algorithms}
}
Document
##### 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)

@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},
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
##### B-Chromatic Number: Beyond NP-Hardness

Authors: Fahad Panolan, Geevarghese Philip, and Saket Saurabh

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

##### Abstract
The b-chromatic number of a graph G, chi_b(G), is the largest integer k such that G has a k-vertex coloring with the property that each color class has a vertex which is adjacent to at least one vertex in each of the other color classes. In the B-Chromatic Number problem, the objective is to decide whether chi_b(G) >= k. Testing whether chi_b(G)=Delta(G)+1, where Delta(G) is the maximum degree of a graph, itself is NP-complete even for connected bipartite graphs (Kratochvil, Tuza and Voigt, WG 2002). In this paper we study B-Chromatic Number in the realm of parameterized complexity and exact exponential time algorithms. We show that B-Chromatic Number is W[1]-hard when parameterized by k, resolving the open question posed by Havet and Sampaio (Algorithmica 2013). When k=Delta(G)+1, we design an algorithm for B-Chromatic Number running in time 2^{O(k^2 * log(k))}*n^{O(1)}. Finally, we show that B-Chromatic Number for an n-vertex graph can be solved in time O(3^n * n^{4} * log(n)).

##### Cite as

Fahad Panolan, Geevarghese Philip, and Saket Saurabh. B-Chromatic Number: Beyond NP-Hardness. In 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 43, pp. 389-401, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

@InProceedings{panolan_et_al:LIPIcs.IPEC.2015.389,
author =	{Panolan, Fahad and Philip, Geevarghese and Saurabh, Saket},
title =	{{B-Chromatic Number: Beyond NP-Hardness}},
booktitle =	{10th International Symposium on Parameterized and Exact Computation (IPEC 2015)},
pages =	{389--401},
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},
URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2015.389},
URN =		{urn:nbn:de:0030-drops-55997},
doi =		{10.4230/LIPIcs.IPEC.2015.389},
annote =	{Keywords: b-chromatic number, exact algorithm, parameterized complexity}
}
Document
##### 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)

@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},
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
##### Tree Deletion Set Has a Polynomial Kernel (but no OPT^O(1) Approximation)

Authors: Archontia C. Giannopoulou, Daniel Lokshtanov, Saket Saurabh, and Ondrej Suchy

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

##### Abstract
In the Tree Deletion Set problem the input is a graph G together with an integer k. The objective is to determine whether there exists a set S of at most k vertices such that G \ S is a tree. The problem is NP-complete and even NP-hard to approximate within any factor of OPT^c for any constant c. In this paper we give an O(k^5) size kernel for the Tree Deletion Set problem. An appealing feature of our kernelization algorithm is a new reduction rule, based on system of linear equations, that we use to handle the instances on which Tree Deletion Set is hard to approximate.

##### Cite as

Archontia C. Giannopoulou, Daniel Lokshtanov, Saket Saurabh, and Ondrej Suchy. Tree Deletion Set Has a Polynomial Kernel (but no OPT^O(1) Approximation). In 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 29, pp. 85-96, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

@InProceedings{giannopoulou_et_al:LIPIcs.FSTTCS.2014.85,
author =	{Giannopoulou, Archontia C. and Lokshtanov, Daniel and Saurabh, Saket and Suchy, Ondrej},
title =	{{Tree Deletion Set Has a Polynomial Kernel (but no OPT^O(1) Approximation)}},
booktitle =	{34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)},
pages =	{85--96},
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},
URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2014.85},
URN =		{urn:nbn:de:0030-drops-48261},
doi =		{10.4230/LIPIcs.FSTTCS.2014.85},
annote =	{Keywords: Tree Deletion Set, Feedback Vertex Set, Kernelization, Linear Equations}
}
Document
##### Polynomial Kernels for lambda-extendible Properties Parameterized Above the Poljak-Turzik Bound

Authors: Robert Crowston, Mark Jones, Gabriele Muciaccia, Geevarghese Philip, Ashutosh Rai, and Saket Saurabh

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

##### Abstract
Poljak and Turzik (Discrete Mathematics 1986) introduced the notion of lambda-extendible properties of graphs as a generalization of the property of being bipartite. They showed that for any 0<lambda<1 and lambda-extendible property Pi, any connected graph G on n vertices and m edges contains a spanning subgraph H in Pi with at least lambda*m+(1-lambda)(n-1)/2 edges. The property of being bipartite is lambda-extendible for lambda =1/2, and so the Poljak-Turzik bound generalizes the well-known Edwards-Erdos bound for Max Cut. Other examples of lambda-extendible properties include: being an acyclic oriented graph, a balanced signed graph, or a q-colorable graph for some q in N. Mnich et al. (FSTTCS 2012) defined the closely related notion of strong lambda-extendibility. They showed that the problem of finding a subgraph satisfying a given strongly lambda-extendible property Pi is fixed-parameter tractable (FPT) when parameterized above the Poljak-Turzik bound---does there exist a spanning subgraph H of a connected graph G such that H in Pi and H has at least lambda*m+(1-lambda)(n-1)/2+k edges?---subject to the condition that the problem is FPT on a certain simple class of graphs called almost-forests of cliques. This generalized an earlier result of Crowston et al. (ICALP 2012) for Max Cut, to all strongly lambda-extendible properties which satisfy the additional criterion. In this paper we settle the kernelization complexity of nearly all problems parameterized above Poljak-Turzik bounds, in the affirmative. We show that these problems admit quadratic kernels (cubic when lambda=1/2), without using the assumption that the problem is FPT on almost-forests of cliques. Thus our results not only remove the technical condition of being FPT on almost-forests of cliques from previous results, but also unify and extend previously known kernelization results in this direction. Our results add to the select list of generic kernelization results known in the literature.

##### Cite as

Robert Crowston, Mark Jones, Gabriele Muciaccia, Geevarghese Philip, Ashutosh Rai, and Saket Saurabh. Polynomial Kernels for lambda-extendible Properties Parameterized Above the Poljak-Turzik Bound. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 43-54, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

@InProceedings{crowston_et_al:LIPIcs.FSTTCS.2013.43,
author =	{Crowston, Robert and Jones, Mark and Muciaccia, Gabriele and Philip, Geevarghese and Rai, Ashutosh and Saurabh, Saket},
title =	{{Polynomial Kernels for lambda-extendible Properties Parameterized Above the Poljak-Turzik Bound}},
booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
pages =	{43--54},
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},
URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.43},
URN =		{urn:nbn:de:0030-drops-43599},
doi =		{10.4230/LIPIcs.FSTTCS.2013.43},
annote =	{Keywords: Kernelization, Lambda Extension, Above-Guarantee Parameterization, MaxCut}
}
Document
##### 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)

@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},
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}
}
Document
##### Backdoors to q-Horn

Authors: Serge Gaspers, Sebastian Ordyniak, M. S. Ramanujan, Saket Saurabh, and Stefan Szeider

Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)

##### Abstract
The class q-Horn, introduced by Boros, Crama and Hammer in 1990, is one of the largest known classes of propositional CNF formulas for which satisfiability can be decided in polynomial time. This class properly contains the fundamental classes of Horn and Krom formulas as well as the class of renamable (or disguised) Horn formulas. In this paper we extend this class so that its favorable algorithmic properties can be made accessible to formulas that are outside but "close"' to this class. We show that deciding satisfiability is fixed-parameter tractable parameterized by the distance of the given formula from q-Horn. The distance is measured by the smallest number of variables that we need to delete from the formula in order to get a q-Horn formula, i.e., the size of a smallest deletion backdoor set into the class q-Horn. This result generalizes known fixed-parameter tractability results for satisfiability decision with respect to the parameters distance from Horn, Krom, and renamable Horn.

##### Cite as

Serge Gaspers, Sebastian Ordyniak, M. S. Ramanujan, Saket Saurabh, and Stefan Szeider. Backdoors to q-Horn. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 67-79, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

@InProceedings{gaspers_et_al:LIPIcs.STACS.2013.67,
author =	{Gaspers, Serge and Ordyniak, Sebastian and Ramanujan, M. S. and Saurabh, Saket and Szeider, Stefan},
title =	{{Backdoors to q-Horn}},
booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
pages =	{67--79},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-939897-50-7},
ISSN =	{1868-8969},
year =	{2013},
volume =	{20},
editor =	{Portier, Natacha and Wilke, Thomas},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.67},
URN =		{urn:nbn:de:0030-drops-39236},
doi =		{10.4230/LIPIcs.STACS.2013.67},
annote =	{Keywords: Algorithms and data structures, Backdoor sets, Satisfiability, Fixed Parameter Tractability}
}
Document
##### Linear kernels for (connected) dominating set on graphs with excluded topological subgraphs

Authors: Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Dimitrios M. Thilikos

Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)

##### Abstract
We give the first linear kernels for Dominating Set and Connected Dominating Set problems on graphs excluding a fixed graph H as a topological minor.

##### Cite as

Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Dimitrios M. Thilikos. Linear kernels for (connected) dominating set on graphs with excluded topological subgraphs. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 92-103, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

@InProceedings{fomin_et_al:LIPIcs.STACS.2013.92,
author =	{Fomin, Fedor V. and Lokshtanov, Daniel and Saurabh, Saket and Thilikos, Dimitrios M.},
title =	{{Linear kernels for (connected) dominating set on graphs with excluded topological subgraphs}},
booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
pages =	{92--103},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-939897-50-7},
ISSN =	{1868-8969},
year =	{2013},
volume =	{20},
editor =	{Portier, Natacha and Wilke, Thomas},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.92},
URN =		{urn:nbn:de:0030-drops-39255},
doi =		{10.4230/LIPIcs.STACS.2013.92},
annote =	{Keywords: Parameterized complexity, kernelization, algorithmic graph minors, dominating set, connected dominating set}
}
Document
##### Beyond Max-Cut: lambda-Extendible Properties Parameterized Above the Poljak-Turzik Bound

Authors: Matthias Mnich, Geevarghese Philip, Saket Saurabh, and Ondrej Suchy

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

##### Abstract
Poljak and Turzík (Discrete Math. 1986) introduced the notion of lambda-extendible properties of graphs as a generalization of the property of being bipartite. They showed that for any 0 < lambda < 1 and lambda-extendible property Pi, any connected graph G on n vertices and m edges contains a spanning subgraph H in Pi with at least lambda m+ (1-lambda)/2 (n-1) edges. The property of being bipartite is lambda-extendible for lambda=1/2, and thus the Poljak-Turzík bound generalizes the well-known Edwards-Erdos bound for MAXCUT. We define a variant, namely strong lambda-extendibility, to which the Poljak-Turzík bound applies. For a strong lambda-extendible graph property \Pi, we define the parameterized Above Poljak-Turzík problem as follows: Given a connected graph G on n vertices and m edges and an integer parameter k, does there exist a spanning subgraph H of G such that H in Pi and H has at least lambda m+ (1-lambda)/2 (n-1)+k edges? The parameter is k, the surplus over the number of edges guaranteed by the Poljak-Turzík bound. We consider properties Pi for which the Above Poljak-Turzík problem is fixed-parameter tractable (FPT) on graphs which are O(k) vertices away from being a graph in which each block is a clique. We show that for all such properties, Above Poljak-Turzík is FPT for all 0< lambda <1. Our results hold for properties of oriented graphs and graphs with edge labels. Our results generalize the recent result of Crowston et al. (ICALP 2012) on MAXCUT parameterized above the Edwards-Erdos, and yield FPT algorithms for several graph problems parameterized above lower bounds. For instance, we get that the above-guarantee Max q-Colorable Subgraph problem is FPT. Our results also imply that the parameterized above-guarantee Oriented Max Acyclic Digraph problem thus solving an open question of Raman and Saurabh (Theor. Comput. Sci. 2006).

##### Cite as

Matthias Mnich, Geevarghese Philip, Saket Saurabh, and Ondrej Suchy. Beyond Max-Cut: lambda-Extendible Properties Parameterized Above the Poljak-Turzik Bound. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 18, pp. 412-423, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

@InProceedings{mnich_et_al:LIPIcs.FSTTCS.2012.412,
author =	{Mnich, Matthias and Philip, Geevarghese and Saurabh, Saket and Suchy, Ondrej},
title =	{{Beyond Max-Cut:  lambda-Extendible Properties Parameterized Above the Poljak-Turzik Bound}},
booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)},
pages =	{412--423},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-939897-47-7},
ISSN =	{1868-8969},
year =	{2012},
volume =	{18},
editor =	{D'Souza, Deepak and Radhakrishnan, Jaikumar and Telikepalli, Kavitha},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2012.412},
URN =		{urn:nbn:de:0030-drops-38776},
doi =		{10.4230/LIPIcs.FSTTCS.2012.412},
annote =	{Keywords: Algorithms and data structures; fixed-parameter algorithms; bipartite graphs; above-guarantee parameterization}
}
Document
##### Subexponential Parameterized Odd Cycle Transversal on Planar Graphs

Authors: Daniel Lokshtanov, Saket Saurabh, and Magnus Wahlström

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

##### Abstract
In the Odd Cycle Transversal (OCT) problem we are given a graph G on n vertices and an integer k, the objective is to determine whether there exists a vertex set O in G of size at most k such that G - O is bipartite. Reed, Smith and Vetta [Oper. Res. Lett., 2004] gave an algorithm for OCT with running time 3^kn^{O(1)}. Assuming the exponential time hypothesis of Impagliazzo, Paturi and Zane, the running time can not be improved to 2^{o(k)}n^{O(1)}. We show that OCT admits a randomized algorithm running in O(n^{O(1)} + 2^{O(sqrt{k} log k)}n) time when the input graph is planar. As a byproduct we also obtain a linear time algorithm for OCT on planar graphs with running time O(n^O(1) + 2O( sqrt(k) log k) n) time. This improves over an algorithm of Fiorini et al. [Disc. Appl. Math., 2008].

##### Cite as

Daniel Lokshtanov, Saket Saurabh, and Magnus Wahlström. Subexponential Parameterized Odd Cycle Transversal on Planar Graphs. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 18, pp. 424-434, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

@InProceedings{lokshtanov_et_al:LIPIcs.FSTTCS.2012.424,
author =	{Lokshtanov, Daniel and Saurabh, Saket and Wahlstr\"{o}m, Magnus},
title =	{{Subexponential Parameterized Odd Cycle Transversal on Planar Graphs}},
booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)},
pages =	{424--434},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-939897-47-7},
ISSN =	{1868-8969},
year =	{2012},
volume =	{18},
editor =	{D'Souza, Deepak and Radhakrishnan, Jaikumar and Telikepalli, Kavitha},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2012.424},
URN =		{urn:nbn:de:0030-drops-38783},
doi =		{10.4230/LIPIcs.FSTTCS.2012.424},
annote =	{Keywords: Graph Theory, Parameterized Algorithms, Odd Cycle Transversal}
}
Document
##### Data Reduction and Problem Kernels (Dagstuhl Seminar 12241)

Authors: Michael R. Fellows, Jiong Guo, Dániel Marx, and Saket Saurabh

Published in: Dagstuhl Reports, Volume 2, Issue 6 (2012)

##### Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 12241 Data Reduction and Problem Kernels''. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.

##### Cite as

Michael R. Fellows, Jiong Guo, Dániel Marx, and Saket Saurabh. Data Reduction and Problem Kernels (Dagstuhl Seminar 12241). In Dagstuhl Reports, Volume 2, Issue 6, pp. 26-50, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

@Article{fellows_et_al:DagRep.2.6.26,
author =	{Fellows, Michael R. and Guo, Jiong and Marx, D\'{a}niel and Saurabh, Saket},
title =	{{Data Reduction and Problem Kernels (Dagstuhl Seminar 12241)}},
pages =	{26--50},
journal =	{Dagstuhl Reports},
ISSN =	{2192-5283},
year =	{2012},
volume =	{2},
number =	{6},
editor =	{Fellows, Michael R. and Guo, Jiong and Marx, D\'{a}niel and Saurabh, Saket},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.2.6.26},
URN =		{urn:nbn:de:0030-drops-37297},
doi =		{10.4230/DagRep.2.6.26},
annote =	{Keywords: Preprocessing, Fixed-parameter tractability, Parameterized algorithmics}
}
Document
##### 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)

@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},
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
##### Hitting forbidden minors: Approximation and Kernelization

Authors: Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, Geevarghese Philip, and Saket Saurabh

Published in: LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)

##### Abstract
We study a general class of problems called F-Deletion problems. In an F-Deletion problem, we are asked whether a subset of at most k vertices can be deleted from a graph G such that the resulting graph does not contain as a minor any graph from the family F of forbidden minors. We obtain a number of algorithmic results on the F-Deletion problem when F contains a planar graph. We give - a linear vertex kernel on graphs excluding t-claw K_(1,t), the star with t leaves, as an induced subgraph, where t is a fixed integer. - an approximation algorithm achieving an approximation ratio of O(log^(3/2) OPT), where $OPT$ is the size of an optimal solution on general undirected graphs. Finally, we obtain polynomial kernels for the case when F only contains graph theta_c as a minor for a fixed integer c. The graph theta_c consists of two vertices connected by $c$ parallel edges. Even though this may appear to be a very restricted class of problems it already encompasses well-studied problems such as Vertex Cover, Feedback Vertex Set and Diamond Hitting Set. The generic kernelization algorithm is based on a non-trivial application of protrusion techniques, previously used only for problems on topological graph classes.

##### Cite as

Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, Geevarghese Philip, and Saket Saurabh. Hitting forbidden minors: Approximation and Kernelization. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 189-200, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

@InProceedings{fomin_et_al:LIPIcs.STACS.2011.189,
author =	{Fomin, Fedor V. and Lokshtanov, Daniel and Misra, Neeldhara and Philip, Geevarghese and Saurabh, Saket},
title =	{{Hitting forbidden minors: Approximation and Kernelization}},
booktitle =	{28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)},
pages =	{189--200},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-939897-25-5},
ISSN =	{1868-8969},
year =	{2011},
volume =	{9},
editor =	{Schwentick, Thomas and D\"{u}rr, Christoph},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.189},
URN =		{urn:nbn:de:0030-drops-30103},
doi =		{10.4230/LIPIcs.STACS.2011.189},
annote =	{Keywords: kernelization}
}
Document
##### 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)

@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},
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
##### Determining the Winner of a Dodgson Election is Hard

Authors: Michael Fellows, Bart M. P. Jansen, Daniel Lokshtanov, Frances A. Rosamond, and Saket Saurabh

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

##### Abstract
Computing the Dodgson Score of a candidate in an election is a hard computational problem, which has been analyzed using classical and parameterized analysis. In this paper we resolve two open problems regarding the parameterized complexity of DODGSON SCORE. We show that DODGSON SCORE parameterized by the target score value $k$ does not have a polynomial kernel unless the polynomial hierarchy collapses to the third level; this complements a result of Fellows, Rosamond and Slinko who obtain a non-trivial kernel of exponential size for a generalization of this problem. We also prove that DODGSON SCORE parameterized by the number $n$ of votes is hard for $W[1]$.

##### Cite as

Michael Fellows, Bart M. P. Jansen, Daniel Lokshtanov, Frances A. Rosamond, and Saket Saurabh. Determining the Winner of a Dodgson Election is Hard. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). Leibniz International Proceedings in Informatics (LIPIcs), Volume 8, pp. 459-468, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

@InProceedings{fellows_et_al:LIPIcs.FSTTCS.2010.459,
author =	{Fellows, Michael and Jansen, Bart M. P. and Lokshtanov, Daniel and Rosamond, Frances A. and Saurabh, Saket},
title =	{{Determining the Winner of a Dodgson Election is Hard}},
booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)},
pages =	{459--468},
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},
URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2010.459},
URN =		{urn:nbn:de:0030-drops-28866},
doi =		{10.4230/LIPIcs.FSTTCS.2010.459},
annote =	{Keywords: Dodgson Score, Parameterized Complexity, Kernelization Lower Bounds}
}
Document
##### 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)

@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},
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
##### Kernels for Feedback Arc Set In Tournaments

Authors: Stéphane Bessy, Fedor V. Fomin, Serge Gaspers, Christophe Paul, Anthony Perez, Saket Saurabh, and Stéphan Thomassé

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

##### Abstract
A tournament $T = (V,A)$ is a directed graph in which there is exactly one arc between every pair of distinct vertices. Given a digraph on $n$ vertices and an integer parameter $k$, the {\sc Feedback Arc Set} problem asks whether thegiven digraph has a set of $k$ arcs whose removal results in an acyclicdigraph. The {\sc Feedback Arc Set} problem restricted to tournaments is knownas the {\sc $k$-Feedback Arc Set in Tournaments ($k$-FAST)} problem. In thispaper we obtain a linear vertex kernel for \FAST{}. That is, we give apolynomial time algorithm which given an input instance $T$ to \FAST{} obtains an equivalent instance $T'$ on $O(k)$ vertices. In fact, given any fixed $\epsilon > 0$, the kernelized instance has at most $(2 + \epsilon)k$ vertices.Our result improves the previous known bound of $O(k^2)$ on the kernel size for\FAST{}. Our kernelization algorithm solves the problem on a subclass of tournaments in polynomial time and uses a known polynomial time approximation scheme for \FAST.

##### Cite as

Stéphane Bessy, Fedor V. Fomin, Serge Gaspers, Christophe Paul, Anthony Perez, Saket Saurabh, and Stéphan Thomassé. Kernels for Feedback Arc Set In Tournaments. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 4, pp. 37-47, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

@InProceedings{bessy_et_al:LIPIcs.FSTTCS.2009.2305,
author =	{Bessy, St\'{e}phane and Fomin, Fedor V. and Gaspers, Serge and Paul, Christophe and Perez, Anthony and Saurabh, Saket and Thomass\'{e}, St\'{e}phan},
title =	{{Kernels for Feedback Arc Set In Tournaments}},
booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
pages =	{37--47},
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},
URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2009.2305},
URN =		{urn:nbn:de:0030-drops-23055},
doi =		{10.4230/LIPIcs.FSTTCS.2009.2305},
annote =	{Keywords: Parameterized complexity, kernels, tournaments}
}
Document
##### 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)

@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},
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}
}
Document
##### Kernel(s) for Problems with No Kernel: On Out-Trees with Many Leaves

Authors: Henning Fernau, Fedor V. Fomin, Daniel Lokshtanov, Daniel Raible, Saket Saurabh, and Yngve Villanger

Published in: LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)

##### Abstract
The {\sc $k$-Leaf Out-Branching} problem is to find an out-branching, that is a rooted oriented spanning tree, with at least $k$ leaves in a given digraph. The problem has recently received much attention from the viewpoint of parameterized algorithms. Here, we take a kernelization based approach to the {\sc $k$-Leaf-Out-Branching} problem. We give the first polynomial kernel for {\sc Rooted $k$-Leaf-Out-Branching}, a variant of {\sc $k$-Leaf-Out-Branching} where the root of the tree searched for is also a part of the input. Our kernel has cubic size and is obtained using extremal combinatorics. For the {\sc $k$-Leaf-Out-Branching} problem, we show that no polynomial kernel is possible unless the polynomial hierarchy collapses to third level by applying a recent breakthrough result by Bodlaender et al. (ICALP 2008) in a non-trivial fashion. However, our positive results for {\sc Rooted $k$-Leaf-Out-Branching} immediately imply that the seemingly intractable {\sc $k$-Leaf-Out-Branching} problem admits a data reduction to $n$ independent $O(k^3)$ kernels. These two results, tractability and intractability side by side, are the first ones separating {\it many-to-one kernelization} from {\it Turing kernelization}. This answers affirmatively an open problem regarding cheat kernelization'' raised by Mike Fellows and Jiong Guo independently.

##### Cite as

Henning Fernau, Fedor V. Fomin, Daniel Lokshtanov, Daniel Raible, Saket Saurabh, and Yngve Villanger. Kernel(s) for Problems with No Kernel: On Out-Trees with Many Leaves. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 421-432, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

@InProceedings{fernau_et_al:LIPIcs.STACS.2009.1843,
author =	{Fernau, Henning and Fomin, Fedor V. and Lokshtanov, Daniel and Raible, Daniel and Saurabh, Saket and Villanger, Yngve},
title =	{{Kernel(s) for Problems with No Kernel: On Out-Trees with Many Leaves}},
booktitle =	{26th International Symposium on Theoretical Aspects of Computer Science},
pages =	{421--432},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-939897-09-5},
ISSN =	{1868-8969},
year =	{2009},
volume =	{3},
editor =	{Albers, Susanne and Marion, Jean-Yves},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1843},
URN =		{urn:nbn:de:0030-drops-18437},
doi =		{10.4230/LIPIcs.STACS.2009.1843},
annote =	{Keywords: Parameterized algorithms, Kernelization, Out-branching, Max-leaf, Lower bounds}
}
Document
Extended Abstract
##### Implicit Branching and Parameterized Partial Cover Problems (Extended Abstract)

Authors: Omid Amini, Fedor Fomin, and Saket Saurabh

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

##### Abstract
Covering problems are fundamental classical problems in optimization, computer science and complexity theory. Typically an input to these problems is a family of sets over a finite universe and the goal is to cover the elements of the universe with as few sets of the family as possible. The variations of covering problems include well known problems like Set Cover, Vertex Cover, Dominating Set and Facility Location to name a few. Recently there has been a lot of study on partial covering problems, a natural generalization of covering problems. Here, the goal is not to cover all the elements but to cover the specified number of elements with the minimum number of sets.

##### Cite as

Omid Amini, Fedor Fomin, and Saket Saurabh. Implicit Branching and Parameterized Partial Cover Problems (Extended Abstract). In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 2, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

@InProceedings{amini_et_al:LIPIcs.FSTTCS.2008.1736,
author =	{Amini, Omid and Fomin, Fedor and Saurabh, Saket},
title =	{{Implicit Branching and Parameterized Partial Cover Problems}},
booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
pages =	{1--12},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-939897-08-8},
ISSN =	{1868-8969},
year =	{2008},
volume =	{2},
editor =	{Hariharan, Ramesh and Mukund, Madhavan and Vinay, V},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
}`