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 2o(n+m) [Y81b] See Algorithms 2o(n+m) [Y81b] Unknown P [Trivial] Unknown
Chordal 2O(n1/4/logcn) [BCKMP16,NSS01] 2O(n1-δ) [CS17] NP-hard [DDLS15] Unknown O(1.8899n) [FKTV08] Unknown
Comparability 2o(n+m) [Y81b] 2O(n+m) [HSY97] 2O(n) [NSS01] Unknown Unknown Unknown
H-free NP-hard [ASS16] NP-hard [ASS16] NP-hard [ASS16] Unknown Unknown Unknown
Interval 2o(√n+m) [GJT76,GGKS95] 2O(√n/logcn) [BCKMP16] 2o(√n+m) [BBD06,GJT76] Unknown Unknown Unknown
Line 2o(n+m) [Y81b] Unknown Unknown Unknown Unknown Unknown
Perfect 2O(n1/8/logcn) [BCKMP16,NSS01] 2O(n1/8/logcn) [BCKMP16,NSS01] 2O(n1/8/logcn) [BCKMP16,NSS01] Unknown Unknown Unknown
Planar NP-hard [LG77] See Algorithms NP-hard [LG77] Unknown P [Trivial] Unknown
Proper Interval 2o(√n+m) [GJT76,GGKS95] 2O(√n/logcn) [BCKMP16] NP-hard [BBD06] Unknown Unknown Unknown
Split 2O(n1-δ) [CS17] 2O(n1-δ) [CS17] See Algorithms Unknown Unknown P [HS81]
Threshold NP-hard [M94] 2O(√n/logcn) [BCKMP16] NP-hard [DDLS15] 2O(n log n) [D15] 2O(n log n) [DFPV15] 2O(n log n) [DDLS15]
Trivially Perfect NP-hard [S02] 2O(√n/logcn) [BCKMP16] NP-hard [NSS01] Unknown 2O(n log n) [DFPV15] Unknown

Parameterized Lower Bounds and Algorithms

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

Polynomial Kernelization

Bipartite Unknown P [Trivial] Unknown
Chordal Unknown O(k2) [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(k3) [BP13] Unknown
Split O(k2) [GKKMPRR13] O(k2) [GKKMPRR13] P [HS81]
Threshold O(k2) [DDLS15] O(k2) [DDLS15] O(k2) [DDLS15]
Trivially Perfect O(k7) [DP15] O(k3) [G07] O(k7) [DP15]
P.R. -- Partial Result(s).

If you have any feedback, please send an email.


[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

[C96] 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

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

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

[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. To appear in SODA 2017.

[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

[G07] Jiong Guo. Problem kernels for NP-complete edge deletion problems: Split and related graphs. In ISAAC 2007:915–926. doi:10.1007/978-3-540-77120-3_79

[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.

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

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

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

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