Modification problems toward proper (Helly) circular-arc graphs

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. [Computer Science Review 2023]. Our structural study also implies parameterized algorithms for modification problems toward proper Helly circular-arc graphs.

Authors

• Yixin Cao
• Hanchun Yuan
• Jianxin Wang

Keywords

No keywords are indexed for this paper.