Abstract
It is known to be NP-hard to decide whether a graph can be made chordal by the deletion of k vertices or by the deletion of k edges. Here we present a uniformly polynomial-time algorithm for both problems: the running time is f(k)⋅n α for some constant α not depending on k and some f depending only on k. For large values of n, such an algorithm is much better than trying all the O(n k) possibilities. Therefore, the chordal deletion problem parameterized by the number k of vertices or edges to be deleted is fixed-parameter tractable. This answers an open question of Cai (Discrete Appl. Math. 127:415–429, 2003).
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Adler, I., Grohe, M., Kreutzer, S.: Computing excluded minors. In: SODA ’08: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 641–650. Society for Industrial and Applied Mathematics, Philadelphia (2008)
Bodlaender, H.L.: A tourist guide through treewidth. Acta Cybern. 11(1–2), 1–21 (1993)
Cai, L.: Fixed-parameter tractability of graph modification problems for hereditary properties. Inf. Process. Lett. 58(4), 171–176 (1996)
Cai, L.: Parameterized complexity of vertex colouring. Discrete Appl. Math. 127, 415–429 (2003)
Courcelle, B.: Graph rewriting: an algebraic and logic approach. In: Handbook of Theoretical Computer Science, vol. B, pp. 193–242. Elsevier, Amsterdam (1990)
Dehne, F., Fellows, M., Langston, M., Rosamond, F., Stevens, K.: An O(2O(k) n 3) FPT algorithm for the undirected feedback vertex set problem. Theory Comput. Syst. 41(3), 479–492 (2007)
Dom, M., Guo, J., Hüffner, F., Niedermeier, R., Truß, A.: Fixed-parameter tractability results for feedback set problems in tournaments. In: Algorithms and Complexity. Lecture Notes in Computer Science, vol. 3998, pp. 320–331. Springer, Berlin (2006)
Downey, R.G., Fellows, M.R.: Parameterized Complexity. Monographs in Computer Science. Springer, New York (1999)
Flum, J., Grohe, M.: Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, Berlin (2006)
Gallai, T.: Maximum-minimum Sätze und verallgemeinerte Faktoren von Graphen. Acta Math. Acad. Sci. Hung. 12, 131–173 (1961)
Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980)
Grohe, M.: Computing crossing numbers in quadratic time. J. Comput. Syst. Sci. 68(2), 285–302 (2004)
Guo, J., Gramm, J., Hüffner, F., Niedermeier, R., Wernicke, S.: Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization. J. Comput. Syst. Sci. 72(8), 1386–1396 (2006)
Heggernes, P., Paul, C., Telle, J.A., Villanger, Y.: Interval completion with few edges. In: STOC ’07: Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, pp. 374–381. ACM, New York (2007)
Ho, M.L.: Linear time algorithms for graphs close to chordal graphs. M. Phil. Thesis, Department of Computer Science and Engineering, The Chinese University of Hong Kong (2003)
Kaplan, H., Shamir, R., Tarjan, R.E.: Tractability of parameterized completion problems on chordal, strongly chordal, and proper interval graphs. SIAM J. Comput. 28(5), 1906–1922 (1999)
Kleinberg, J.: Detecting a network failure. Internet Math. 1(1), 37–55 (2003)
Kloks, T.: Treewidth. Lecture Notes in Computer Science, vol. 842. Springer, Berlin (1994)
Lewis, J.M., Yannakakis, M.: The node-deletion problem for hereditary properties is NP-complete. J. Comput. Syst. Sci. 20(2), 219–230 (1980)
Lokshtanov, D.: Wheel-free deletion is W[2]-hard. In: Proceedings of the International Workshop on Parameterized and Exact Computation (IWPEC 2008). Lecture Notes in Computer Science, vol. 5018, pp. 141–147. Springer, Berlin (2008)
Marx, D.: Parameterized coloring problems on chordal graphs. Theor. Comput. Sci. 351(3), 407–424 (2006)
Marx, D., Schlotter, I.: Obtaining a planar graph by vertex deletion. In: 33rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2007). Lecture Notes in Computer Science, vol. 4769, pp. 292–303. Springer, Berlin (2007)
Natanzon, A., Shamir, R., Sharan, R.: Complexity classification of some edge modification problems. Discrete Appl. Math. 113(1), 109–128 (2001)
Reed, B., Smith, K., Vetta, A.: Finding odd cycle transversals. Oper. Res. Lett. 32(4), 299–301 (2004)
Robertson, N., Seymour, P.D.: Graph minors, XIII: the disjoint paths problem. J. Comb. Theory Ser. B 63(1), 65–110 (1995)
Rose, D.J., Tarjan, R.E., Lueker, G.S.: Algorithmic aspects of vertex elimination on graphs. SIAM J. Comput. 5(2), 266–283 (1976)
Yannakakis, M.: Computing the minimum fill-in is NP-complete. SIAM J. Algebr. Discrete Methods 2(1), 77–79 (1981)
Author information
Authors and Affiliations
Corresponding author
Additional information
Research is supported by the Magyary Zoltán Felsőoktatási Közalapítvány and the Hungarian National Research Fund (OTKA grant 67651).
Rights and permissions
About this article
Cite this article
Marx, D. Chordal Deletion is Fixed-Parameter Tractable. Algorithmica 57, 747–768 (2010). https://doi.org/10.1007/s00453-008-9233-8
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-008-9233-8