Planar directed graphs simplified by removing few vertices to avoid cycles
A Polynomial Kernel for Planar Directed Feedback Vertex Set
Data Structures and Algorithms
Summary
The problem tackled is figuring out if a directed network (digraph) can be made free of loops by removing a small number of nodes. The authors provide a way to shrink such planar networks into a much smaller version without changing the answer to this problem. They do this by clever steps including simplifying the graph, switching perspectives to its dual, and compressing repeated patterns while keeping the problem’s solution intact. This leads to a smaller, manageable instance that still accurately represents whether the original network can be made loop-free.
What this means in practice
- •For network algorithm designers: Create smaller models of planar communication networks to test feedback removal strategies efficiently.
- •For circuit layout engineers: Simplify planar circuit dependency graphs to identify minimal sets of critical components to alter for cycle elimination.
A theory result. No direct application yet.
Authors
Zimo Sheng, Mingyu Xiao
Abstract
The Directed Feedback Vertex Set problem (DFVS) asks whether a digraph can be made acyclic by deleting at most $k$ vertices. Whether DFVS admits a polynomial kernel parameterized by $k$ is a major open problem in kernelization, even for planar digraphs. We resolve the planar case by giving a deterministic kernel with $O(k^{66}\log^2 k)$ vertices and arcs. Our algorithm proceeds in three stages. First, we apply structural reduction rules to the input digraph, bounding the number of directed faces and some special vertices. Second, we pass to the planar dual, where vertex deletion corresponds to adding groups of reverse arcs to make each weakly connected component strongly connected. The structural bounds in the first stage yield a small retained vertex set in the dual. We then compress the dual instance by identifying vertices with the same distance records from this retained vertex set. The main technical contribution is a directed-cut argument showing that this identification preserves feasibility. Finally, we transform the polynomial-size dual instance back into an instance of Planar Directed Feedback Vertex Set via a $3$-CNF encoding and a planar graph construction.