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
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
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