Here is the current status of exact, parameterized and kernelization complexities of Π edge modification problems. For a graph property Π, the Π edge modification problem is to check whether there exist at most k edges whose modification on the input graph results in a graph with property Π. The three types of edge modifications considered here are deletion, completion and editing. The parameter we consider is k. Explicit exact and parameterized lower bounds assume Exponential Time Hypothesis (ETH) and kernelization lower bounds assume NP ⊈ CoNP/poly. In the following tables a lower bound x means that the corresponding problem cannot be solved in time x.

Exact Lower Bounds and Algorithms

Π	Exact Lower Bounds			Exact Algorithms
Π	Deletion	Completion	Editing	Deletion	Completion	Editing
Bipartite	2^o(n+m) [Y81b]	See Algorithms	2^o(n+m) [Y81b]	Unknown	P [Trivial]	Unknown
Chordal	2^{O(n^1/4/log^cn)} [BCKMP16,NSS01]	2^{O(n^1-δ)} [CS17]	NP-hard [DDLS15]	Unknown	O(1.8899ⁿ) [FKTV08]	Unknown
Comparability	2^o(n+m) [Y81b]	2^O(n+m) [HSY97]	2^O(n) [NSS01]	Unknown	Unknown	Unknown
H-free	NP-hard [ASS16]	NP-hard [ASS16]	NP-hard [ASS16]	Unknown	Unknown	Unknown
Interval	2^o(√n+m) [GJT76,GGKS95]	2^{O(√n/log^cn)} [BCKMP16]	2^o(√n+m) [BBD06,GJT76]	Unknown	Unknown	Unknown
Line	2^o(n+m) [Y81b]	Unknown	Unknown	Unknown	Unknown	Unknown
Perfect	2^{O(n^1/8/log^cn)} [BCKMP16,NSS01]	2^{O(n^1/8/log^cn)} [BCKMP16,NSS01]	2^{O(n^1/8/log^cn)} [BCKMP16,NSS01]	Unknown	Unknown	Unknown
Planar	NP-hard [LG77]	See Algorithms	NP-hard [LG77]	Unknown	P [Trivial]	Unknown
Proper Interval	2^o(√n+m) [GJT76,GGKS95]	2^{O(√n/log^cn)} [BCKMP16]	NP-hard [BBD06]	Unknown	Unknown	Unknown
Split	2^{O(n^1-δ)} [CS17]	2^{O(n^1-δ)} [CS17]	See Algorithms	Unknown	Unknown	P [HS81]
Threshold	NP-hard [M94]	2^{O(√n/log^cn)} [BCKMP16]	NP-hard [DDLS15]	2^{O(n log n)} [D15]	2^{O(n log n)} [DFPV15]	2^{O(n log n)} [DDLS15]
Trivially Perfect	NP-hard [S02]	2^{O(√n/log^cn)} [BCKMP16]	NP-hard [NSS01]	Unknown	2^{O(n log n)} [DFPV15]	Unknown

Parameterized Lower Bounds and Algorithms

Π	Parameterized Lower Bounds			Parameterized Algorithms
Π	Deletion	Completion	Editing	Deletion	Completion	Editing
Bipartite	2^o(k)n^O(1) [Y81b]	See Algorithms	2^o(k)n^O(1) [Y81b]	O(1.977^k · nm) [PPW16]	P [Trivial]	O(1.977^k · nm) [PPW16]
Chordal	2^{O(k^1/4/log^cn)}n^O(1) [BCKMP16,NSS01]	2^{O(k^1/2-δ)} [CS17]	2^o(√k)n^O(1) [DDLS15]	2^{O(k log k)}n^O(1) [CM16]	2^{O(√k log k)}n^O(1) [FV13]	2^{O(k log k)}n^O(1) [CM16]
Comparability	2^o(k)n^O(1) [Y81b]	2^o(k)n^O(1) [HSY97]	2^o(k)n^O(1) [NSS01]	Unknown	Unknown	Unknown
H-free	2^o(k)n^O(1) [ASS16]	2^o(k)n^O(1) [ASS16]	2^o(k)n^O(1) [ASS16]	2^O(k)n^O(1) [C96]	2^O(k)n^O(1) [C96]	2^O(k)n^O(1) [C96]
Interval	2^o(√k)n^O(1) [GJT76,GGKS95]	2^{O(k^1/4/log^cn)}n^O(1) [BCKMP16]	2^o(√k)n^O(1) [BBD06,GJT76]	k^O(k)n^O(1) [C16]	k^O(√k)n^O(1) [BFPP16]	Unknown
Line	2^o(k)n^O(1) [Y81b]	Unknown	Unknown	2^O(k)n^O(1) [C96]	2^O(k)n^O(1) [C96]	2^O(k)n^O(1) [C96]
Perfect	2^{O(k^1/4/log^cn)}n^O(1) [BCKMP16,NSS01]	2^{O(k^1/4/log^cn)}n^O(1) [BCKMP16,NSS01]	2^{O(k^1/4/log^cn)}n^O(1) [BCKMP16,NSS01]	Unknown	Unknown	Unknown
Planar	Unknown	Unknown	Unknown	FPT [KR07]	P [Trivial]	FPT [KR07]
Proper Interval	2^o(√k)n^O(1) [GJT76,GGKS95]	2^{O(k^1/4/log^cn)}n^O(1) [BCKMP16]	Unknown	2^O(k)n^O(1) [C15]	2^{O(k^2/3log k)}n^O(1) [BFPP15]	2^{O(k log k)}n^O(1) [C15]
Split	2^{O(k^1/2-δ)}n^O(1) [CS17]	2^{O(k^1/2-δ)}n^O(1) [CS17]	See Algorithms	2^{O(√k log k)}n^O(1) [GKKMPRR13]	2^{O(√k log k)}n^O(1) [GKKMPRR13]	P [HS81]
Threshold	Unknown	Unknown	2^o(k)n^O(1) [D15]	2^{O(√k log k)}n^{O(1) [D15]}	2^{O(√k log k)}n^{O(1) [DFPV15]}	2^{O(√k log k)}n^{O(1) [DDLS15]}
Trivially Perfect	2^o(k)n^O(1) [DFPV15]	2^{O(k^1/4/log^cn)}n^O(1) [BCKMP16]	2^o(k)n^O(1) [DP15]	2^O(k)n^O(1) [C96]	2^{O(√k log k)}n^{O(1) [DFPV15]}	2^O(k)n^O(1) [C96]

Polynomial Kernelization

Π	Deletion	Completion	Editing
Cluster	2k [CK21]	P [Trivial]	2k [CC12]
Bipartite	Unknown	P [Trivial]	Unknown
Chordal	Unknown	O(k²) [NSS00]	Unknown
Comparability	Unknown	Unknown	Unknown
H-free	P.R. [CC15,S16]	P.R. [CC15,S16]	P.R. [CC15,S16]
Interval	Unknown	Unknown	Unknown
Line	P.R. [ASS14]	Unknown	P.R. [DDS16]
Perfect	Unknown	Unknown	Unknown
Planar	Unknown	P [Trivial]	Unknown
Proper Interval	Unknown	O(k³) [BP13]	Unknown
Split	O(k^1.5) [CK21]	O(k^1.5) [CK21]	P [HS81]
Pseudo-split	O(k^1.5) [CK21]	O(k^1.5) [CK21]
Threshold	O(k²) [DDLS15]	O(k²) [DDLS15]	O(k²) [DDLS15]
Trivially Perfect	O(k⁷) [DP15]	O(k²) [CK21]	O(k⁷) [DP15]

P.R. -- Partial Result(s).

If you have any feedback, please send an email or modify the content.

References

[ASS14] N. R. Aravind, R. B. Sandeep, and Naveen Sivadasan. On polynomial kernelization of ℋ-free edge deletion. In IPEC 2014:28–38. doi:10.1007/978-3-319-13524-3_3

[ASS16] N. R. Aravind, R. B. Sandeep, and Naveen Sivadasan. Parameterized lower bounds and dichotomy results for the NP-completeness of H-free edge modification problems. In LATIN, 2016:82--95. doi:10.1007/978-3-662-49529-2_7

[BP13] Stéphane Bessy and Anthony Perez. Polynomial kernels for Proper Interval Completion and related problems. Information and Computation, 231:89--108, 2013. doi:10.1016/j.ic.2013.08.006

[BCKMP16] Ivan Bliznets, Marek Cygan, Paweł Komasa, Lukáš Mach, and Michał Pilipczuk. Lower bounds for the parameterized complexity of minimum fill-in and other completion problems. In SODA 2016:1132--1151. doi:10.1137/1.9781611974331.ch79

[BFPP15] Ivan Bliznets, Fedor V. Fomin, Marcin Pilipczuk, and Michał Pilipczuk. A Subexponential Parameterized Algorithm for Proper Interval Completion. SIAM Journal on Discrete Mathematics, 29(4):1961--1987, 2015. doi:10.1137/140988565

[BFPP16] Ivan Bliznets, Fedor V. Fomin, Marcin Pilipczuk, and Michał Pilipczuk. Subexponential parameterized algorithm for interval completion. In SODA, 2016:1116--1131. doi:10.1137/1.9781611974331.ch78

[BBD06] Pablo Burzyn, Flavia Bonomo, and Guillermo Durán. NP-completeness results for edge modification problems. Discrete Applied Mathematics, 154(13):1824–1844, 2006. doi:10.1016/j.dam.2006.03.031

[Cai96] Leizhen Cai. 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

[CC15] Leizhen Cai and Yufei Cai. Incompressibility of H-free edge modification problems. Algorithmica, 71(3):731–757, 2015. doi:10.1007/s00453-014-9937-x

[Cao15] Yixin Cao. Unit interval editing is fixed-parameter tractable. In ICALP 2015:306--317. doi:10.1007/978-3-662-47672-7_25

[Cao16] Yixin Cao. Linear recognition of almost interval graphs. In SODA, 2016:1096--1115. doi:10.1137/1.9781611974331.ch77

[CC12] Yixin Cao and Jianer Chen. Cluster editing: Kernelization based on edge cuts. Algorithmica 64(1): 152–169 (2012). doi:10.1007/s00453-011-9595-1

[CK21] Yixin Cao and Yuping Ke. Improved kernels for edge modification problems. arXiv:2104.14510

[CM16] Yixin Cao and Dániel Marx. Chordal editing is fixed-parameter tractable. Algorithmica 75(1): 118-137 (2016). doi:10.1007/s00453-015-0014-x

[CS17] Yixin Cao, and R. B. Sandeep. Minimum Fill-In: Inapproximability and Almost Tight Lower Bounds. Information and Computation, 271 (2020) 104514. doi:10.1016/j.ic.2020.104514

[D15] Pål Grønås Drange. Parameterized Graph Modification Algorithms. PhD dissertation, University of Bergen, 2015.

[DDLS15] Pål Grønås Drange, Markus Sortland Dregi, Daniel Lokshtanov, and Blair D. Sullivan. On the threshold of intractability. In ESA 2015:411--423. doi:10.1007/978-3-662-48350-3_35

[DDS16] Pål Grønås Drange, Markus Sortland Dregi, and R. B. Sandeep. Compressing bounded degree graphs. In LATIN 2016, 2016:362--375. doi:10.1007/978-3-662-49529-2_27

[DFPV15] Pål Grønås Drange, Fedor V Fomin, Michał Pilipczuk, and Yngve Villanger. Exploring the subexponential complexity of completion problems. ACM Transactions on Computation Theory (TOCT), 7(4):14, 2015. doi:10.1145/2799640

[DP15] Pål Grønås Drange and Michał Pilipczuk. A polynomial kernel for trivially perfect editing. In ESA 2015:424–436. doi:10.1007/978-3-662-48350-3_36

[FKTV08] Fedor V. Fomin, Dieter Kratsch, Ioan Todinca, Yngve Villanger: Exact Algorithms for Treewidth and Minimum Fill-In. SIAM J. Comput. 38(3): 1058-1079 (2008). doi:10.1137/050643350

[FV13] Fedor V Fomin and Yngve Villanger. Subexponential parameterized algorithm for minimum fill-in. SIAM Journal on Computing, 42(6):2197--2216, 2013. doi:10.1137/11085390X

[GJT76] Michael R Garey, David S. Johnson, and R Endre Tarjan. The planar hamiltonian circuit problem is NP-complete. SIAM Journal on Computing, 5(4):704–714, 1976. doi:10.1137/0205049

[GKKMPRR13] Esha Ghosh, Sudeshna Kolay, Mrinal Kumar, Pranabendu Misra, Fahad Panolan, Ashutosh Rai, and MS Ramanujan. Faster parameterized algorithms for deletion to split graphs. Algorithmica, 71(4):989–1006, 2013. doi:10.1007/s00453-013-9837-5

[GGKS95] Paul W Goldberg, Martin C Golumbic, Haim Kaplan, and Ron Shamir. Four strikes against physical mapping of DNA. Journal of Computational Biology, 2(1):139–152, 1995. doi:10.1089/cmb.1995.2.139

[HSY97] S Louis Hakimi, Edward F Schmeichel, and Neal E Young. Orienting graphs to optimize reachability. Information Processing Letters, 63(5):229–235, 1997. doi:10.1016/S0020-0190(97)00129-4

[HS81] Peter L Hammer and Bruno Simeone. The splittance of a graph. Combinatorica, 1(3):275–284, 1981. doi:10.1007/BF02579333

[KR07] Ken-ichi Kawarabayashi and Buce Reed. Computing crossing number in linear time. In STOC 2007:382–390. doi:10.1145/1250790.1250848

[LG77] PC Liu and RC Geldmacher. On the deletion of nonplanar edges of a graph. In 10th Southeastern Conference on Combinatorics, Graph Theory, and Computing 1977:727–738.

[M94] François Margot. Some complexity results about threshold graphs. Discrete applied mathematics, 49(1):299–308, 1994. doi:10.1016/0166-218X(94)90214-3

[NSS00] Assaf Natanzon, Ron Shamir, and Roded Sharan. A polynomial approximation algorithm for the minimum fill-in problem. SIAM Journal on Computing, 30(4):1067–1079, 2000. doi:10.1137/S0097539798336073

[NSS01] Assaf Natanzon, Ron Shamir, and Roded Sharan. Complexity classification of some edge modification problems. Discrete Applied Mathematics, 113(1):109--128, 2001. doi:10.1016/S0166-218X(00)00391-7

[PPW16] Marcin Pilipczuk, Michał Pilipczuk and Marcin Wrochna. Edge Bipartization faster than 2^k. IPEC 2016.

[San16] R. B. Sandeep. Results on Hardness of Edge Modification Problems and Chromatic Discrepancy of Graphs. PhD thesis, IIT Hyderabad, 2016.

[Sha02] Roded Sharan. Graph modification problems and their applications to genomic research. PhD thesis, Tel-Aviv University, 2002.

[Yan81a] Mihalis Yannakakis. Computing the minimum fill-in is NP-complete. SIAM Journal on Algebraic Discrete Methods, 2(1):77--79, 1981.

[Yan81b] Mihalis Yannakakis. Edge Deletion Problems. SIAM J. Comput., 10(2):297--309, 1981. doi:10.1137/0210021