11 citations · 35 across the 50 of their papers we have counts for
11 papers · 1 filter
Balanced Judicious Partition is Fixed-Parameter Tractable
Daniel Lokshtanov, Saket Saurabh, Roohani Sharma +1
The family of judicious partitioning problems, introduced by Bollobás and Scott to the field of extremal combinatorics, has been extensively studied from a structural point of view…
Balanced Stable Marriage: How Close is Close Enough?
Sushmita Gupta, Sanjukta Roy, Saket Saurabh +1
The Balanced Stable Marriage problem is a central optimization version of the classic Stable Marriage problem. Here, the output cannot be an arbitrary stable matching, but one that…
On Treewidth and Stable Marriage
Sushmita Gupta, Saket Saurabh, Meirav Zehavi
Stable Marriage is a fundamental problem to both computer science and economics. Four well-known NP-hard optimization versions of this problem are the Sex-Equal Stable Marriage (SE…
Feedback Vertex Set Inspired Kernel for Chordal Vertex Deletion
Akanksha Agrawal, Daniel Lokshtanov, Pranabendu Misra +2
Given a graph and a parameter , the Chordal Vertex Deletion (CVD) problem asks whether there exists a subset of size at most that hits all induced cycl…
Polylogarithmic Approximation Algorithms for Weighted--Deletion Problems
Akanksha Agrawal, Daniel Lokshtanov, Pranabendu Misra +2
For a family of graphs , the canonical Weighted Vertex Deletion problem is defined as follows: given an -vertex undirected graph and a weight function $w: V…
Packing Cycles Faster Than Erdős-Pósa
Daniel Lokshtanov, Amer E. Mouawad, Saket Saurabh +1
The Cycle Packing problem asks whether a given undirected graph contains vertex-disjoint cycles. Since the publication of the classic Erdős-Pósa theorem in 1965, this…
Designing Deterministic Polynomial-Space Algorithms by Color-Coding Multivariate Polynomials
Gregory Gutin, Felix Reidl, Magnus Wahlström +1
In recent years, several powerful techniques have been developed to design {\em randomized} polynomial-space parameterized algorithms. In this paper, we introduce an enhancement of…
Rank Vertex Cover as a Natural Problem for Algebraic Compression
Syed Mohammad Meesum, Fahad Panolan, Saket Saurabh +1
The question of the existence of a polynomial kernelization of the Vertex Cover Above LP problem has been a longstanding, notorious open problem in Parameterized Complexity. Five y…
Covering Small Independent Sets and Separators with Applications to Parameterized Algorithms
Daniel Lokshtanov, Fahad Panolan, Saket Saurabh +2
We present two new combinatorial tools for the design of parameterized algorithms. The first is a simple linear time randomized algorithm that given as input a -degenerate graph…
Finding, Hitting and Packing Cycles in Subexponential Time on Unit Disk Graphs
Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan +2
We give algorithms with running time for the following problems. Given an -vertex unit disk graph and an integer , decide whethe…
Parameterized Complexity and Approximability of Directed Odd Cycle Transversal
Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh +1
A directed odd cycle transversal of a directed graph (digraph) is a vertex set that intersects every odd directed cycle of . In the Directed Odd Cycle Transversal (DOCT)…