Forbidden structure characterization of circular-arc graphs and a certifying recognition algorithm

DOI10.1137/1.9781611973730.114MaRDI QIDQ5363059zbMATH OpenOpenAlexFDO

Authors Mathew C. Francis, Juraj Stacho, Pavol Hell

Publication date 5 October 2017

Published in Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1408.2639

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Structural characterization of families of graphs (05C75)

Abstract: A circular-arc graph is the intersection graph of arcs of a circle. It is a well-studied graph model with numerous natural applications. A certifying algorithm is an algorithm that outputs a certificate, along with its answer (be it positive or negative), where the certificate can be used to easily justify the given answer. While the recognition of circular-arc graphs has been known to be polynomial since the 1980s, no polynomial-time certifying recognition algorithm is known to date, despite such algorithms being found for many subclasses of circular-arc graphs. This is largely due to the fact that a forbidden structure characterization of circular-arc graphs is not known, even though the problem has been intensely studied since the seminal work of Klee in the 1960s. In this contribution, we settle this problem. We present the first forbidden structure characterization of circular-arc graphs. Our obstruction has the form of mutually avoiding walks in the graph. It naturally extends a similar obstruction that characterizes interval graphs. As a consequence, we give the first polynomial-time certifying algorithm for the recognition of circular-arc graphs.

Recommendations

• Linear-time recognition of circular-arc graphs
• Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs
• Certifying Algorithms for Recognizing Proper Circular-Arc Graphs and Unit Circular-Arc Graphs
• Characterizations and Linear Time Recognition of Helly Circular-Arc Graphs
• Linear-time recognition of Helly circular-arc models and graphs

Cited in

(11)

• A linear-time certifying algorithm for recognizing generalized series-parallel graphs
• Certifying Algorithms for Recognizing Proper Circular-Arc Graphs and Unit Circular-Arc Graphs
• Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs
• An efficient certifying algorithm for the Hamiltonian cycle problem on circular-arc graphs
• Essential obstacles to Helly circular-arc graphs
• Isometric path complexity of graphs
• Certifying induced subgraphs in large graphs
• Forbidden induced subgraphs of normal Helly circular-arc graphs: characterization and detection
• Strong Cocomparability Graphs and Slash-Free Orderings of Matrices
• On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid
• Characterising circular-arc contact \(B_0\)-VPG graphs

This page was built for publication: Forbidden structure characterization of circular-arc graphs and a certifying recognition algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5363059)