TL;DR
This paper tackles the "k-APEX problem": finding if deleting at most k vertices can make a graph planar. While existing theory guarantees a solution exists, the algorithms are impractically complex. The authors present a significantly simpler, quadratic-time algorithm by cleverly reducing the graph and leveraging techniques for graphs with bounded treewidth.
What Problem Does This Paper Address?
The core problem is determining if a graph G can be made planar by removing k or fewer vertices. This is known as the k-APEX problem. Planarity is a fundamental graph property, and many problems become much easier on planar graphs. The k-APEX problem is important because it quantifies how "far" a graph is from being planar in terms of vertex deletions. While the celebrated Graph Minor Theorem by Robertson and Seymour implies a polynomial-time algorithm for any fixed k, the proof is highly theoretical and leads to algorithms with enormous constant factors, making them unusable in practice. This paper aims to provide a more practical, efficient, and conceptually simpler algorithm for this problem.
Methods
The paper introduces a two-phase algorithm:
Phase I: Graph Compression This phase iteratively reduces the input graph. It relies on two key ideas:
- Finding Grid Minors: Leveraging results that connect high treewidth to the presence of large grid minors (specifically hexagonal grids). The algorithm uses a procedure (based on Theorem 3 and Lemma 1) to either find a tree decomposition of bounded width or a hexagonal grid subdivision.
- Reduction Techniques:
- Flat Zones (Reduction A): Identifying and removing "flat zones" within the hexagonal grid structure. These zones are carefully defined subgraphs that, if planar after removing certain components, allow for the removal of their associated grid components without affecting the overall k-APEX solvability (Lemma 2).
- Well-Attached Vertices (Reduction B): Identifying and removing "well-attached" vertices. These are vertices that, due to their connectivity to multiple disjoint blocks within the grid structure, must be part of any solution set X if one exists (Lemma 4). If no well-attached vertices are found, the algorithm guarantees the existence of a "flat zone" (Lemma 7).
This phase either concludes that no solution exists or produces a smaller graph G' with a tree decomposition of bounded treewidth, along with a set W of vertices that must be deleted.
Phase II: Bounded Treewidth Solvers Once Phase I has reduced the problem to a graph G' with bounded treewidth and a remaining budget of k' vertices to delete, Phase II employs advanced techniques:
- MSO Logic and Courcelle's Theorem: The planarity of G' after deleting k' vertices is expressed using a Monadic Second-Order Logic (MSO) formula. Courcelle's Theorem (and its strengthened version, Theorem 6) states that any graph property expressible in MSO can be decided in linear time on graphs with bounded treewidth.
- Apex Formula: The paper constructs an MSO formula,
apex(v1,...,vk'), that precisely captures the condition: "there exists a set of k' vertices {v1, ..., vk'} such that G' minus these vertices is planar." This formula leverages formulas for detecting K5 and K3,3 topological minors (Kuratowski's Theorem).
By applying Theorem 6 with this apex formula to G', the algorithm can efficiently determine if a solution exists and, if so, find the required set of vertices.
Datasets
Not discussed in the paper. The paper deals with theoretical algorithms on general graphs.
Key Insights and Ideas
- Bridging Theory and Practice: The paper demonstrates how deep theoretical results (Graph Minor Theorem, Courcelle's Theorem) can be combined with clever graph reduction techniques to yield practical algorithms for computationally hard problems.
- Iterative Reduction: The core idea of Phase I is to iteratively simplify the graph by removing structures that are either provably irrelevant to the k-APEX problem or must be part of any solution. This is a powerful strategy for tackling problems on graphs with complex structural properties.
- Hexagonal Grids as Building Blocks: The use of hexagonal grids as a structural element is key. Their properties, particularly in relation to subdivisions and topological minors, allow for precise local reductions.
- "Well-Attached" Vertices: The concept of "well-attached" vertices is a clever way to identify vertices that are "forced" into the deletion set, simplifying the problem incrementally.
- MSO for Graph Properties: The application of MSO logic and Courcelle's Theorem highlights the power of formal logic in solving graph problems, especially when combined with structural properties like bounded treewidth.
Key Results
- Quadratic Time Algorithm: The paper presents a new algorithm for the k-APEX problem with a running time of O(f(k)n²), where n is the number of vertices and f(k) is a function depending only on k. This is a significant improvement over the cubic-time algorithms implied by existing theory, especially for practical purposes.
- Simpler Algorithm: The authors emphasize that their algorithm is conceptually simpler than those derived directly from the Graph Minor Theorem.
- Explicit Construction: Unlike proofs relying on the non-constructive aspects of the Graph Minor Theorem, this algorithm provides an explicit computational procedure.
Limitations and Future Work
- Function of k: The running time is parameterized by k, meaning the f(k) term can still be substantial. While quadratic in n, the dependence on k might still be high.
- Constant Factors: While the paper aims for a simpler and more practical algorithm, the exact constant factors in the O(f(k)n²) complexity are not explicitly detailed but are implied to be much smaller than those from purely minor-theoretic approaches.
- Future Work: The paper mentions that Phase II could also be implemented using dynamic programming on the tree decomposition, which would yield a linear-time algorithm in n but with a double exponential dependence on k. This suggests further avenues for optimizing the k dependence. The paper also notes that the problem of finding a maximum induced planar subgraph is NP-complete, hinting at the inherent difficulty of related problems.
Summary updated