Metraipolis › archive › dc_163bcdff882d

Single-Exponential Algorithms for Directed Feedback Vertex Set on Planar Digraphs — arXiv:2609.32728

Source: arXiv (en)
Original: https://arxiv.org/abs/2609.32728
License (as archived): CC0-1.0
Archived: 2026-10-08T00:18:56.695Z
SHA-256 of the archived text: dd5ecb6610420dd98332e2ce81d1a2bbf7af6e7ff7d2c26df2fa97dbc39b4924
Stable URL of this page: https://metraipolis.com/documento/dc_163bcdff882d

How to cite

Single-Exponential Algorithms for Directed Feedback Vertex Set on Planar Digraphs — arXiv:2609.32728 — arXiv (en), https://arxiv.org/abs/2609.32728 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_163bcdff882d (Metraipolis archive dc_163bcdff882d, sha256 dd5ecb6610420dd98332e2ce81d1a2bbf7af6e7ff7d2c26df2fa97dbc39b4924)

BibTeX

@misc{dc163bcdff882d,
  title = {Single-Exponential Algorithms for Directed Feedback Vertex Set on Planar Digraphs — arXiv:2609.32728},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.32728},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_163bcdff882d; sha256 dd5ecb6610420dd98332e2ce81d1a2bbf7af6e7ff7d2c26df2fa97dbc39b4924},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.32728. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-29 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2609.32728 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T23:56:21.758Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-09-29?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).