arXiv preprint ·
A Polynomial Kernel for Planar Directed Feedback Vertex Set
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
The Inverse Lyndon Array
High-Dimensional Ultra-Log-Concave Distributions
An Arboricity-Sensitive Algorithm for the $K_r-e$-Free Graph Sandwich Problem
Byzantine Causal Reliable Broadcast (BCRB) with Constant-Size Message Metadata
Single-Pass Estimation of the Clustering Coefficient Distribution in Graph Streams
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.