×

Chordal editing is fixed-parameter tractable. (English) Zbl 1344.68095

Summary: Graph modification problems typically ask for a small set of operations that transforms a given graph to have a certain property. The most commonly considered operations include vertex deletion, edge deletion, and edge addition; for the same property, one can define significantly different versions by allowing different operations. We study a very general graph modification problem that allows all three types of operations: given a graph \(G\) and integers \(k_1\), \(k_2\), and \(k_3\), the chordal editing problem asks whether \(G\) can be transformed into a chordal graph by at most \(k_1\) vertex deletions, \(k_2\) edge deletions, and \(k_3\) edge additions. Clearly, this problem generalizes both chordal deletion and chordal completion (also known as minimum fill-in). Our main result is an algorithm for chordal editing in time \(2^{O(k\log k)}\cdot n^{O(1)}\), where \(k:=k_1+k_2+k_3\) and \(n\) is the number of vertices of \(G\). Therefore, the problem is fixed-parameter tractable parameterized by the total number of allowed operations. Our algorithm is both more efficient and conceptually simpler than the previously known algorithm for the special case chordal deletion.

MSC:

68Q25 Analysis of algorithms and problem complexity
05C85 Graph algorithms (graph-theoretic aspects)

References:

[1] Balas, E., Yu, C.S.: Finding a maximum clique in an arbitrary graph. SIAM J. Comput. 15(4), 1054-1068 (1986). doi:10.1137/0215075 · Zbl 0604.05024 · doi:10.1137/0215075
[2] Berge, C.; Harary, F. (ed.), Some classes of perfect graphs, 155-166 (1967), New York · Zbl 0203.26403
[3] Berge, C.: Motivations and history of some of my conjectures. Discrete Math. 165-166, 61-70 (1997). doi:10.1016/S0012-365X(96)00161-6 · Zbl 0873.05066 · doi:10.1016/S0012-365X(96)00161-6
[4] Cai, L.: Fixed-parameter tractability of graph modification problems for hereditary properties. Inf. Process. Lett. 58(4), 171-176 (1996). doi:10.1016/0020-0190(96)00050-6 · Zbl 0875.68702 · doi:10.1016/0020-0190(96)00050-6
[5] Cai, L.: Parameterized complexity of vertex colouring. Discrete Appl. Math. 127(3), 415-429 (2003). doi:10.1016/S0166-218X(02)00242-1 · Zbl 1015.05027 · doi:10.1016/S0166-218X(02)00242-1
[6] Cao, Y.: Unit interval editing is fixed-parameter tractable. In: Automata, Languages and Programming (ICALP), vol. 9134, pp. 306-317. Springer (2015). doi:10.1007/978-3-662-47672-7_25 · Zbl 1440.68135
[7] Cao, Y., Chen, J., Liu, Y.: On feedback vertex set: new measure and new structures. Algorithmica (2014). doi:10.1007/s00453-014-9904-6 · Zbl 1285.68061
[8] Dearing, P.M., Shier, D.R., Warner, D.D.: Maximal chordal subgraphs. Discrete Appl. Math. 20(3), 181-190 (1988). doi:10.1016/0166-218X(88)90075-3 · Zbl 0664.05032 · doi:10.1016/0166-218X(88)90075-3
[9] Dirac, G.A.: On rigid circuit graphs. Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg 25(1), 71-76 (1961). doi:10.1007/BF02992776 · Zbl 0098.14703 · doi:10.1007/BF02992776
[10] Downey, R.G., Fellows, M.R.: Fundamentals of parameterized complexity. Undegrad. Texts Comput. Sci. (2013). doi:10.1007/978-1-4471-5559-1 · Zbl 1358.68006
[11] Erdős, P., Pósa, L.: On the maximal number of disjoint circuits of a graph. Publicationes Mathematicae Debrecen 9, 3-12 (1962) · Zbl 0133.16701
[12] Hajnal, A., Surányi, J.: Über die auflösung von graphen in vollständige teilgraphen. Annales Universitatis Scientarium Budapestinensis de Rolando Eötvös Nominatae Sectio Mathematica 1, 113-121 (1958) · Zbl 0093.37801
[13] 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. A preliminary version appeared in FOCS 1994 (1999). doi:10.1137/S0097539796303044 · Zbl 0928.68124
[14] Krishnamoorthy, M.S., Deo, N.: Node-deletion NP-complete problems. SIAM J. Comput. 8(4), 619-625 (1979). doi:10.1137/0208049 · Zbl 0423.05039 · doi:10.1137/0208049
[15] Lewis, J.G., Peyton, B.W., Pothen, A.: A fast algorithm for reordering sparse matrices for parallel factorization. SIAM J. Sci. Stat. Comput. 10(6), 1146-1173 (1989). doi:10.1137/0910070 · Zbl 0693.65032 · doi:10.1137/0910070
[16] Lewis, J.M., Yannakakis, M.: The node-deletion problem for hereditary properties is NP-complete. J. Comput. Syst. Sci. 20(2), 219-230. Preliminary versions independently presented in STOC 1978 (1980). doi:10.1016/0022-0000(80)90060-4 · Zbl 0436.68029
[17] Mancini, F.: Graph Modification problems related to graph classes. Ph.D. thesis, University of Bergen, Bergen (2008) · Zbl 0604.05024
[18] Marx, D.: Parameterized coloring problems on chordal graphs. Theor. Comput. Sci. 351(3), 407-424 (2006). doi:10.1016/j.tcs.2005.10.008 · Zbl 1087.68072 · doi:10.1016/j.tcs.2005.10.008
[19] Marx, D.: Chordal deletion is fixed-parameter tractable. Algorithmica 57(4), 747-768 (2010). doi:10.1007/s00453-008-9233-8 · Zbl 1220.05066 · doi:10.1007/s00453-008-9233-8
[20] Marx, D., O’Sullivan, B., Razgon, I.: Finding small separators in linear time via treewidth reduction. ACM Trans. Algorithms 9(4), 30.1-30.35. A preliminary version appeared in STACS 2010 (2013). doi:10.1145/2500119 · Zbl 1301.05337
[21] Natanzon, A., Shamir, R., Sharan, R.: Complexity classification of some edge modification problems. Discrete Appl. Math. 113(1), 109-128. A preliminary version appeared in WG 1999 (2001). doi:10.1016/S0166-218X(00)00391-7 · Zbl 0982.68104
[22] Reed, B.A., Smith, K., Vetta, A.: Finding odd cycle transversals. Oper. Res. Lett. 32(4), 299-301 (2004). doi:10.1016/j.orl.2003.10.009 · Zbl 1052.05061 · doi:10.1016/j.orl.2003.10.009
[23] Rose, D.J.: Triangulated graphs and the elimination process. J. Math. Anal. Appl. 32(3), 597-609 (1970). doi:10.1016/0022-247X(70)90282-9 · Zbl 0216.02602 · doi:10.1016/0022-247X(70)90282-9
[24] Rose, DJ; Reed, RC (ed.), A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations, 183-217 (1973), New York · Zbl 0266.65028
[25] Xue, J.: Edge-maximal triangulated subgraphs and heuristics for the maximum clique problem. Networks 24(2), 109-120 (1994). doi:10.1002/net.3230240208 · Zbl 0791.90065 · doi:10.1002/net.3230240208
[26] Yannakakis, M.: Computing the minimum fill-in is NP-complete. SIAM J. Algebraic Discrete Methods 2(1), 77-79 (1981). doi:10.1137/0602010 · Zbl 0496.68033 · doi:10.1137/0602010
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.