121 citations · 373 across the 96 of their papers we have counts for
14 papers · 1 filter
A Constant Factor Approximation for Navigating Through Connected Obstacles in the Plane
Neeraj Kumar, Daniel Lokshtanov, Saket Saurabh +1
Given two points s and t in the plane and a set of obstacles defined by closed curves, what is the minimum number of obstacles touched by a path connecting s and t? This is a funda…
Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths
Daniel Lokshtanov, Saket Saurabh, Meirav Zehavi
In the Disjoint Paths problem, the input consists of an -vertex graph and a collection of vertex pairs, , and the objective is to determine whethe…
Dominated Minimal Separators are Tame (Nearly All Others are Feral)
Peter Gartland, Daniel Lokshtanov
A class of graphs is called {\em tame} if there exists a constant so that every graph in on vertices contains at most minimal separators, {\e…
Computing the Largest Bond and the Maximum Connected Cut of a Graph
Gabriel L. Duarte, Hiroshi Eto, Tesshu Hanaka +6
The cut-set of a graph is the set of edges that have one endpoint in and the other endpoint in , and whenever is connected…
Finding large induced sparse subgraphs in -free graphs in quasipolynomial time
Peter Gartland, Daniel Lokshtanov, Marcin Pilipczuk +2
For an integer , a graph is called {\em{-free}} if does not contain any induced cycle on more than~ vertices. We prove the following statement: for every pair…
On the Parameterized Approximability of Contraction to Classes of Chordal Graphs
Spoorthy Gunda, Pallavi Jain, Daniel Lokshtanov +2
A graph operation that {\em contracts edges} is one of the fundamental operations in the theory of graph minors. Parameterized Complexity of editing to a family of graphs by contra…
Independent Set on P-Free Graphs in Quasi-Polynomial Time
Peter Gartland, Daniel Lokshtanov
We present an algorithm that takes as input a graph with weights on the vertices, and computes a maximum weight independent set of . If the input graph excludes a pa…
A Parameterized Approximation Scheme for Min -Cut
Daniel Lokshtanov, Saket Saurabh, Vaishali Surianarayanan
In the Min -Cut problem, input is an edge weighted graph and an integer , and the task is to partition the vertex set into non-empty sets, such that the total weight…
Computation of Hadwiger Number and Related Contraction Problems: Tight Lower Bounds
Fedor V. Fomin, Daniel Lokshtanov, Ivan Mihajlin +2
We prove that the Hadwiger number of an -vertex graph (the maximum size of a clique minor in ) cannot be computed in time , unless the Exponential Time Hypothes…
The Parameterized Complexity of Guarding Almost Convex Polygons
Akanksha Agrawal, Kristine V. K. Knudsen, Daniel Lokshtanov +2
Art Gallery is a fundamental visibility problem in Computational Geometry. The input consists of a simple polygon P, (possibly infinite) sets G and C of points within P, and an int…
ETH-Tight Algorithms for Long Path and Cycle on Unit Disk Graphs
Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan +2
We present an algorithm for the extensively studied Long Path and Long Cycle problems on unit disk graphs that runs in time . Under the Exponential Time Hypot…
b-Coloring Parameterized by Clique-Width
Lars Jaffke, Paloma T. Lima, Daniel Lokshtanov
We provide a polynomial-time algorithm for b-Coloring on graphs of constant clique-width. This unifies and extends nearly all previously known polynomial time results on graph clas…
Removing Connected Obstacles in the Plane is FPT
Eduard Eiben, Daniel Lokshtanov
Given two points in the plane, a set of obstacles defined by closed curves, and an integer , does there exist a path between the two designated points intersecting at most o…
Faster and Enhanced Inclusion-Minimal Cograph Completion
Christophe Crespelle, Daniel Lokshtanov, Thi Ha Duong Phan +1
We design two incremental algorithms for computing an inclusion-minimal completion of an arbitrary graph into a cograph. The first one is able to do so while providing an additiona…