Author

D. Lokshtanov

2 papers indexed here

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

Preprint 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 · 0 citations