Unit interval editing is fixed-parameter tractable

Given a graph G and integers k 1, k 2, and k 3, the unit interval editing problem asks whether G can be transformed into a unit interval graph by at most k 1 vertex deletions, k 2 edge deletions, and k 3 edge additions. We give an algorithm solving this problem in time 2 O ( k log ⁡ k ) ⋅ ( n + m ), where k: = k 1 + k 2 + k 3, and n, m denote respectively the numbers of vertices and edges of G. Therefore, it is fixed-parameter tractable parameterized by the total number of allowed operations. Our algorithm implies the fixed-parameter tractability of the unit interval edge deletion problem, for which we also present a more efficient algorithm running in time O ( 4 k ⋅ ( n + m ) ). Another result is an O ( 6 k ⋅ ( n + m ) ) -time algorithm for the unit interval vertex deletion problem, significantly improving the algorithm of van 't Hof and Villanger, which runs in time O ( 6 k ⋅ n 6 ).

Authors

• Yixin Cao

Keywords

• Graph modification problem
• Forbidden induced subgraph
• Proper Helly circular-arc graph
• (Proper, unit) interval model
• (Proper, Helly) arc model
• Certifying algorithm