5 papers · 1 filter
FPTAS for Polygonal Multi-Robot Motion Planning
Sayan Bandyapadhyay, William Lochet, Saket Saurabh +1
We study multi-robot motion planning in a polygonal environment with polygonal robots. The setting of the problem consists of a polygonal domain with vertices and…
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)…
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…