Planar digraph feedback vertex set solved faster with new algorithms

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

Data Structures and Algorithms

Summary

Directed Feedback Vertex Set is a problem about removing certain points from a network of arrows to break all cycles. The authors found faster algorithms to solve this problem specifically for networks that can be drawn on a plane without crossings. Their new methods are more efficient than previous ones for this special case and use clever counting techniques and known mathematical results. These algorithms also keep the memory use manageable.

What this means in practice

  • For network algorithm developers: Design algorithms for eliminating cycles in planar directed networks more efficiently, enabling faster graph-based computations in planar settings.
  • For circuit layout engineers: Improve tools for detecting and fixing feedback loops in planar circuit designs by integrating faster algorithms for removing vertices breaking cycles.

Authors

Daniel Lokshtanov, Saket Saurabh, Jie Xue

Abstract

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 best of our knowledge, these are the first single-exponential fixed-parameter algorithms for Directed Feedback Vertex Set on planar digraphs. This contrasts with general digraphs, where the best known algorithms run in time $2^{O(k\log k)}(n+m)$, and whether a $2^{o(k\log k)}n^{O(1)}$-time algorithm exists remains a major open problem. Our main tool is an exact Euler-type counting identity for plane digraphs. It shows that every small solution must carry a large share of the vertices whose in- and out-arcs alternate in the embedding, while solutions avoiding such vertices can be computed by reducing to Directed Feedback Arc Set, which is known to be solvable in polynomial time on planar digraphs via the Lucchesi-Younger theorem.