Fixed-Treewidth-Efficient Algorithms for Edge-Deletion to Interval Graph Classes
Publication date
2021-01-31
Authors
Saitoh, Toshiki
Yoshinaka, Ryo
Bodlaender, H.L.
Editors
Uehara, Ryuhei
Hong, Seok-Hee
Nandy, Subhas C.
Advisors
Supervisors
Document Type
Part of book
Metadata
Show full item recordCollections
License
taverne
Abstract
For a graph class C, the C -Edge-Deletion problem asks for a given graph G to delete the minimum number of edges from G in order to obtain a graph in C. We study the C -Edge-Deletion problem for C the class of interval graphs and other related graph classes. It follows from Courcelle’s Theorem that these problems are fixed parameter tractable when parameterized by treewidth. In this paper, we present concrete FPT algorithms for these problems. By giving explicit algorithms and analyzing these in detail, we obtain algorithms that are significantly faster than the algorithms obtained by using Courcelle’s theorem.
Keywords
Edge-Deletion, Interval graphs, Parameterized algorithms, Treewidth, Taverne, Theoretical Computer Science, General Computer Science
Citation
Saitoh, T, Yoshinaka, R & Bodlaender, H L 2021, Fixed-Treewidth-Efficient Algorithms for Edge-Deletion to Interval Graph Classes. in R Uehara, S-H Hong & S C Nandy (eds), WALCOM: Algorithms and Computation : 15th International Conference and Workshops, WALCOM 2021, Yangon, Myanmar, February 28 – March 2, 2021, Proceedings. 1 edn, Lecture Notes in Computer Science , vol. 12635 , Springer, Cham, pp. 142-153, 15th International Conference on Algorithms and Computation, WALCOM 2021, Virtual, Online, 28/02/21. https://doi.org/10.1007/978-3-030-68211-8_12, conference