Author

Saket Saurabh

The Institute of Mathematical Sciences

h-index 54 View on Semantic Scholar

We have 3 of 561 papers

We haven’t gathered this author’s papers yet. Follow them and we’ll fetch their work.

Not the right person? Other researchers publish under this name.

Preprint Oct 2026

How to Fix a Broken Metric: A Linear Kernel, Tight Bounds, and Tree Metrics

Given a complete graph whose edge weights represent dissimilarities, Metric Violation Distance asks whether at most $k$ weights can be changed to form a metric. Motivated by metric repair for noisy data, the problem admits a polynomial-time $O(\log n)$-approximation due to Cohen-Addad, Fan, Lee and de Mesmay [SIAM J. C...

Sayan Bandyapadhyay, William Lochet, D. Lokshtanov et al. · 0 citations

Sep 2026

Single-Exponential Algorithms for Directed Feedback Vertex Set on Planar Digraphs

We consider Directed Feedback Vertex Set on planar digraphs, parameterized by the solution size $k$. We give a randomized algorithm with one-sided error running in time $(2+\sqrt5)^k n^{O(1)}= 4.24^k n^{O(1)}$, and a deterministic algorithm running in time $8.04^k n^{O(1)}$. Both algorithms use polynomial space. To the...

D. Lokshtanov, Saket Saurabh, Jie Xue · arXiv.org · 1 citation

Preprint Sep 2026

Counting Paths and Trees via Exterior Algebra

These algorithms combine exterior algebra with random matrix estimators, using the tensor-train moment bound of Rakhshan and Rabusseau~[AISTATS 2020].

Fahad Panolan, Saket Saurabh, M. Zehavi et al. · 0 citations