# Search Results

### Documents authored by Lokshtanov, Daniel

Document
APPROX
##### Bipartizing (Pseudo-)Disk Graphs: Approximation with a Ratio Better than 3

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

Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)

##### Abstract
In a disk graph, every vertex corresponds to a disk in ℝ² and two vertices are connected by an edge whenever the two corresponding disks intersect. Disk graphs form an important class of geometric intersection graphs, which generalizes both planar graphs and unit-disk graphs. We study a fundamental optimization problem in algorithmic graph theory, Bipartization (also known as Odd Cycle Transversal), on the class of disk graphs. The goal of Bipartization is to delete a minimum number of vertices from the input graph such that the resulting graph is bipartite. A folklore (polynomial-time) 3-approximation algorithm for Bipartization on disk graphs follows from the classical framework of Goemans and Williamson [Combinatorica'98] for cycle-hitting problems. For over two decades, this result has remained the best known approximation for the problem (in fact, even for Bipartization on unit-disk graphs). In this paper, we achieve the first improvement upon this result, by giving a (3-α)-approximation algorithm for Bipartization on disk graphs, for some constant α > 0. Our algorithm directly generalizes to the broader class of pseudo-disk graphs. Furthermore, our algorithm is robust in the sense that it does not require a geometric realization of the input graph to be given.

##### Cite as

Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Jie Xue, and Meirav Zehavi. Bipartizing (Pseudo-)Disk Graphs: Approximation with a Ratio Better than 3. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 6:1-6:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

@InProceedings{lokshtanov_et_al:LIPIcs.APPROX/RANDOM.2024.6,
author =	{Lokshtanov, Daniel and Panolan, Fahad and Saurabh, Saket and Xue, Jie and Zehavi, Meirav},
title =	{{Bipartizing (Pseudo-)Disk Graphs: Approximation with a Ratio Better than 3}},
booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)},
pages =	{6:1--6:14},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-348-5},
ISSN =	{1868-8969},
year =	{2024},
volume =	{317},
editor =	{Kumar, Amit and Ron-Zewi, Noga},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.6},
URN =		{urn:nbn:de:0030-drops-209990},
doi =		{10.4230/LIPIcs.APPROX/RANDOM.2024.6},
annote =	{Keywords: bipartization, geometric intersection graphs, approximation algorithms}
}
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
Complete Volume
##### LIPIcs, Volume 289, STACS 2024, Complete Volume

Authors: Olaf Beyersdorff, Mamadou Moustapha Kanté, Orna Kupferman, and Daniel Lokshtanov

Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)

##### Abstract
LIPIcs, Volume 289, STACS 2024, Complete Volume

##### Cite as

41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 1-1048, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

@Proceedings{beyersdorff_et_al:LIPIcs.STACS.2024,
title =	{{LIPIcs, Volume 289, STACS 2024, Complete Volume}},
booktitle =	{41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)},
pages =	{1--1048},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-311-9},
ISSN =	{1868-8969},
year =	{2024},
volume =	{289},
editor =	{Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024},
URN =		{urn:nbn:de:0030-drops-197098},
doi =		{10.4230/LIPIcs.STACS.2024},
annote =	{Keywords: LIPIcs, Volume 289, STACS 2024, Complete Volume}
}
Document
Front Matter

Authors: Olaf Beyersdorff, Mamadou Moustapha Kanté, Orna Kupferman, and Daniel Lokshtanov

Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)

##### Cite as

41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 0:i-0:xx, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

@InProceedings{beyersdorff_et_al:LIPIcs.STACS.2024.0,
author =	{Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel},
booktitle =	{41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)},
pages =	{0:i--0:xx},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-311-9},
ISSN =	{1868-8969},
year =	{2024},
volume =	{289},
editor =	{Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.0},
URN =		{urn:nbn:de:0030-drops-197108},
doi =		{10.4230/LIPIcs.STACS.2024.0},
}
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
##### 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
##### Counting and Sampling Labeled Chordal Graphs in Polynomial Time

Authors: Úrsula Hébert-Johnson, Daniel Lokshtanov, and Eric Vigoda

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

##### Abstract
We present the first polynomial-time algorithm to exactly compute the number of labeled chordal graphs on n vertices. Our algorithm solves a more general problem: given n and ω as input, it computes the number of ω-colorable labeled chordal graphs on n vertices, using O(n⁷) arithmetic operations. A standard sampling-to-counting reduction then yields a polynomial-time exact sampler that generates an ω-colorable labeled chordal graph on n vertices uniformly at random. Our counting algorithm improves upon the previous best result by Wormald (1985), which computes the number of labeled chordal graphs on n vertices in time exponential in n. An implementation of the polynomial-time counting algorithm gives the number of labeled chordal graphs on up to 30 vertices in less than three minutes on a standard desktop computer. Previously, the number of labeled chordal graphs was only known for graphs on up to 15 vertices.

##### Cite as

Úrsula Hébert-Johnson, Daniel Lokshtanov, and Eric Vigoda. Counting and Sampling Labeled Chordal Graphs in Polynomial Time. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 58:1-58:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

@InProceedings{hebertjohnson_et_al:LIPIcs.ESA.2023.58,
author =	{H\'{e}bert-Johnson, \'{U}rsula and Lokshtanov, Daniel and Vigoda, Eric},
title =	{{Counting and Sampling Labeled Chordal Graphs in Polynomial Time}},
booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
pages =	{58:1--58: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.58},
URN =		{urn:nbn:de:0030-drops-187119},
doi =		{10.4230/LIPIcs.ESA.2023.58},
annote =	{Keywords: Counting algorithms, graph sampling, chordal graphs}
}
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
##### 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
Track A: Algorithms, Complexity and Games
##### Backdoor Sets on Nowhere Dense SAT

Authors: Daniel Lokshtanov, Fahad Panolan, and M. S. Ramanujan

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

##### Abstract
For a satisfiable CNF formula ϕ and an integer t, a weak backdoor set to treewidth-t is a set of variables such that there is an assignment to this set that reduces ϕ to a satisfiable formula that has an incidence graph of treewidth at most t. A natural research program in the work on fixed-parameter algorithms (FPT algorithms) for SAT is to delineate the tractability borders for the problem of detecting a small weak backdoor set to treewidth-t formulas. In this line of research, Gaspers and Szeider (ICALP 2012) showed that detecting a weak backdoor set of size at most k to treewidth-1 is W[2]-hard parameterized by k if the input is an arbitrary CNF formula. Fomin, Lokshtanov, Misra, Ramanujan and Saurabh (SODA 2015), showed that if the input is d-CNF, then detecting a weak backdoor set of size at most k to treewidth-t is fixed-parameter tractable (parameterized by k,t,d). These two results indicate that sparsity of the input plays a role in determining the parameterized complexity of detecting weak backdoor sets to treewidth-t. In this work, we take a major step towards characterizing the precise impact of sparsity on the parameterized complexity of this problem by obtaining algorithmic results for detecting small weak backdoor sets to treewidth-t for input formulas whose incidence graphs belong to a nowhere-dense graph class. Nowhere density provides a robust and well-understood notion of sparsity that is at the heart of several advances on model checking and structural graph theory. Moreover, nowhere-dense graph classes contain many well-studied graph classes such as bounded treewidth graphs, graphs that exclude a fixed (topological) minor and graphs of bounded expansion. Our main contribution is an algorithm that, given a formula ϕ whose incidence graph belongs to a fixed nowhere-dense graph class and an integer k, in time f(t,k)|ϕ|^O(1), either finds a satisfying assignment of ϕ, or concludes correctly that ϕ has no weak backdoor set of size at most k to treewidth-t. To obtain this algorithm, we develop a strategy that only relies on the fact that nowhere-dense graph classes are biclique-free. That is, for every nowhere-dense graph class, there is a p such that it is contained in the class of graphs that exclude K_{p,p} as a subgraph. This is a significant feature of our techniques since the class of biclique-free graphs also generalizes the class of graphs of bounded degeneracy, which are incomparable with nowhere-dense graph classes. As a result, our algorithm also generalizes the results of Fomin, Lokshtanov, Misra, Ramanujan and Saurabh (SODA 2015) for the special case of d-CNF formulas as input when d is fixed. This is because the incidence graphs of such formulas exclude K_{d+1,d+1} as a subgraph.

##### Cite as

Daniel Lokshtanov, Fahad Panolan, and M. S. Ramanujan. Backdoor Sets on Nowhere Dense SAT. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 91:1-91:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

@InProceedings{lokshtanov_et_al:LIPIcs.ICALP.2022.91,
author =	{Lokshtanov, Daniel and Panolan, Fahad and Ramanujan, M. S.},
title =	{{Backdoor Sets on Nowhere Dense SAT}},
booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
pages =	{91:1--91:20},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-235-8},
ISSN =	{1868-8969},
year =	{2022},
volume =	{229},
editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.91},
URN =		{urn:nbn:de:0030-drops-164323},
doi =		{10.4230/LIPIcs.ICALP.2022.91},
annote =	{Keywords: Fixed-parameter Tractability, Satisfiability, Backdoors, Treewidth}
}
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
##### 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
##### A 2lk Kernel for l-Component Order Connectivity

Authors: Mithilesh Kumar and Daniel Lokshtanov

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

##### Abstract
In the l-Component Order Connectivity problem (l in N), we are given a graph G on n vertices, m edges and a non-negative integer k and asks whether there exists a set of vertices S subseteq V(G) such that |S| <= k and the size of the largest connected component in G-S is at most l. In this paper, we give a kernel for l-Component Order Connectivity with at most 2*l*k vertices that takes n^{O(l)} time for every constant l. On the way to obtaining our kernel, we prove a generalization of the q-Expansion Lemma to weighted graphs. This generalization may be of independent interest.

##### Cite as

Mithilesh Kumar and Daniel Lokshtanov. A 2lk Kernel for l-Component Order Connectivity. In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, pp. 20:1-20:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

@InProceedings{kumar_et_al:LIPIcs.IPEC.2016.20,
author =	{Kumar, Mithilesh and Lokshtanov, Daniel},
title =	{{A 2lk Kernel for l-Component Order Connectivity}},
booktitle =	{11th International Symposium on Parameterized and Exact Computation (IPEC 2016)},
pages =	{20:1--20: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.20},
URN =		{urn:nbn:de:0030-drops-69345},
doi =		{10.4230/LIPIcs.IPEC.2016.20},
annote =	{Keywords: Parameterized algorithms, Kernel, Component Order Connectivity, Max-min allocation, Weighted expansion}
}
Document
##### Faster Exact and Parameterized Algorithm for Feedback Vertex Set in Bipartite Tournaments

Authors: Mithilesh Kumar and Daniel Lokshtanov

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

##### Abstract
A bipartite tournament is a directed graph T:=(A cup B, E) such that every pair of vertices (a,b), a in A, b in B are connected by an arc, and no arc connects two vertices of A or two vertices of B. A feedback vertex set is a set S of vertices in T such that T - S is acyclic. In this article we consider the Feedback Vertex Set problem in bipartite tournaments. Here the input is a bipartite tournament T on n vertices together with an integer k, and the task is to determine whether T has a feedback vertex set of size at most k. We give a new algorithm for Feedback Vertex Set in Bipartite Tournaments. The running time of our algorithm is upper-bounded by O(1.6181^k + n^{O(1)}), improving over the previously best known algorithm with running time (2^k)k^{O(1)} + n^{O(1)} [Hsiao, ISAAC 2011]. As a by-product, we also obtain the fastest currently known exact exponential-time algorithm for the problem, with running time O(1.3820^n).

##### Cite as

Mithilesh Kumar and Daniel Lokshtanov. Faster Exact and Parameterized Algorithm for Feedback Vertex Set in Bipartite Tournaments. In 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 65, pp. 24:1-24:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

@InProceedings{kumar_et_al:LIPIcs.FSTTCS.2016.24,
author =	{Kumar, Mithilesh and Lokshtanov, Daniel},
title =	{{Faster Exact and Parameterized Algorithm for Feedback Vertex Set in Bipartite Tournaments}},
booktitle =	{36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)},
pages =	{24:1--24:15},
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.24},
URN =		{urn:nbn:de:0030-drops-68591},
doi =		{10.4230/LIPIcs.FSTTCS.2016.24},
annote =	{Keywords: Parameterized algorithms, Exact algorithms, Feedback vertex set, Tour- naments, Bipartite tournaments}
}
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
##### 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
##### Faster Exact and Parameterized Algorithm for Feedback Vertex Set in Tournaments

Authors: Mithilesh Kumar and Daniel Lokshtanov

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

##### Abstract
A tournament is a directed graph T such that every pair of vertices is connected by an arc. A feedback vertex set is a set S of vertices in T such that T\S is acyclic. In this article we consider the FEEDBACK VERTEX SET problem in tournaments. Here the input is a tournament T and an integer k, and the task is to determine whether T has a feedback vertex set of size at most k. We give a new algorithm for FEEDBACK VERTEX SET IN TOURNAMENTS. The running time of our algorithm is upper-bounded by O(1.6181^k + n^{O(1)}) and by O(1.466^n). Thus our algorithm simultaneously improves over the fastest known parameterized algorithm for the problem by Dom et al. running in time O(2^kk^{O(1)} + n^{O(1)}), and the fastest known exact exponential-time algorithm by Gaspers and Mnich with running time O(1.674^n). On the way to proving our main result we prove a strengthening of a special case of a graph partitioning theorem due to Bollobas and Scott. In particular we show that the vertices of any undirected m-edge graph of maximum degree d can be colored white or black in such a way that for each of the two colors, the number of edges with both endpoints of that color is between m/4-d/2 and m/4+d/2.

##### Cite as

Mithilesh Kumar and Daniel Lokshtanov. Faster Exact and Parameterized Algorithm for Feedback Vertex Set in Tournaments. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 49:1-49:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

@InProceedings{kumar_et_al:LIPIcs.STACS.2016.49,
author =	{Kumar, Mithilesh and Lokshtanov, Daniel},
title =	{{Faster Exact and Parameterized Algorithm for Feedback Vertex Set in Tournaments}},
booktitle =	{33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)},
pages =	{49:1--49:13},
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.49},
URN =		{urn:nbn:de:0030-drops-57501},
doi =		{10.4230/LIPIcs.STACS.2016.49},
annote =	{Keywords: Parameterized algorithms, Exact algorithms, Feedback vertex set, Tour- naments, Graph partitions}
}
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
##### Optimality and tight results in parameterized complexity (Dagstuhl Seminar 14451)

Authors: Stefan Kratsch, Daniel Lokshtanov, Dániel Marx, and Peter Rossmanith

Published in: Dagstuhl Reports, Volume 4, Issue 11 (2015)

##### Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 14451 "Optimality and tight results in parameterized complexity". Over the last two decades parameterized complexity has become one of the main tools for handling intractable problems. Recently, tools have been developed not only to classify problems, but also to make statements about how close an algorithm is to being optimal with respect to running time. The focus of this seminar is to highlight and discuss recent, relevant results within this optimality framework and discover fruitful research directions. The report contains the abstracts of the results presented at the seminar, as well as a collection of open problems stated at the seminar.

##### Cite as

Stefan Kratsch, Daniel Lokshtanov, Dániel Marx, and Peter Rossmanith. Optimality and tight results in parameterized complexity (Dagstuhl Seminar 14451). In Dagstuhl Reports, Volume 4, Issue 11, pp. 1-21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

@Article{kratsch_et_al:DagRep.4.11.1,
author =	{Kratsch, Stefan and Lokshtanov, Daniel and Marx, D\'{a}niel and Rossmanith, Peter},
title =	{{Optimality and tight results in parameterized complexity (Dagstuhl Seminar 14451)}},
pages =	{1--21},
journal =	{Dagstuhl Reports},
ISSN =	{2192-5283},
year =	{2015},
volume =	{4},
number =	{11},
editor =	{Kratsch, Stefan and Lokshtanov, Daniel and Marx, D\'{a}niel and Rossmanith, Peter},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.4.11.1},
URN =		{urn:nbn:de:0030-drops-49677},
doi =		{10.4230/DagRep.4.11.1},
annote =	{Keywords: Algorithms, parameterized complexity, kernels, width measures, exponential time hypothesis, lower bounds}
}
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
##### Graph Modification Problems (Dagstuhl Seminar 14071)

Authors: Hans L. Bodlaender, Pinar Heggernes, and Daniel Lokshtanov

Published in: Dagstuhl Reports, Volume 4, Issue 2 (2014)

##### Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 14071 "Graph Modification Problems". The seminar was held from February 9 to February 14, 2014. This report contains abstracts for presentations about the recent developments on algorithms and structural results for graph modification problems, as well as related areas. Furthermore, the report contains a summary of open problems in this area of research.

##### Cite as

Hans L. Bodlaender, Pinar Heggernes, and Daniel Lokshtanov. Graph Modification Problems (Dagstuhl Seminar 14071). In Dagstuhl Reports, Volume 4, Issue 2, pp. 38-59, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

@Article{bodlaender_et_al:DagRep.4.2.38,
author =	{Bodlaender, Hans L. and Heggernes, Pinar and Lokshtanov, Daniel},
title =	{{Graph Modification Problems (Dagstuhl Seminar 14071)}},
pages =	{38--59},
journal =	{Dagstuhl Reports},
ISSN =	{2192-5283},
year =	{2014},
volume =	{4},
number =	{2},
editor =	{Bodlaender, Hans L. and Heggernes, Pinar and Lokshtanov, Daniel},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.4.2.38},
URN =		{urn:nbn:de:0030-drops-45443},
doi =		{10.4230/DagRep.4.2.38},
annote =	{Keywords: graphs, algorithms, graph modification, fixed parameter tractable, graph classes}
}
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
##### 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
##### Obtaining a Bipartite Graph by Contracting Few Edges

Authors: Pinar Heggernes, Pim van 't Hof, Daniel Lokshtanov, and Christophe Paul

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

##### Abstract
We initiate the study of the Bipartite Contraction problem from the perspective of parameterized complexity. In this problem we are given a graph G on n vertices and an integer k, and the task is to determine whether we can obtain a bipartite graph from G by a sequence of at most k edge contractions. Our main result is an f(k) n^{O(1)} time algorithm for Bipartite Contraction. Despite a strong resemblance between Bipartite Contraction and the classical Odd Cycle Transversal (OCT) problem, the methods developed to tackle OCT do not seem to be directly applicable to Bipartite Contraction. To obtain our result, we combine several techniques and concepts that are central in parameterized complexity: iterative compression, irrelevant vertex, and important separators. To the best of our knowledge, this is the first time the irrelevant vertex technique and the concept of important separators are applied in unison. Furthermore, our algorithm may serve as a comprehensible example of the usage of the irrelevant vertex technique.

##### Cite as

Pinar Heggernes, Pim van 't Hof, Daniel Lokshtanov, and Christophe Paul. Obtaining a Bipartite Graph by Contracting Few Edges. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 13, pp. 217-228, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

@InProceedings{heggernes_et_al:LIPIcs.FSTTCS.2011.217,
author =	{Heggernes, Pinar and van 't Hof, Pim and Lokshtanov, Daniel and Paul, Christophe},
title =	{{Obtaining a Bipartite Graph by Contracting Few Edges}},
booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)},
pages =	{217--228},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-939897-34-7},
ISSN =	{1868-8969},
year =	{2011},
volume =	{13},
editor =	{Chakraborty, Supratik and Kumar, Amit},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2011.217},
URN =		{urn:nbn:de:0030-drops-33579},
doi =		{10.4230/LIPIcs.FSTTCS.2011.217},
annote =	{Keywords: fixed parameter tractability, graph modification problems, edge contractions, bipartite graphs}
}
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
##### 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
##### 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}
}
X

Feedback for Dagstuhl Publishing