Modification Problems toward Proper (Helly) Circular-arc Graphs

Yixin Cao, Jianxin Wang, Hanchun Yuan

Abstract

This paper presents the first fixed-parameter tractable (FPT) algorithm for the proper circular-arc vertex deletion problem, resolving a long-standing open question in graph theory. By exploring the structural relationships between proper circular-arc (PCA) graphs, their complements, and bipartite permutation graphs, the authors also develop efficient modification algorithms for the proper Helly circular-arc (PHCA) class.

Introduction

Modification problems are a cornerstone of graph theory, asking how many operations—such as vertex deletion, edge deletion, or edge addition—are required to transform an arbitrary graph into a member of a specific target class. This paper focuses on two significant classes: Proper Circular-arc (PCA) graphs and Proper Helly Circular-arc (PHCA) graphs.

PCA graphs represent vertices as arcs on a circle where no arc is contained within another. PHCA graphs are a subclass that satisfies the "Helly property": if a set of arcs pairwise intersect, they must all share at least one common point. While modification problems for interval graphs (arcs on a line) are well-understood, the circular topology introduces significant complexity that had left the PCA vertex deletion problem open for nearly a decade.

Visualizing PCA and PHCA graphs through arc representations.

Methodology

The authors employ a "branch-and-reduce" strategy rooted in structural graph theory. The core of the algorithm involves identifying small forbidden induced subgraphs—specific structures known to be illegal in the target class—and branching on which vertex or edge to remove to "break" these structures.

Forbidden induced subgraphs used in the branching algorithm.

Beyond simple branching, the paper introduces the concept of "reduced graphs"—graphs that are connected, co-connected, and free of small forbidden subgraphs. A key structural lemma proven by the authors states that if a reduced graph contains a long even hole (a cycle of length $\ge 8$), it must be bipartite. This allows the authors to bridge PCA graph theory with the study of bipartite permutation graphs, significantly simplifying the computational search space.

Key Insights

A major "aha moment" in the research is the Bipartite Bridge: the realization that once small forbidden subgraphs are handled, the remaining difficulty in PCA graphs is tied directly to the structure of bipartite permutation graphs via the graph's complement.

The paper also highlights the unique topological constraints of circular graphs. Unlike interval graphs, which are closed under disjoint unions, a disconnected PCA graph is essentially forced to be a proper interval graph. Interestingly, while the Helly property adds a constraint, it actually makes modification problems more tractable algorithmically by limiting how maximal cliques overlap, enabling linear-time recognition.

Results and Complexity

The headline result is the first FPT algorithm for Proper Circular-arc Vertex Deletion, achieving a time complexity of $9^k \cdot n^{O(1)}$, where $k$ is the number of deletions. The paper also provides a suite of algorithms for PHCA modifications:

  • PHCA Vertex Deletion: $O(6^k \cdot (m + n))$
  • PHCA Edge Deletion: $O(8^k \cdot (m + n))$
  • PHCA Edge Completion: $k^{O(k)} \cdot (m + n)$

Additionally, the authors establish polynomial-time approximation algorithms with ratios of 9 for PCA vertex deletion and 6 for PHCA vertex deletion.

Conclusion and Future Work

While this work successfully resolves the PCA vertex deletion problem, the editing problem (simultaneous edge additions and deletions) for PHCA graphs remains a conjecture. The current dynamic programming approaches for edge completion do not easily extend to editing because edge deletions can disrupt the connectivity required for the "attachment" logic. Future research will likely focus on closing this gap and refining the constant factors of the FPT algorithms to improve their practical applicability.

Summary updated

BibTeX
@inproceedings{cao2023modification,
  author = {Yixin Cao and Jianxin Wang and Hanchun Yuan},
  title = {{Modification Problems toward Proper (Helly) Circular-arc Graphs}},
  booktitle = {MFCS},
  year = {2023},
  doi = {10.4230/lipics.mfcs.2023.31},
}
Figure