Modification Problems toward Proper (Helly) Circular-arc Graphs

2022/02/02 by Cao, Yixin, Wang, Jianxin, Yuan, Hanchun
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2202.00854

Abstract

We present a 9^k⋅ n^O(1)-time algorithm for the proper circular-arc vertex deletion problem, resolving an open problem of van 't Hof and Villanger [Algorithmica 2013] and Crespelle et al. [arXiv:2001.06867]. Our structural study also implies parameterized algorithms for modification problems toward proper Helly circular-arc graphs.

Related

• A Polynomial Kernel for Proper Helly Circular-arc Vertex Deletion
• A certifying and dynamic algorithm for the recognition of proper\n circular-arc graphs
• Forbidden Induced Subgraphs of Normal Helly Circular-Arc Graphs: Characterization and Detection
• Extending Partial Representations of Circular-Arc Graphs
• Circular-arc graphs and the Helly property