121 citations · 373 across the 96 of their papers we have counts for
12 papers · 1 filter
Algorithms for low-distortion embeddings into arbitrary 1-dimensional spaces
Timothy Carpenter, Fedor V. Fomin, Daniel Lokshtanov +2
We study the problem of finding a minimum-distortion embedding of the shortest path metric of an unweighted graph into a "simpler" metric . Computing such an embedding (exactly…
Clustering with Local Restrictions
Daniel Lokshtanov, Dániel Marx
We study a family of graph clustering problems where each cluster has to satisfy a certain local requirement. Formally, let be a function on the subsets of vertices of a graph…
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…
Covering vectors by spaces: Regular matroids
Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov +1
Seymour's decomposition theorem for regular matroids is a fundamental result with a number of combinatorial and algorithmic applications. In this work we demonstrate how this theor…
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…
The complexity of independent set reconfiguration on bipartite graphs
Daniel Lokshtanov, Amer E. Mouawad
We settle the complexity of the Independent Set Reconfiguration problem on bipartite graphs under all three commonly studied reconfiguration models. We show that under the token ju…
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…
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)…
The Half-integral Erdös-Pósa Property for Non-null Cycles
Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh
A Group Labeled Graph is a pair where is an oriented graph and is a mapping from the arcs of to elements of a group. A (not necessarily directed) cycle is c…