121 citations · 360 across the 111 of their papers we have counts for
181 papers
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)…
Counting Paths and Trees via Exterior Algebra
Fahad Panolan, Saket Saurabh, Meirav Zehavi +1
We give randomized approximation algorithms for counting k-paths and k-forests in a host graph. Here k denotes the number of pattern vertices, n and m denote the numbers of host ve…
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…
Polynomial Kernels for Spanning Tree with Diversity Requirements
Petr A. Golovach, Diptapriyo Majumdar, Saket Saurabh
Given a connected undirected graph , a spanning tree is a subgraph of such that and is a tree. A collection of spanning trees $T_1,\ldots,T_\ell…