zbMATH — the first resource for mathematics

Fixed-parameter tractability of graph modification problems for hereditary properties. (English) Zbl 0875.68702
Summary: This paper is concerned with the fixed-parameter tractability of the problem of deciding whether a graph can be made into a graph with a specified hereditary property by deleting at most i vertices, at most j edges, and adding at most k edges, where i,j,k are fixed integers. It is shown that this problem is fixed-parameter tractable whenever the hereditary property can be characterized by a finite set of forbidden induced subgraphs. Furthermore, the problem of deciding whether a graph can be made into a chordal graph by adding a fixed number k of edges is shown to be solvable in O\((4^{k}(k+1)^{-3/2}(m+n))\) time, and is thus fixed-parameter tractable.

68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI
[1] Beineke, L.W., On derived graphs and digraphs, (), 17-33 · Zbl 0179.29204
[2] Cormen, T.H.; Leiserson, C.E.; Rivest, R.L., Introduction to algorithms, (1990), MIT Press Cambridge, MA · Zbl 1158.68538
[3] Corneil, D.G.; Lerchs, H.; Burlingham, L.S., Complement reducible graphs, Discrete appl. math., 3, 163-174, (1981) · Zbl 0463.05057
[4] R.G. Downey and M.R. Fellows, Parameterized complexity, Monograph in preparation.
[5] Downey, R.G.; Fellows, M.R., Fixed-parameter intractability, (), 36-49
[6] Downey, R.G.; Fellows, M.R., Fixed parameter tractability and completeness, (), 36-49 · Zbl 0768.68136
[7] Födes, S.; Hammer, P.L., Split graphs, (), 36-49
[8] Garey, M.R.; Johnson, D.S., Computers and intractability: A guide to the theory of NP-completeness, (1979), Freeman San Francisco · Zbl 0411.68039
[9] Kaplan, H.; Shamir, R.; Tarjan, R.E., Tractability of parameterized completion problems on chordal and interval graphs: minimum fill-in and physical mapping (extended abstract), (), 36-49
[10] Krishnamoorthy, M.S.; Narsingh, D., Node-deletion NP-complete problems, SIAM J. comput., 8, 619-625, (1979) · Zbl 0423.05039
[11] Lewis, J.M., On the complexity of the maximum subgraph problem, (), 265-274 · Zbl 1282.68124
[12] Rose, D.; Tarjan, R.; Lueker, G., Algorithmic aspects of vertex elimination on graphs, SIAM J. comput., 5, 266-283, (1976) · Zbl 0353.65019
[13] Ruskey, F.; Proskurowski, A., Generating binary trees by transpositions, J. algorithms, 11, 266-283, (1990) · Zbl 0709.05016
[14] Tarjan, R.; Yannakakis, M., Addendum: simple lineartime algorithms to test chordality of graphs, text acyclicity of hypergraphs and selectively reduce acyclic hypergraphs, SIAM J. comput., 14, 254-255, (1985) · Zbl 0562.68055
[15] Yannakakis, M., Node- and edge-deletion NP-complete problems, (), 253-264 · Zbl 1282.68131
[16] Yannakakis, M., Computing the minimum fill-in is NP-complete, SIAM J. algebraic discrete methods, 2, 77-79, (1981) · Zbl 0496.68033
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.