2012/11/19 by Arash Rafiey, Rafiey, Arash
Computer Science · #Advanced Graph Theory Research #Algorithms and Data Compression #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.1211.4629
openalex publication_date 2012/11/19 · openalex created_date 2022/09/04 · openalex updated_date 2026/07/28
Let G be an input graph with n vertices and m edges and let k be a fixed\nparameter. We provide a single exponential FPT algorithm with running time\nO(ckn(n+m)), c= min 18,k that turns graph G into an interval graph by\ndeleting at most k vertices from G. This solves an open problem posed by D.Marx\n[19]. We also provide a single exponential FPT algorithm with running time\nO(ckn(n+m)), c= min 17,k that turns G into an interval graph by adding at\nmostk edges. The first FPT algorithm with run time O(k2kn3m) appeared in\nSTOC 2007 [24]. Our algorithm is the the first single exponential FPT algorithm\nthat improves the running time of the previous algorithm. The algorithms are\nbased on a structural decomposition of G into smaller subgraphs when G is free\nfrom small interval graph obstructions. The decomposition allows us to manage\nthe search tree more efficiently.\n