Skip to content

Author

Saket Saurabh

The Institute of Mathematical Sciences

We have 4 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 Nov 2026

Vertex Deletion on $H$-Induced-Minor-Free Graphs: Subexponential FPT Algorithms and Approximation Schemes

We study vertex-deletion problems on string graphs and, more generally, on graphs excluding a fixed graph as an induced minor. For every fixed graph $H$, fixed nonnegative integer $t$, and fixed monadic second-order formula $\phi$, we consider the problem of finding a minimum-cardinality set $S$ such that $G-S$ has tre...

D. Lokshtanov, Fahad Panolan, Saket Saurabh et al. · 0 citations
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 · 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

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.