A polynomial delay algorithm generating all potential maximal cliques in triconnected planar graphs

Basic Information

• Paper ID: 2506.12635
• Title: A polynomial delay algorithm generating all potential maximal cliques in triconnected planar graphs
• Authors: Alexander Grigoriev, Yasuaki Kobayashi, Hisao Tamaki, Tom C. van der Zanden
• Classification: cs.DS (Data Structures and Algorithms)
• Publication Time/Conference: IPEC 2025 (20th International Symposium on Parameterized and Exact Computation)
• Paper Link: https://arxiv.org/abs/2506.12635

Abstract

This paper develops a novel characterization method for the Potential Maximal Cliques (PMC) problem in triconnected planar graphs and proposes a polynomial delay algorithm based on this characterization to generate all potential maximal cliques of a given triconnected planar graph. Combined with the dynamic programming algorithm of Bouchitté and Todinca, this algorithm provides a treewidth computation algorithm for general planar graphs with running time linear in the number of potential maximal cliques and polynomial in the number of vertices.

Research Background and Motivation

Problem Importance

1. Core Problem in Treewidth Computation: The computation of Potential Maximal Cliques (PMC) is the first step of the Bouchitté-Todinca treewidth algorithm, which computes the treewidth of graph G through dynamic programming in the second step with time complexity |Π(G)|n^O(1).
2. Open Problem: Whether Π(G) can be computed in time |Π(G)|n^O(1) is an important open problem in parameterized and exact computation. Prior to this work, except for graph classes where Π(G) is known to be computable in polynomial time, this problem remained unsolved for any natural graph class.
3. Role of Planarity: For branchwidth, the utility of planarity is clear (Ratcatcher algorithm), but for treewidth, whether treewidth computation on planar graphs is NP-hard or polynomial-time solvable has been a long-standing open question.

Limitations of Existing Methods

• Bouchitté and Todinca proved that Π(G) can be computed in polynomial time with respect to the number of minimal separators
• Fomin and Villanger provided an upper bound of O(1.7549^n) and corresponding algorithm
• Although theoretical bounds exist, algorithms requiring |Π(G)|n^O(1) time are more practical for real applications

Core Contributions

1. Novel PMC Characterization: Proposes a simple characterization of PMC in triconnected planar graphs based on "steering" graphs
2. Polynomial Delay Algorithm: Designs the first polynomial delay algorithm for generating all PMCs in triconnected planar graphs
3. Introduction of Latching Graphs: Introduces the concept of latching graphs as a new tool for handling triconnected planar graphs, replacing traditional radial graphs and noose methods
4. Improved Treewidth Algorithm: Provides a treewidth computation algorithm for general planar graphs with running time |Π(G)|n^O(1)
5. First Explicit Use of Planarity: This is the first algorithm to explicitly exploit planarity in a non-trivial manner for exact treewidth computation

Methodology Details

Task Definition

Input: Triconnected planar graph G Output: All potential maximal cliques Π(G) of G Constraint: The algorithm must satisfy polynomial delay generation, i.e., the time between consecutive outputs is n^O(1)

Core Concepts

Latching Graphs

For a biconnected planar graph G, its latching graph L_G is a multigraph obtained by adding all chords of the boundary cycle of each face in G.

Key Properties:

• For triconnected planar graphs, the latching graph is a simple graph (Proposition 6)
• L_GX is a planar graph if and only if there does not exist a face f such that |V(f)∩X|≥4 (Proposition 7)

Steering Graph Characterization

Definition 13: A graph H is a steering graph if there exists a bipartition (S,P) of the vertex set such that:

• HS is a cycle
• N_H(P) is neither empty nor a slot of HS
• If |P|≥2, additional conditions are satisfied (path structure, connectivity constraints, etc.)

Main Theorem (Theorem 21): A vertex set X of a triconnected planar graph G is a PMC if and only if L_GX is a steering graph.

Algorithm Architecture

Generation Algorithm Structure

1. Classified Generation:
   • Generate all PMCs X for which there exists C∈C_G(X) with |N_G(C)|=3 (corresponding to K_4)
   • Generate PMCs X for which there exists C∈C_G(X) with |N_G(C)|≥4
2. Generation Based on Minimal Separators:
   • For each minimal separator S, generate related PMCs
   • Use the concept of arches to construct steering graphs
3. Avoiding Duplicate Output: Employs techniques from Bergougnoux et al. (Theorem 27) to handle duplicate generation

Key Algorithm Components

Arch Concept (Definition 18): For a minimal separator S, an arch P is a subset of V(G)\S such that:

• L_GP is a path
• N_(P)∩S is neither empty nor a slot of L_GS

Generation Process:

1. Generate all minimal separators (using chordless cycle generation)
2. For each separator, find corresponding arches
3. Construct PMCs using chordless path generation algorithm
4. Apply duplicate suppression techniques to ensure polynomial delay

Experimental Setup

Theoretical Analysis

This paper primarily conducts theoretical analysis, proving the correctness and polynomial delay properties of the algorithm, rather than experimental research.

Complexity Analysis

• Time Complexity: |Π(G)|n^O(1)
• Delay Complexity: n^O(1) (polynomial delay)
• Space Complexity: Polynomial space

Experimental Results

Theoretical Results

1. Correctness: Proves the sufficiency and necessity of the steering graph characterization
2. Completeness: The algorithm generates all PMCs without duplication
3. Efficiency: Satisfies polynomial delay requirements

Extension to General Planar Graphs

Theorem 34: For a planar graph G, treewidth tw(G) can be computed in time |Π(G)|n^O(1).

The proof uses induction based on decomposition by two-vertex separators, employing the Bodlaender-Koster theorem for handling almost clique separators.

Related Work

PMC Computation

• Pioneering work by Bouchitté-Todinca established the connection between PMC and treewidth computation
• Fomin-Villanger provided exponential-time algorithms and combinatorial bounds for general graphs

Planar Graph Algorithms

• The Ratcatcher algorithm for branchwidth demonstrates the utility of planarity in related problems
• Existing treewidth approximation algorithms (such as 1.5-approximation) exploit planarity, but no exact algorithms existed

Enumeration Algorithms

• Polynomial delay generation is an important research goal in combinatorial enumeration
• Uno-Satoh's chordless cycle and path generation algorithms provide the foundation for this work

Conclusions and Discussion

Main Conclusions

1. First solves the problem of computing PMC in time |Π(G)|n^O(1) for a specific graph class (triconnected planar graphs)
2. Provides the first exact treewidth algorithm that explicitly exploits planarity
3. Introduces latching graphs as an effective tool for handling triconnected planar graphs

Limitations

1. Graph Class Restrictions: The method is specifically designed for triconnected planar graphs; extension to general planar graphs requires additional techniques
2. Latching Graph Limitations: For non-triconnected graphs, latching graphs may not be simple graphs, limiting method applicability
3. Theory vs. Practice: Although theoretically elegant, actual performance remains to be verified

Future Directions

1. Extension to General Planar Graphs: Seek methods for handling PMCs that span two-vertex minimal separators
2. Other Surfaces: Extend to graphs on other surfaces such as tori (authors note that the latching graph method does not apply)
3. Improved Bounds: Investigate tighter bounds on |Π(G)| for triconnected planar graphs
4. Practical Algorithms: Develop practical implementations and conduct performance evaluation

In-Depth Evaluation

Strengths

1. Theoretical Innovation: The steering graph characterization is elegant and simple, avoiding the complexity of traditional noose and radial graphs
2. Technical Contribution: The latching graph concept provides a new tool for analyzing triconnected planar graphs
3. Problem Resolution: First solves an important open problem on a natural graph class
4. Algorithm Design: Polynomial delay generation techniques are cleverly applied, with effective handling of duplicate output

Weaknesses

1. Limited Applicability: Restricted to triconnected planar graphs; general planar graphs still require complex inductive treatment
2. Unknown Practical Utility: Lacks actual implementation and performance testing
3. Constant Factors: Constants in polynomial delay may be large, affecting practical efficiency

Impact

1. Theoretical Significance: Provides partial resolution to a long-standing open problem, advancing parameterized algorithm theory
2. Methodological Contribution: The latching graph method may inspire other planar graph algorithms
3. Practical Potential: Provides new theoretical foundation for planar graph treewidth computation

Applicable Scenarios

• Planar graph analysis in circuit design
• Planar network optimization in geographic information systems
• Problems requiring tree decomposition in computational geometry
• Theoretical analysis tools in graph theory research

References

The paper cites 22 important references, primarily including:

• Foundational work by Bouchitté & Todinca on PMC and treewidth
• Classical results in planar graph algorithms (such as Seymour-Thomas's Ratcatcher algorithm)
• Polynomial delay techniques in combinatorial enumeration
• Foundational theory of graph triconnectivity and planar embeddings

This paper makes important contributions to theoretical computer science. Although its scope of application is limited, its methodological innovations and problem-solving approach have significant academic value, providing new insights and tools for the development of planar graph algorithms and parameterized complexity theory.