Single-Exponential Algorithms for Directed Feedback Vertex Set on Planar Digraphs
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: We're looking at the paper: "Single-Exponential Algorithms for Directed Feedback Vertex Set on Planar Digraphs".
Jane: Here's the gist of the paper. Single-Exponential Algorithms for Directed Feedback Vertex Set on Planar Digraphs gives the first single-exponential fixed-parameter algorithms for Directed Feedback Vertex Set on planar digraphs, parameterized by the solution size k <ref:2609.32728#pg16>.
Tom: This contrasts with general digraphs where the best known algorithms run in time 2O(k log k)nO(1), and whether a 2o(k log k)nO(1)-time algorithm exists remains a major open problem <ref:2609.32728#pg16>.
Jane: Structural Tools The authors introduce structural relations between the alternation of incoming and outgoing arcs around vertices of a plane digraph and its directed facial walks <ref:2609.32728#pg7> The main tool is an exact Euler-type counting identity for plane digraphs <ref:2609.32728#pg16>.
Tom: This identity shows that every small solution must carry a large share of the vertices whose in- and out-arcs alternate in the embedding <ref:2609.32728#pg16>.
Title and authors: Tom: So we're looking at this paper called "Single-Exponential Algorithms for Directed Feedback Vertex Set on Planar Digraphs," and what they did is they found the first single-exponential fixed-parameter algorithms for this problem on planar digraphs, parameterized by the solution size k.
Jane: That sounds pretty big, Tom. What does that mean in plain English for someone listening right now?
Tom: It means we can find a solution to removing feedback vertices in a planar directed graph using an algorithm whose running time is bounded by two to the power of k times some polynomial of n, which is way better than the general case where you're talking about n log n.
Lu: The core idea they use is this exact Euler-type counting identity for plane digraphs, which basically shows that every small solution must include a large portion of vertices whose in and out arcs alternate around the embedding.
Meng: But what's the catch here? Is this just a theoretical win, or can we actually run this on something like real traffic data without it slowing down to a crawl?
Tom: The authors present two algorithms for Planar DFVS with one-sided error, and one deterministic algorithm that runs in time eight point zero three k n O of one <ref:2609.32728#pg1>.
Jane: That deterministic running time, eight point zero three k n O of one sounds much more concrete than just a theoretical bound <ref:2609.32728#pg1>. What's the trade-off when you use that deterministic method versus the randomized one?
Tom: The deterministic approach branches on directed facial walks that contain few deletable nonbimodal vertices, and it uses a measure mu equals j minus alpha times M to guide the recursion, which leads to that eight point zero three k n O of one running time <ref:2609.32728#pg1>.
Lu: And the randomized algorithm, which is faster by two plus the square root of five k n O of one samples a vertex based on its weight when the total weight L is greater than three times k <ref:2609.32728#pg1>.
Jane: So, for someone who just wants to know if this helps them solve a real problem—say, finding cycles in some network—what does this mean for their day-to-day work?
Tom: It means that if your graph has the planarity property and you're looking for a small feedback vertex set, you have an algorithm that is guaranteed to be fixed-parameter tractable with a single exponential dependency on k.
Meng: But we need to talk about the limitations. The paper mentions that whether DFVS on general digraphs admits an algorithm running in time c k n O of one for some constant c remains a major open problem, and they also noted that their kernelization might increase the solution budget by a factor related to six six log two k <ref:2609.32728#pg2>.
Lu: That kernelization point is important because it shows that while they solve the planar version nicely, we still don't have a guaranteed polynomial kernel for general digraphs parameterized by k, which is another open question mentioned in their work <ref:2609.32728#pg2>.
Jane: So, if you’re hoping for a super fast solution on a general graph without relying on planarity, this paper points out that the problem is still wide open.
Tom: Exactly. We have these two fixed-parameter algorithms for planar DFVS now, but the question about general digraphs remains unanswered regarding whether c k n O of one time exists <ref:2609.32728#pg1>.
Lu: The structural lemma they use—the one relating total vertex weight L to the weight of a DFVS X by showing L is less than two times the size of X plus its weight—is what unlocks both their randomized and deterministic approaches, connecting the geometry of plane digraphs to the solution size k <ref:2609.32728#pg3>.
Jane: It’s interesting how they use this counting identity to show that every small solution has to hit a big set of vertices with alternating in and out arcs, which is a nice geometric constraint.
Tom: Right. And when we look at the improvements, they suggest using this exact Euler-type counting identity to show that every small solution must carry a large share of the vertices whose in and out arcs alternate in the embedding <ref:2609.32728#pg1>.
The paper's summary: Tom: So, we're looking at how they summarized this work on planar directed feedback vertex set and what that really means for solving these kinds of problems.
Jane: Basically, the paper shows that for graphs that are planar, if you want to remove a small number of vertices to break all the cycles in the direction they point, there's an algorithm whose running time is just two to the power of k times some polynomial of n.
Tom: That’s it. It’s fixed-parameter tractable with a single exponential dependency on that solution size k, which is much better than what we usually see for general directed graphs where things get way worse.
Lu: What they really focus on is this exact Euler type counting identity for plane digraphs. It connects the geometry of how the graph is drawn in space to how many vertices you need to remove.
Jane: So, they’re saying that because it’s planar, every small solution you find has to hit a large portion of vertices where their incoming and outgoing arcs are alternating around the drawing. That's a big structural hint for the algorithm.
Tom: Exactly. It shows that the physical layout of the graph dictates which parts are most important when looking for feedback vertices.
Meng: But what’s actually cool is that they didn't just stop there with theory; they gave us two actual algorithms, one randomized and one deterministic, both running in time bounds tied directly to k.
Jane: That deterministic version runs in eight point zero three k n O of one time, which is quite specific. And it uses polynomial space for the computation, which is important for when we try to actually deploy these kinds of systems.
Tom: The randomized one is faster at two plus the square root of five k n O of one time, with a one-sided error. It means you’re either guaranteed a solution of size k or you fail, but with a decent probability if one exists.
Lu: What this changes for representation learning or graph theory is that it proves we can use geometric constraints—like planarity—to get tight bounds on problems we thought were much harder to solve in terms of the solution size k.
Jane: It’s a step toward showing that for certain structured data, the complexity of finding a small fix is bounded by just an exponential factor of that fix size, not the whole input graph.
Tom: And they also pointed out some open questions; specifically whether we can get a polynomial kernel for planar feedback vertex set without increasing the solution budget.
Lu: That kernel question is still wide open, and it connects to what we discussed earlier about how different parameterized problems behave when you try to simplify the input first.
Jane: So, while they nailed single exponential algorithms for planar graphs, there are still big questions about making those algorithms even tighter or applying them more broadly.
Tom: Right. We’ve got these concrete tools for planar feedback vertex set now, but the challenge is figuring out how to generalize these geometric ideas to much more complex graph structures without losing that fixed-parameter advantage.
The paper's improvements: Tom: So, we're looking at how they suggest improving these existing single exponential algorithms for planar directed feedback vertex set and what those upgrades actually mean for performance.
Jane: They propose a few ways to make the randomized algorithm even better by sampling vertices based on their weight when the total weight is really high, which helps guarantee a success probability of at least one half if a solution exists.
Lu: And for the deterministic side, they introduce an idea about how to guide that branching process using this measure mu equals j minus alpha times M, where alpha is chosen in a specific way to keep the complexity manageable.
Tom: That leads to the eight point zero three k n O of one time complexity we talked about earlier, and it’s tied directly into tracking the measure mu over the circular faces of those drawings.
Jane: They also suggest that for that deterministic run time, you need polynomial space, which is a concrete constraint when you think about deploying these algorithms on real-world data where memory matters.
Lu: The structural improvements they discuss rely heavily on that exact Euler counting identity again to show how every small solution must have a large share of those alternating in and out arcs around the embedding.
Tom: It's like they’re saying the geometry forces your hand; you can’t avoid those alternating arcs if you want a small solution.
Jane: That’s a powerful way to frame it, showing that the structure of the plane graph itself is what limits how small the feedback set can be.
Lu: The authors also highlighted two open problems they think are important: whether we can find a polynomial kernel for planar feedback vertex set without increasing the solution budget, and whether general directed feedback vertex set has an algorithm running in time c k n O of one for some constant c.
Tom: So the implication is that while we have these tight bounds for planar graphs, the next big engineering hurdle is figuring out how to handle those kernelization questions or generalize these ideas to non-planar graphs.
Jane: It really shows us that understanding the geometric constraints of a graph can be a huge lever when trying to make NP hard problems tractable by reducing their dependency on the input size n.
Lu: And we need to keep an eye on those open problems because if we solve the kernelization one, it would mean we have a much better way to handle these instances in practice.
Conclusion: Tom: So we're wrapping up this discussion on "Single-Exponential Algorithms for Directed Feedback Vertex Set on Planar Digraphs" by summarizing what they achieved and why it matters for AI research right now.
Jane: Essentially, the authors presented the first single exponential fixed parameter algorithms for planar directed feedback vertex set, showing that you can solve this problem much faster when the graph has a planar structure.
Lu: The main takeaway is using an exact Euler type counting identity for plane digraphs to prove that every small solution must hit a large portion of vertices with alternating in and out arcs in the embedding.
Tom: It’s a clean way to connect the physical drawing of the graph to the actual size of the feedback set you need to remove.
Meng: From an engineering standpoint, getting those running times like eight point zero three k n O of one time is solid, and they use polynomial space for both methods which is something we can actually work with at scale.
Jane: They also gave us a randomized algorithm that runs in two plus the square root of five k n O of one time, which is pretty efficient if you're willing to accept a small error probability.
Lalam: I’m confident in this result; it confirms that for planar graphs, we can indeed get these tight fixed-parameter bounds tied directly to the solution size k.
Tom: So the paper sets a high bar for how we approach NP hard problems when they have underlying geometric structure like planarity.
Lu: It also leaves those open questions about whether a polynomial kernel exists for planar feedback vertex set, which is something we still need to figure out to get the absolute best practical performance.
Jane: It’s a good reminder that in AI research, understanding the structure of the data or graph itself can unlock complexity bounds that wouldn't be possible otherwise.
Meng: I just hope we see more work applying these structural counting identities to graphs that aren't as nicely behaved as planar ones, because those are the ones we actually deal with in production.
Tom: Yeah, keeping an eye on those kernelization gaps is key for moving this from theory into something practical for real-world AI applications.
Daniel Lokshtanov, Saket Saurabh, Jie Xue
University of California, Santa Barbara, USA · Institute of Mathematical Sciences, HBNI, Chennai, India · New York University Shanghai
cs.DS
Submitted: 2026-09-26
Updated: 2026-11-09
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 83/100
The gist: Single-Exponential Algorithms for Directed Feedback Vertex Set on Planar Digraphs gives the first single-exponential fixed-parameter algorithms for Directed Feedback Vertex Set on planar digraphs…
Key concepts
- Directed Feedback Vertex Set (DFVS)
- This is a set of vertices whose removal breaks all directed cycles in a graph. In this context, the goal is to find the smallest such set, parameterized by its size k.
- Planar Digraphs
- These are directed graphs that can be drawn on a plane without any edges crossing. This geometric constraint allows the authors to use specific structural properties of embeddings to design more efficient algorithms for solving NP-hard problems like DFVS.
- Vertex Weight and Bimodality
- A vertex weight is defined based on the in-degree minus one. A vertex is 'bimodal' if its weight is non-positive. The paper uses these weights and the concept of bimodal vertices to guide the selection process for removing vertices from a potential solution.
- Euler-type Counting Identity
- This is a mathematical tool specific to planar digraphs that relates properties of the graph's embedding (like incoming and outgoing arcs around vertices) to the size of any small DFVS. It proves that small solutions must involve many vertices with alternating in/out arcs.
Terminology
Summary
Single-Exponential Algorithms for Directed Feedback Vertex Set on Planar Digraphs gives the first single-exponential fixed-parameter algorithms for Directed Feedback Vertex Set on planar digraphs, parameterized by the solution size k <ref:2609. p. 0 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. 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 2O(k log k)
(n + m), and whether a 2o(k log k)n
O(1)-time algorithm exists remains
a major open problem.Where the paper says it
Where the paper says it
Structural Tools
The authors introduce structural relations between the alternation of incoming and outgoing arcs around vertices of a plane digraph and its directed facial walks <ref:2609.32728#pg7> The main tool is an exact Euler-type counting identity for plane digraphs <ref:2609. p. 0 This contrasts with general digraphs, where the best known algorithms
run in time 2O(k log k)
(n + m), and whether a 2o(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. 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.Where the paper says it
Where the paper says it
Vertex Weights and DFVS
The authors define a vertex weight as w(v) = b(v)−1 for v ∈ V (D), and a vertex is bimodal if w(v) ≤ 0 <ref:2609.32728#pg7> The main structural lemma relates the total vertex weight L to the weight of a DFVS, showing that L. p. 2 Our main structural lemma (Lemma 3. 3) relates the total vertex weight L to the weight of a
DFVS. let L = w(V (D)) denote the total weight of the cyclic core D. Every vertex of D has both an
incoming and an outgoing arc, so its weight is nonnegative.Where the paper says it
Where the paper says it
Randomized Algorithms
The authors present two randomized algorithms for Planar DFVS with one-sided error <ref:2609.32728#pg16>. The simple 6. p. 1 It turns out that the following problem is polynomial time solvable: given a plane digraph
D, find the smallest feedback vertex set which only contains bimodal vertices. This polynomial
time algorithm follows from a simple reduction to Planar Directed Feedback Arc Set
(Planar DFAS), which in turn known to be solvable in polynomial time [LY78, MSW22] . 1 A simple 6. 75k
-time algorithm
Our algorithm is recursive, and roughly works as follows. 75kn
O(1)
. 2 A (2 + √
5)k
-time algorithm
We improve the previous algorithm by trying, before every sampling step, to find a solution that
contains only the current bimodal vertices.Where the paper says it
Where the paper says it
Where the paper says it
Deterministic Algorithms
The deterministic algorithm branches on directed facial walks containing few deletable nonbimodal vertices <ref:2609.32728#pg16>. It uses a measure µ(I) = j − αM to guide the recursion, where branching instances create at most four children of measure µ − 1 and one child of measure µ − α <ref:2609. p. 3 The deterministic running time can be improved by allowing branching on circular faces with
more deletable nonbimodal vertices, thereby postponing enumeration. For example, branching
on faces with at most four such vertices when q ≥ 3m, and at most six when 5m/3 ≤ q < 3m,
gives a running time of 7. Single-Exponential Algorithms for Directed Feedback Vertex Set
on Planar Digraphs∗
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 + √
5)
kn
O(1) = 4. Email: jiexue@nyu. 1
arXiv:2609.Where the paper says it
Where the paper says it
Where the paper says it
Conclusion
The paper concludes by presenting the first single-exponential fixed-parameter algorithms for Planar DFVS, both randomized and deterministic, with running times (2 + √5)knO(1) and 8.030knO(1) respectively <ref:2609. p. 0 Email: jiexue@nyu. 1
arXiv:2609. Whether DFVS admits a
polynomial kernel parameterized by the solution size remains open on general digraphs [BEG+21]. Until very recently, this was open even on planar digraphs. 04kn
O(1)
. Both algorithms use polynomial space.Where the paper says it
Where the paper says it
Where the paper says it
References
[BBYG00] Ann Becker, Reuven Bar-Yehuda, and Dan Geiger. Randomized algorithms for the loop cutset problem. p. 0 Mehlhorn’s 1984 monograph already contained a fixed-parameter algorithm for the
undirected problem [Meh84, CCHM15]. Since then, FVS has been a central problem in the
development of parameterized algorithms, with techniques such as randomized branching, iterative compression, and Cut& Count contributing to its study [BBYG00, GGH+06, CNP+11]. These improvements retain a
∗This manuscript is a preliminary draft. We would have preferred more time to explore the ideas and polish
the presentation, but the current pace of research has prompted us to share the results at this stage.Where the paper says it
Where the paper says it
[BCX26] Tian Bai, Yixin Cao, and Mingyu Xiao. Feedback set problems on bounded-degree (planar) graphs. p. 2 Thus the problem reduces to weighted
Planar Directed Feedback Arc Set, which is polynomial-time solvable [LY78, MSW22]. This splitting argument builds on the work of Bai, Cao, and Xiao [BCX26], who showed that
DFVS is polynomial-time solvable on planar digraphs in which every vertex has in-degree at
most one or out-degree at most one. This implies that no cycle in D is disjoint from S iff no cycle in D∗
is disjoint from AS. The above observation allows us to reduce the problem of computing a minimum P-avoiding
DFVS of D to the problem of computing a minimum FAS A ⊆ {ev ∈ E(D∗
) : v ∈ Q} of D∗
. Email: jiexue@nyu. 1
arXiv:2609.Where the paper says it
Where the paper says it
Where the paper says it
[BEG+21] Benjamin Bergougnoux, Eduard Eiben, Robert Ganian, Sebastian Ordyniak, and M. S. Ramanujan. Towards a polynomial kernel for directed feedback vertex set. p. 0 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. Email: jiexue@nyu. 1
arXiv:2609.Where the paper says it
Where the paper says it
[BKN+18] Marthe Bonamy, Lukasz Kowalik, Jesper Nederlof, Micha l Pilipczuk, Arkadiusz Soca la, and Marcin Wrochna. On directed feedback vertex set parameterized by treewidth. p. 0 Single-Exponential Algorithms for Directed Feedback Vertex Set
on Planar Digraphs∗
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 + √
5)
kn
O(1) = 4. Email: jiexue@nyu. 1
arXiv:2609.Where the paper says it
Where the paper says it
[CCHM15] Rajesh Chitnis, Marek Cygan, MohammadTaghi Hajiaghayi, and D´aniel Marx. Directed subset feedback vertex set is fixed-parameter tractable. p. 0 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. Email: jiexue@nyu. 1
arXiv:2609.Where the paper says it
Where the paper says it
[CLL+08] Jianer Chen, Yang Liu, Songjian Lu, Barry O’Sullivan, and Igor Razgon. A fixedparameter algorithm for the directed feedback vertex set problem. p. 0 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 2O(k log k)
(n + m), and whether a 2o(k log k)n
O(1)-time algorithm exists remains
a major open problem. Email: jiexue@nyu. 1
arXiv:2609.Where the paper says it
Where the paper says it
[CNP+11] Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Micha l Pilipczuk, Johan M. M. van Rooij, and Jakub Onufry Wojtaszczyk. Solving connectivity problems parameterized by treewidth in single exponential time. p. 1 Using the treewidth algorithm
of [BKN+18] improves this to 2O(k
33 log k)n
O(1), since a planar graph on N vertices has treewidth
O(
√
N). Thus, although the kernel resolves the polynomial-kernel question on planar digraphs,
it does not by itself resolve the single-exponential running-time question. Email: jiexue@nyu. 1
arXiv:2609.Where the paper says it
Where the paper says it
[GGH+06] Jiong Guo, Jens Gramm, Falk H¨uffner, Rolf Niedermeier, and Sebastian Wernicke. Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization. p. 0 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. Email: daniello@ucsb. ‡The Institute of Mathematical Sciences, HBNI, Chennai, India; and University of Bergen, Norway.Where the paper says it
Where the paper says it
[HT74] John Hopcroft and Robert Tarjan. Efficient planarity testing. p. 1 factorial dependence on k, leaving the central question of whether DFVS admits an algorithm
running in time c
kn
O(1) for some constant c. Planarity is a natural setting in which to seek such an algorithm. Email: jiexue@nyu. 1
arXiv:2609.Where the paper says it
Where the paper says it
[IK19] Yoichi Iwata and Yusuke Kobayashi. Improved analysis of highest-degree branching for feedback vertex set. p. 2 Thus the problem reduces to weighted
Planar Directed Feedback Arc Set, which is polynomial-time solvable [LY78, MSW22]. This splitting argument builds on the work of Bai, Cao, and Xiao [BCX26], who showed that
DFVS is polynomial-time solvable on planar digraphs in which every vertex has in-degree at
most one or out-degree at most one.Where the paper says it
[LN20] Jason Li and Jesper Nederlof. Detecting feedback vertex sets of size k in o∗(2. p. 4 For a digraph D we write
V (D) and E(D) for its vertex and arc sets, and D − X for the digraph obtained by deleting
X ⊆ V (D). A directed feedback vertex set (DFVS) of D is a set X ⊆ V (D) such that D − X
is acyclic. Email: jiexue@nyu. 1
arXiv:2609.Where the paper says it
Where the paper says it
[LRS18] Daniel Lokshtanov, M. S. Ramanujan, and Saket Saurabh. p. 0 n
O(1)) [CLL+08]. Lokshtanov, Ramanujan, and Saurabh subsequently obtained a
linear dependence on the input size, with running time O(k! Single-Exponential Algorithms for Directed Feedback Vertex Set
on Planar Digraphs∗
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 + √
5)
kn
O(1) = 4. Email: jiexue@nyu. 1
arXiv:2609.Where the paper says it
Where the paper says it
Where the paper says it
[LY78] Claudio L. Lucchesi and Daniel H. p. 0 Single-Exponential Algorithms for Directed Feedback Vertex Set
on Planar Digraphs∗
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 + √
5)
kn
O(1) = 4. 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. Email: daniello@ucsb. ‡The Institute of Mathematical Sciences, HBNI, Chennai, India; and University of Bergen, Norway.Where the paper says it
Where the paper says it
Where the paper says it
[Meh84] Kurt Mehlhorn. Data Structures and Algorithms 2: Graph Algorithms and NPCompleteness, volume 2 of Monographs in Theoretical Computer Science. p. 0 Single-Exponential Algorithms for Directed Feedback Vertex Set
on Planar Digraphs∗
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 + √
5)
kn
O(1) = 4. The parameterized study of FVS predates the formal development of parameterized complexity. Mehlhorn’s 1984 monograph already contained a fixed-parameter algorithm for the
undirected problem [Meh84, CCHM15].Where the paper says it
Where the paper says it
[MSW22] Marcelo Garlet Millani, Raphael Steiner, and Sebastian Wiederrecht. Colouring non-even digraphs. p. 1 However, this does not yield a single-exponential algorithm parameterized by the solution size k. Whether such an algorithm exists remained open even for planar digraphs. Email: jiexue@nyu. 1
arXiv:2609. Email: jiexue@nyu. 1
arXiv:2609.Where the paper says it
Where the paper says it
Where the paper says it
[RS03] Venkatesh Raman and Saket Saurabh. Parameterized complexity of directed feedback set problems in tournaments. p. 0 Its directed counterpart,
Directed Feedback Vertex Set (DFVS), asks for at most k vertices that intersect every
directed cycle of a given digraph. Although the two problems have similar formulations, their
parameterized complexity has developed very differently.Where the paper says it
[SX26] Zimo Sheng and Mingyu Xiao. A polynomial kernel for planar directed feedback vertex set, 2026 <ref:2609. p. 0 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.Where the paper says it
[XX25] Ziliang Xiong and Mingyu Xiao. A simplified parameterized algorithm for directed feedback vertex set. p. 0 Single-Exponential Algorithms for Directed Feedback Vertex Set
on Planar Digraphs∗
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 + √
5)
kn
O(1) = 4. Email: jiexue@nyu. 1
arXiv:2609.Where the paper says it
Where the paper says it
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Improved algorithm for Planar Directed Feedback Vertex Set (DFVS) can find a solution in time (2 + sqrt(5))knO(1) with a one-sided error, returning either a DFVS of size at most k or Fail, and returns a solution with probability at least 1/2 whenever one exists.
-
Improved algorithm for Planar Directed Feedback Vertex Set can find a solution in time 8.030knO(1) deterministically, using polynomial space, by employing branching on circular faces with at most four deletable nonbimodal vertices when the number of such vertices exceeds three times the number of marked faces.
-
Improved randomized algorithm for Planar Directed Feedback Vertex Set can find a solution in time (2 + sqrt(5))knO(1) and polynomial space, by recursively sampling a vertex proportional to its weight and solving the remaining instance with budget k-1, guaranteeing a success probability of at least 1/2.
-
Improved deterministic algorithm for Planar Directed Feedback Vertex Set can find a solution in time 8.030knO(1) and polynomial space by tracking the measure mu = j - alphaM, where alpha is chosen such that 4/c + c - alpha = 1, to guide branching on circular faces efficiently.
-
The improved systems can solve Planar DFVS by utilizing an exact Euler-type counting identity for plane digraphs to show that
every small solution must carry a large share of the vertices whose in- and out-arcs alternate in the embedding.
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 k)(n+m), and whether a 2 o(k 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.
Sources
Related papers
- Exploiting Low Scanwidth to Resolve Soft Polytomies
- PHastR: Faster Minimal Perfect Hashing with Rotated Layouts
- Fine-Grained Complexity of Approximating Vector Knapsack: A Faster Algorithm and Equivalence with k-SUM in 2D
- Polynomial-time computation of p-contraction fixed points for even p
- Separations Between Submodular-Like Graph Widths
- Bounded Integer Programming in Almost N 2d Time