121 citations · 373 across the 96 of their papers we have counts for
11 papers · 1 filter
How to Fix a Broken Metric: A Linear Kernel, Tight Bounds, and Tree Metrics
Sayan Bandyapadhyay, William Lochet, Daniel Lokshtanov +4
Given a complete graph whose edge weights represent dissimilarities, Metric Violation Distance asks whether at most weights can be changed to form a metric. Motivated by metric…
Single-Exponential Algorithms for Directed Feedback Vertex Set on Planar Digraphs
Daniel Lokshtanov, Saket Saurabh, Jie Xue
We consider Directed Feedback Vertex Set on planar digraphs, parameterized by the solution size . We give a randomized algorithm with one-sided error running in time $(2+\sqrt5)…
Forbidden Subgraphs of Graphs with Low Bandwidth
Maria Chudnovsky, Daniel Lokshtanov, Eran Nevo
A layout of a graph G is an injective function , and the bandwidth of a layout f is . The bandwidth bw(G) of G is…
Covering Points with Rectangular Boundaries
Madhumita Kundu, Daniel Lokshtanov, Soumi Nandi +2
Geometric covering problems ask for a small family of geometric objects whose union covers a given point set. We study the more restrictive \emph{boundary covering} variant, where…
Courcelle's Theorem in Truly Linear FPT
Tuukka Korhonen, Daniel Lokshtanov, Saket Saurabh
Recently, Bumpus, Downey, Eagling-Vose, Enright, Fellows, Kutner, Larios-Jones, Martin, Rosamond, and Yates defined Truly Linear FPT (TLFPT) to be the class of parameterized proble…
Fine-Grained Bounds for Courcelle's Theorem
Daniel Lokshtanov, Fahad Panolan, Saket Saurabh +2
Courcelle's theorem states that there exists an algorithm that takes as input a graph of treewidth at most and a MSO formula , and determines whether satisfies i…
Parameterized Approximation of Rectangle Stabbing
Huairui Chu, Ajaykrishnan E S, Daniel Lokshtanov +4
In the Rectangle Stabbing problem, input is a set of axis-parallel rectangles and a set of axis parallel lines in the plane. The task is to find a minimum siz…
Faster Parameterized Vertex Multicut
Huairui Chu, Yuxi Liu, Daniel Lokshtanov +3
In the {\sc Vertex Multicut} problem the input consists of a graph , integer , and a set of pairs of vertices of . The ta…
On the complexity of Multipacking
Sandip Das, Sk Samim Islam, Daniel Lokshtanov
A multipacking in an undirected graph is a set such that for every vertex and for every integer , the ball of radius around conta…
Finding large sparse induced subgraphs in graphs of small (but not very small) tree-independence number
Daniel Lokshtanov, Michał Pilipczuk, Paweł Rzążewski
The independence number of a tree decomposition is the size of a largest independent set contained in a single bag. The tree-independence number of a graph is the minimum indep…
FPT Approximations for Connected Maximum Coverage
Tanmay Inamdar, Satyabrata Jana, Madhumita Kundu +3
We revisit connectivity-constrained coverage through a unifying model, Partial Connected Red-Blue Dominating Set. Given a red-blue bipartite graph and an auxiliary connectivity…