TY - GEN
T1 - Unit interval editing is fixed-parameter tractable
AU - Cao, Yixin
PY - 2015/1/1
Y1 - 2015/1/1
N2 - Given a graph G and integers k1, k2, and k3, the unit interval editing problem asks whether G can be transformed into a unit interval graph by at most k1 vertex deletions, k2 edge deletions, and k3 edge additions. We give an algorithm solving the problem in 2O(klogk) ·(n+m) time, where k:= k1 +k2 +k3, 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. This 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(4k · (n + m)). Another result is an O(6k · (n + m))-time algorithm for the unit interval vertex deletion problem, significantly improving the best-known algorithm running in time O(6k · n6).
AB - Given a graph G and integers k1, k2, and k3, the unit interval editing problem asks whether G can be transformed into a unit interval graph by at most k1 vertex deletions, k2 edge deletions, and k3 edge additions. We give an algorithm solving the problem in 2O(klogk) ·(n+m) time, where k:= k1 +k2 +k3, 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. This 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(4k · (n + m)). Another result is an O(6k · (n + m))-time algorithm for the unit interval vertex deletion problem, significantly improving the best-known algorithm running in time O(6k · n6).
UR - http://www.scopus.com/inward/record.url?scp=84950134089&partnerID=8YFLogxK
U2 - 10.1007/978-3-662-47672-7_25
DO - 10.1007/978-3-662-47672-7_25
M3 - Conference article published in proceeding or book
SN - 9783662476710
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 306
EP - 317
BT - Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Proceedings
PB - Springer Verlag
T2 - 42nd International Colloquium on Automata, Languages and Programming, ICALP 2015
Y2 - 6 July 2015 through 10 July 2015
ER -