A survey of parameterized algorithms and the complexity of edge modification

Lewis, 1980, The node-deletion problem for hereditary properties is NP-complete, J. Comput. System Sci., 20, 219, 10.1016/0022-0000(80)90060-4 Yannakakis, 1981, Edge-deletion problems, SIAM J. Comput., 10, 297, 10.1137/0210021 Burzyn, 2006, NP-completeness results for edge modification problems, Discrete Appl. Math., 154, 1824, 10.1016/j.dam.2006.03.031 Mancini, 2008 Natanzon, 2001, Complexity classification of some edge modification problems, Discrete Appl. Math., 113, 109, 10.1016/S0166-218X(00)00391-7 Yannakakis, 1981, Computing the minimum fill-in is NP-complete, SIAM J. Algebr. Discrete Methods, 2, 77, 10.1137/0602010 Eswaran, 1976, Augmentation problems, SIAM J. Comput., 5, 653, 10.1137/0205044 Shamir, 2004, Cluster graph modification problems, Discrete Appl. Math., 144, 173, 10.1016/j.dam.2004.01.007 Hammer, 1981, The splittance of a graph, Combinatorica, 275, 10.1007/BF02579333 Cygan, 2015 Fomin, 2019 Golovach, 2013, Obtaining planarity by contracting few edges, Theoret. Comput. Sci., 476, 38, 10.1016/j.tcs.2012.12.041 Guillemot, 2013, A faster FPT algorithm for bipartite contraction, Inform. Process. Lett., 113, 906, 10.1016/j.ipl.2013.09.004 Guo, 2015, Obtaining split graphs by edge contraction, Theoret. Comput. Sci., 607, 60, 10.1016/j.tcs.2015.01.056 Heggernes, 2013, Obtaining a bipartite graph by contracting few edges, SIAM J. Discrete Math., 27, 2143, 10.1137/130907392 Cai, 2003, Parameterized complexity of vertex colouring, Discrete Appl. Math., 127, 415, 10.1016/S0166-218X(02)00242-1 Downey, 1992, Fixed-parameter tractability and completeness, vol. 87, 161 Flum, 2006 Downey, 2013 Grohe, 2007, Logic, graphs, and algorithms Niedermeier, 2006, Invitation to fixed-parameter algorithms, vol. 31 Bodlaender, 2009, On problems without polynomial kernels, J. Comput. System Sci., 75, 423, 10.1016/j.jcss.2009.04.001 Impagliazzo, 2001, Which problems have strongly exponential complexity?, J. Comput. System Sci., 63, 512, 10.1006/jcss.2001.1774 Golumbic, 1980 Brandstädt, 1999, Graph classes. A survey Kawarabayashi, 2007, Computing crossing number in linear time, 382 Lokshtanov, 2008, Wheel-free deletion is W[2]-hard, vol. 5018, 141 Guillemot, 2013, On the (non-)existence of polynomial kernels for Pl-free edge modification problems, Algorithmica, 65, 900, 10.1007/s00453-012-9619-5 Cai, 2012 Fomin, 2013, Subexponential parameterized algorithm for minimum fill-in, SIAM J. Comput., 42, 2197, 10.1137/11085390X Drange, 2015, Exploring the subexponential complexity of completion problems, ACM Trans. Comput. Theory, 7, 14:1, 10.1145/2799640 Drange, 2018, A polynomial kernel for trivially perfect editing, Algorithmica, 80, 3481, 10.1007/s00453-017-0401-6 Cai, 1996, Fixed-parameter tractability of graph modification problems for hereditary properties, Inform. Process. Lett., 58, 171, 10.1016/0020-0190(96)00050-6 Liu, 2014, An overview of kernelization algorithms for graph modification problems, Tsinghua Sci. Technol., 19, 346, 10.1109/TST.2014.6867517 Abu-Khzam, 2010, A kernelization algorithm for d-hitting set, J. Comput. System Sci., 76, 524, 10.1016/j.jcss.2009.09.002 Guo, 2010, A more relaxed model for graph-based data clustering: s-plex cluster editing, SIAM J. Discrete Math., 24, 1662, 10.1137/090767285 Bessy, 2013, Polynomial kernels for proper interval completion and related problems, Inform. and Comput., 231, 89, 10.1016/j.ic.2013.08.006 Drange, 2022, On the threshold of intractability, J. Comput. System Sci., 124, 1, 10.1016/j.jcss.2021.09.003 Bathie, 2022, (Sub)linear kernels for edge modification problems toward structured graph classes, Algorithmica, 84, 3338, 10.1007/s00453-022-00969-1 Cao, 2021, Improved kernels for edge modification problems, vol. 214, 13:1 Dumas, 2021, A cubic vertex-kernel for trivially perfect editing, vol. 202, 45:1 Cygan, 2017, Polynomial kernelization for removing induced claws and diamonds, Theory Comput. Syst., 60, 615, 10.1007/s00224-016-9689-x Drange, 2015 Chen, 2012, A 2k kernel for the cluster editing problem, J. Comput. System Sci., 78, 211, 10.1016/j.jcss.2011.04.001 Cao, 2012, Cluster editing: Kernelization based on edge cuts, Algorithmica, 64, 152, 10.1007/s00453-011-9595-1 Brügmann, 2009, On generating triangle-free graphs, Electron. Notes Discrete Math., 32, 51, 10.1016/j.endm.2009.02.008 Yuan, 2021, Polynomial kernels for paw-free edge modification problems, Theoret. Comput. Sci., 891, 1, 10.1016/j.tcs.2021.08.015 Eiben, 2020, A polynomial kernel for paw-free editing, vol. 180, 10:1 Sandeep, 2015, Parameterized lower bound and improved kernel for diamond-free edge deletion, vol. 43, 365 Cao, 2022, A polynomial kernel for diamond-free editing, Algorithmica, 84, 197, 10.1007/s00453-021-00891-y Tsur, 2021, Kernel for Kt-free edge deletion, Inform. Process. Lett., 167, 10.1016/j.ipl.2020.106082 Cai, 2015, Incompressibility of H-free edge modification problems, Algorithmica, 71, 731, 10.1007/s00453-014-9937-x Guo, 2007, Problem kernels for NP-complete edge deletion problems: Split and related graphs, vol. 4835, 915 Gramm, 2009, Data reduction and exact algorithms for clique cover, ACM J. Exp. Algorithmics, 13, 2.2.2, 10.1145/1412228.1412236 Fellows, 2007, Efficient parameterized preprocessing for cluster editing, vol. 4639, 312 Kratsch, 2013, Two edge modification problems without polynomial kernels, Discrete Optim., 10, 193, 10.1016/j.disopt.2013.02.001 Nastos, 2012, Bounded search tree algorithms for parametrized cograph deletion: Efficient branching rules by exploiting structures of special graph classes, Discrete Math. Algorithms Appl., 4, 10.1142/S1793830912500085 Liu, 2012, Complexity and parameterized algorithms for cograph editing, Theoret. Comput. Sci., 461, 45, 10.1016/j.tcs.2011.11.040 Fellows, 2011, Graph-based data clustering with overlaps, Discrete Optim., 8, 2, 10.1016/j.disopt.2010.09.006 Cygan, 2013 Beineke, 1970, Characterizations of derived graphs, J. Combin. Theory, 9, 129, 10.1016/S0021-9800(70)80019-9 Aravind, 2017, On polynomial kernelization of H-free edge deletion, Algorithmica, 79, 654, 10.1007/s00453-016-0215-y Böcker, 2013, Cluster editing, vol. 7921, 33 Gramm, 2005, Graph-modeled data clustering: Exact algorithms for clique generation, Theory Comput. Syst., 38, 373, 10.1007/s00224-004-1178-y Guo, 2009, A more effective linear kernelization for cluster editing, Theoret. Comput. Sci., 410, 718, 10.1016/j.tcs.2008.10.021 Böcker, 2011, Even faster parameterized cluster deletion and cluster editing, Inform. Process. Lett., 111, 717, 10.1016/j.ipl.2011.05.003 Böcker, 2012, A golden ratio parameterized algorithm for cluster editing, J. Discrete Algorithms, 16, 79, 10.1016/j.jda.2012.04.005 van Bevern, 2018, Parameterizing edge modification problems above lower bounds, Theory Comput. Syst., 62, 739, 10.1007/s00224-016-9746-5 Li, 2021, Cluster editing parameterized above modification-disjoint P3-packings, vol. 187, 49:1 Xia, 2012, Kernelization for cycle transversal problems, Discrete Appl. Math., 160, 1224, 10.1016/j.dam.2011.12.024 Liu, 2015, Edge deletion problems: Branching facilitated by modular decomposition, Theoret. Comput. Sci., 573, 63, 10.1016/j.tcs.2015.01.049 Ghosh, 2015, Faster parameterized algorithms for deletion to split graphs, Algorithmica, 71, 989, 10.1007/s00453-013-9837-5 Nastos, 2013, Familial groups in social networks, Social Networks, 35, 439, 10.1016/j.socnet.2013.05.001 Kaplan, 1999, Tractability of parameterized completion problems on chordal, strongly chordal, and proper interval graphs, SIAM J. Comput., 28, 1906, 10.1137/S0097539796303044 Natanzon, 2000, A polynomial approximation algorithm for the minimum fill-in problem, SIAM J. Comput., 30, 1067, 10.1137/S0097539798336073 Agrawal, 2019, Feedback vertex set inspired kernel for chordal vertex deletion, ACM Trans. Algorithms, 15, 11:1, 10.1145/3284356 Jansen, 2018, Approximation and kernelization for chordal vertex deletion, SIAM J. Discrete Math., 32, 2258, 10.1137/17M112035X Cao, 2016, Chordal editing is fixed-parameter tractable, Algorithmica, 75, 118, 10.1007/s00453-015-0014-x Marx, 2010, Chordal deletion is fixed-parameter tractable, Algorithmica, 57, 747, 10.1007/s00453-008-9233-8 Villanger, 2009, Interval completion is fixed parameter tractable, SIAM J. Comput., 38, 2007, 10.1137/070710913 Cao, 2013 Cao, 2016, Linear recognition of almost interval graphs, 1096 Bliznets, 2018, Subexponential parameterized algorithm for interval completion, ACM Trans. Algorithms, 14, 35:1, 10.1145/3186896 Agrawal, 2019, Interval vertex deletion admits a polynomial kernel, 1711 Cao, 2015, Interval deletion is fixed-parameter tractable, ACM Trans. Algorithms, 11, 21:1, 10.1145/2629595 Liu, 2015, An effective branching strategy based on structural relationship among multiple forbidden induced subgraphs, J. Comb. Optim., 29, 257, 10.1007/s10878-014-9733-1 Nishimura, 2002, On graph powers for leaf-labeled trees, J. Algorithms, 42, 69, 10.1006/jagm.2001.1195 Dom, 2006, Error compensation in leaf power problems, Algorithmica, 44, 363, 10.1007/s00453-005-1180-z Bessy, 2010, Polynomial kernels for 3-leaf power graph modification problems, Discrete Appl. Math., 158, 1732, 10.1016/j.dam.2010.07.002 Dom, 2005, Extending the tractability border for closest leaf powers, vol. 3787, 397 Dom, 2008, Closest 4-leaf power is fixed-parameter tractable, Discrete Appl. Math., 156, 3345, 10.1016/j.dam.2008.01.007 Dumas, 2021, Polynomial kernels for strictly chordal edge modification problems, vol. 214, 17:1 Crespelle, 2021, Completion to chordal distance-hereditary graphs: A quartic vertex-kernel, vol. 12911, 156 Courcelle, 2001, On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic, Discrete Appl. Math., 108, 23, 10.1016/S0166-218X(00)00221-3 Kim, 2021, A polynomial kernel for distance-hereditary vertex deletion, Algorithmica, 83, 2096, 10.1007/s00453-021-00820-z Robertson, 2004, Graph minors. XX. Wagner’s conjecture, J. Combin. Theory Ser. B, 92, 325, 10.1016/j.jctb.2004.08.001 Robertson, 1994, Graph minors. XI. Circuits on a surface, J. Combin. Theory Ser. B, 60, 72, 10.1006/jctb.1994.1007 Adler, 2008, Computing excluded minors, 641 Fomin, 2012, Planar F-deletion: Approximation, kernelization and optimal FPT algorithms, 470 Reed, 2004, Finding odd cycle transversals, Oper. Res. Lett., 32, 299, 10.1016/j.orl.2003.10.009 Wernicke, 2003, On the algorithmic tractability of single nucleotide polymorphism (SNP) analysis and related problems Guo, 2006, Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization, J. Comput. System Sci., 72, 1386, 10.1016/j.jcss.2006.02.001 Pilipczuk, 2019, Edge bipartization faster than 2k, Algorithmica, 81, 917, 10.1007/s00453-017-0319-z Kratsch, 2014, Compression via matroids: A randomized polynomial kernel for odd cycle transversal, ACM Trans. Algorithms, 10, 20, 10.1145/2635810 Feng, 2014, Randomized parameterized algorithms for co-path set problem, vol. 8497, 82 van ’t Hof, 2013, Proper interval vertex deletion, Algorithmica, 65, 845, 10.1007/s00453-012-9661-3 Heggernes, 2013, Parameterized complexity of vertex deletion into perfect graph classes, Theoret. Comput. Sci., 511, 172, 10.1016/j.tcs.2012.03.013 Marx, 2012, What’s next? Future directions in parameterized complexity, vol. 7370, 469 Demaine, 2005, Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs, J. ACM, 52, 866, 10.1145/1101821.1101823 Bodlaender, 2008 Alon, 2009, Fast FAST, vol. 5555, 49 Dom, 2010, Fixed-parameter tractability results for feedback set problems in tournaments, J. Discrete Algorithms, 8, 76, 10.1016/j.jda.2009.08.001 Bessy, 2011, Kernels for feedback arc set in tournaments, J. Comput. System Sci., 77, 1071, 10.1016/j.jcss.2010.10.001 Bodlaender, 2011, Faster parameterized algorithms for minimum fill-in, Algorithmica, 61, 817, 10.1007/s00453-010-9421-1 Bouchitté, 2001, Treewidth and minimum fill-in: Grouping the minimal separators, SIAM J. Comput., 31, 212, 10.1137/S0097539799359683 Bouchitté, 2002, Listing all potential maximal cliques of a graph, Theoret. Comput. Sci., 276, 17, 10.1016/S0304-3975(01)00007-X Fomin, 2008, Exact algorithms for treewidth and minimum fill-in, SIAM J. Comput., 38, 1058, 10.1137/050643350 Komusiewicz, 2012, Cluster editing with locally bounded modifications, Discrete Appl. Math., 160, 2259, 10.1016/j.dam.2012.05.019 Drange, 2015, Fast biclustering by dual parameterization, vol. 43, 402 Bliznets, 2020, Lower bounds for the parameterized complexity of minimum fill-in and other completion problems, ACM Trans. Algorithms, 16, 1, 10.1145/3381426 Damaschke, 2014, Editing simple graphs, J. Graph Algorithms Appl., 18, 557, 10.7155/jgaa.00337 Aravind, 2017, Dichotomy results on the hardness of H-free edge modification problems, SIAM J. Discrete Math., 31, 542, 10.1137/16M1055797 Fomin, 2014, Tight bounds for parameterized complexity of cluster editing with a small number of clusters, J. Comput. System Sci., 80, 1430, 10.1016/j.jcss.2014.04.015 Bliznets, 2015, A subexponential parameterized algorithm for proper interval completion, SIAM J. Discrete Math., 29, 1961, 10.1137/140988565 Bodlaender, 2014, Graph modification problems (Dagstuhl Seminar 14071), Dagstuhl Rep., 4, 38 Borgatti, 2000, Models of core/periphery structures, Social Networks, 21, 375, 10.1016/S0378-8733(99)00019-2 Kovác, 2014, On the clique editing problem, vol. 8635, 469 Meesum, 2016, Reducing rank of the adjacency matrix by graph modification, Theoret. Comput. Sci., 654, 70, 10.1016/j.tcs.2016.02.020 Meesum, 2018, Rank reduction of oriented graphs by vertex and edge deletions, Algorithmica, 80, 2757, 10.1007/s00453-017-0340-2 Cao, 2020, Minimum fill-in: Inapproximability and almost tight lower bounds, Inform. and Comput., 271, 10.1016/j.ic.2020.104514 Cao, 2017, Unit interval editing is fixed-parameter tractable, Inform. and Comput., 253, 109, 10.1016/j.ic.2017.01.008 Bliznets, 2018, Hardness of approximation for H-free edge modification problems, ACM Trans. Comput. Theory, 10, 9:1, 10.1145/3196834 Chen, 2011, Lower bounds for kernelizations and other preprocessing procedures, Theory Comput. Syst., 48, 803, 10.1007/s00224-010-9270-y Fernau, 2020, Diminishable parameterized problems and strict polynomial kernelization, Computability, 9, 1, 10.3233/COM-180220 Chen, 2006, Minimum-flip supertrees: Complexity and algorithms, IEEE/ACM Trans. Comput. Biol. Bioinform., 3, 165, 10.1109/TCBB.2006.26 Böcker, 2012, Improved fixed-parameter algorithms for minimum-flip consensus trees, ACM Trans. Algorithms, 8, 10.1145/2071379.2071386 Komusiewicz, 2014, A cubic-vertex kernel for flip consensus tree, Algorithmica, 68, 81, 10.1007/s00453-012-9663-1 Guo, 2008, Improved algorithms for bicluster editing, vol. 4978, 445 Tsur, 2021, Faster parameterized algorithm for bicluster editing, Inform. Process. Lett., 168, 10.1016/j.ipl.2021.106095 Fernau, 2005, Two-layer planarization: Improving on parameterized algorithmics, J. Graph Algorithms Appl., 9, 205, 10.7155/jgaa.00106 Fernau, 2014, Social choice meets graph drawing: how to get subexponential time algorithms for ranking and drawing problems, Tsinghua Sci. Technol., 19, 374, 10.1109/TST.2014.6867519 Kobayashi, 2015, A fast and simple subexponential fixed parameter algorithm for one-sided crossing minimization, Algorithmica, 72, 778, 10.1007/s00453-014-9872-x Zehavi, 2022, Parameterized analysis and crossing minimization problems, Comp. Sci. Rev., 45 Lokshtanov, 2014, Faster parameterized algorithms using linear programming, ACM Trans. Algorithms, 11, 15, 10.1145/2566616 Cygan, 2013 Majumdar, 2019, Tractability of Kőnig edge deletion problems, Theoret. Comput. Sci., 796, 207, 10.1016/j.tcs.2019.09.011 Bock, 2015, Finding small stabilizers for unstable graphs, Math. Program., 154, 173, 10.1007/s10107-014-0854-1 Jr., 1956, Maximal flow through a network, Canad. J. Math., 8, 399, 10.4153/CJM-1956-045-5 Dahlhaus, 1994, The complexity of multiterminal cuts, SIAM J. Comput., 23, 864, 10.1137/S0097539792225297 Marx, 2006, Parameterized graph separation problems, Theoret. Comput. Sci., 351, 394, 10.1016/j.tcs.2005.10.007 Xiao, 2010, Simple and improved parameterized algorithms for multiterminal cuts, Theory Comput. Syst., 46, 723, 10.1007/s00224-009-9215-5 Cao, 2014, An O∗(1.84k) parameterized algorithm for the multiterminal cut problem, Inform. Process. Lett., 114, 167, 10.1016/j.ipl.2013.12.001 Klein, 2012, Solving planar k-terminal cut in O(nck) time, vol. 7391, 569 Lokshtanov, 2012, Parameterized tractability of multiway cut with parity constraints, vol. 7391, 750 Chandrasekaran, 2020, Odd multiway cut in directed acyclic graphs, SIAM J. Discrete Math., 34, 1385, 10.1137/18M1176087 Chitnis, 2013, Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset, SIAM J. Comput., 42, 1674, 10.1137/12086217X Chen, 2008, A fixed-parameter algorithm for the directed feedback vertex set problem, J. ACM, 55, 10.1145/1411509.1411511 Even, 1998, Approximating minimum feedback sets and multicuts in directed graphs, Algorithmica, 20, 151, 10.1007/PL00009191 Chitnis, 2015, Directed subset feedback vertex set is fixed-parameter tractable, ACM Trans. Algorithms, 11, 28, 10.1145/2700209 Xiao, 2012, An FPT algorithm for edge subset feedback edge set, Inform. Process. Lett., 112, 5, 10.1016/j.ipl.2011.10.007 Kratsch, 2020, Multi-budgeted directed cuts, Algorithmica, 82, 2135, 10.1007/s00453-019-00609-1 Claudio, 1978, A minimax theorem for directed graphs, J. Lond. Math. Soc., 2–17, 369 Garg, 1997, Primal–dual approximation algorithms for integral flow and multicut in trees, Algorithmica, 18, 3, 10.1007/BF02523685 Guo, 2005, Fixed-parameter tractability and data reduction for multicut in trees, Networks, 46, 124, 10.1002/net.20081 Bousquet, 2018, Multicut is FPT, SIAM J. Comput., 47, 166, 10.1137/140961808 Marx, 2014, Fixed-parameter tractability of multicut parameterized by the size of the cutset, SIAM J. Comput., 43, 355, 10.1137/110855247 Pilipczuk, 2018, Directed multicut is W[1]-hard, even for four terminal pairs, ACM Trans. Comput. Theory, 10, 1, 10.1145/3201775 Kratsch, 2015, Fixed-parameter tractability of multicut in directed acyclic graphs, SIAM J. Discrete Math., 29, 122, 10.1137/120904202 Chitnis, 2019, FPT inapproximability of directed cut and connectivity problems, vol. 148, 8:1 Bringmann, 2016, Parameterized complexity dichotomy for Steiner Multicut, J. Comput. System Sci., 82, 1020, 10.1016/j.jcss.2016.03.003 Golovach, 2011, Paths of bounded length and their cuts: Parameterized complexity and algorithms, Discrete Optim., 8, 72, 10.1016/j.disopt.2010.09.009 Fluschnik, 2018, Fractals for kernelization lower bounds, SIAM J. Discrete Math., 32, 656, 10.1137/16M1088740 Dvorák, 2018, Parameterized complexity of length-bounded cuts and multicuts, Algorithmica, 80, 3597, 10.1007/s00453-018-0408-7 Bazgan, 2019, A more fine-grained complexity analysis of finding the most vital edges for undirected shortest paths, Networks, 73, 23, 10.1002/net.21832 Bentert, 2022, Length-bounded cuts: Proper interval graphs and structural parameters, J. Comput. System Sci., 126, 21, 10.1016/j.jcss.2021.12.002 Kolman, 2018, On algorithms employing treewidth for L-bounded cut problems, J. Graph Algorithms Appl., 22, 177, 10.7155/jgaa.00462 Fan, 2022, Metric violation distance: Hardness and approximation, Algorithmica, 84, 1441, 10.1007/s00453-022-00940-0 Fan, 2018 Fan, 2020, Generalized metric repair on graphs, vol. 162, 25:1 Lokshtanov, 2013, Clustering with local restrictions, Inform. and Comput., 222, 278, 10.1016/j.ic.2012.10.016 Fomin, 2013, On the parameterized complexity of cutting a few vertices from a graph, vol. 8087, 421 Cygan, 2019, Minimum bisection is fixed-parameter tractable, SIAM J. Comput., 48, 417, 10.1137/140988553 van Bevern, 2013, On the parameterized complexity of computing graph bisections, vol. 8165, 76 Kim, 2017, Parameterized algorithms for min–max multiway cut and list digraph homomorphism, J. Comput. System Sci., 86, 191, 10.1016/j.jcss.2017.01.003 Chitnis, 2017, List H-coloring a graph by removing few vertices, Algorithmica, 78, 110, 10.1007/s00453-016-0139-6 Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, Magnus Wahlström, Directed flow-augmentation, in: Proceedings of the 54th Annual ACM Symposium on Theory of Computing (STOC), 2022, pp. 938–947. Downey, 2003, Cutting up is hard to do: the parameterised complexity of k-cut and related problems, Electron. Notes Theor. Comput. Sci., 78, 209, 10.1016/S1571-0661(04)81014-4 ichi Kawarabayashi, 2011, The minimum k-way cut of bounded size is fixed-parameter tractable, 160 Marx, 2013, Finding small separators in linear time via treewidth reduction, ACM Trans. Algorithms, 9, 30:1, 10.1145/2500119 Komusiewicz, 2020, Matching cut: Kernelization, single-exponential time FPT, and exact exponential algorithms, Discrete Appl. Math., 283, 44, 10.1016/j.dam.2019.12.010 Gomes, 2021, Finding cuts of bounded degree: Complexity, FPT and exact algorithms, and kernelization, Algorithmica, 83, 1677, 10.1007/s00453-021-00798-8 Ray, 1994, Computational complexity of weighted integrity, J. Combin. Math. Combin. Comput., 16, 65 Drange, 2016, On the computational complexity of vertex integrity and component order connectivity, Algorithmica, 76, 1181, 10.1007/s00453-016-0127-x Gross, 2013, A survey of component order connectivity models of graph theoretic networks, WSEAS Trans. Math., 12, 895 Clark, 1987, Computational complexity of integrity, J. Combin. Math. Combin. Comput., 2, 179 Fellows, 1989, Forbidden subgraphs and the complexity of network integrity, J. Combin. Math. Combin. Comput., 6, 23 Barefoot, 1987, Vulnerability in graphs — a comparative survey, J. Combin. Math. Combin. Comput., 1, 13 Bang-Jensen, 2022, Component order connectivity in directed graphs, Algorithmica, 84, 2767, 10.1007/s00453-022-01004-z Bagga, 1994, Edge-integrity: a survey, Discrete Math., 124, 3, 10.1016/0012-365X(94)90084-1 Kratsch, 1997, Measuring the vulnerability for classes of intersection graphs, Discrete Appl. Math., 77, 259, 10.1016/S0166-218X(96)00133-3 Watanabe, 1987, Edge-connectivity augmentation problems, J. Comput. System Sci., 35, 96, 10.1016/0022-0000(87)90038-9 Cai, 1989, The minimum augmentation of any graph to a k-edge-connected graph, Networks, 19, 151, 10.1002/net.3230190112 Frank, 1992, Augmenting graphs to meet edge-connectivity requirements, SIAM J. Discrete Math., 5, 25, 10.1137/0405003 Vegh, 2011, Augmenting undirected node-connectivity by one, SIAM J. Discrete Math., 25, 695, 10.1137/100787507 Jackson, 2005, Independence free graphs and vertex connectivity augmentation, J. Combin. Theory Ser. B, 94, 31, 10.1016/j.jctb.2004.01.004 Nagamochi, 2003, An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree, Discrete Appl. Math., 126, 83, 10.1016/S0166-218X(02)00218-4 Guo, 2010, Kernelization and complexity results for connectivity augmentation problems, Networks, 56, 131 Marx, 2015, Fixed-parameter algorithms for minimum-cost edge-connectivity augmentation, ACM Trans. Algorithms, 11, 27, 10.1145/2700210 Basavaraju, 2014, Parameterized algorithms to preserve connectivity, vol. 8572, 800 Hüffner, 2015, Finding highly connected subgraphs, vol. 8939, 254 Adler, 2016, Planar disjoint-paths completion, Algorithmica, 76, 401, 10.1007/s00453-015-0046-2 Gutin, 2019, Path-contractions, edge deletions and connectivity preservation, J. Comput. System Sci., 101, 1, 10.1016/j.jcss.2018.10.001 Liu, 2012, On editing graphs into 2-club clusters, vol. 7285, 235 Abu-Khzam, 2017, On the complexity of multi-parameterized cluster editing, J. Discrete Algorithms, 45, 26, 10.1016/j.jda.2017.07.003 Misra, 2020, Subexponential algorithm for d-cluster edge deletion: Exception or rule?, J. Comput. System Sci., 113, 150, 10.1016/j.jcss.2020.05.008 Hüffner, 2014, Partitioning biological networks into highly connected clusters with maximum edge coverage, IEEE/ACM Trans. Comput. Biol. Bioinform., 11, 455, 10.1109/TCBB.2013.177 Bliznets, 2017, Parameterized algorithms for partitioning graphs into highly connected clusters, vol. 83, 6:1 Golovach, 2019, Clustering to given connectivities, vol. 115, 17:1 Böcker, 2009, Going weighted: Parameterized algorithms for cluster editing, Theoret. Comput. Sci., 410, 5467, 10.1016/j.tcs.2009.05.006 Luo, 2021, Parameterized dynamic cluster editing, Algorithmica, 83, 1, 10.1007/s00453-020-00746-y Chen, 2018, Cluster editing in multi-layer and temporal graphs, vol. 123, 24:1 Bocci, 2022, A new temporal interpretation of cluster editing, vol. 13270, 214 Moser, 2009, Parameterized complexity of finding regular induced subgraphs, J. Discrete Algorithms, 7, 181, 10.1016/j.jda.2008.09.005 Mathieson, 2012, Editing graphs to satisfy degree constraints: A parameterized approach, J. Comput. System Sci., 78, 179, 10.1016/j.jcss.2011.02.001 Garey, 1979 Stewart, 1994, Deciding whether a planar graph has a cubic subgraph is NP-complete, Discrete Math., 126, 349, 10.1016/0012-365X(94)90277-1 Stewart, 1996, Finding regular subgraphs in both arbitrary and planar graphs, Discrete Appl. Math., 68, 223, 10.1016/0166-218X(95)00061-U Stewart, 1997, On locating cubic subgraphs in bounded-degree connected bipartite graphs, Discrete Math., 163, 319, 10.1016/0012-365X(95)00324-P Mathieson, 2009 Frick, 2001, Deciding first-order properties of locally tree-decomposable structures, J. ACM, 48, 1184, 10.1145/504794.504798 Bulian, 2017, Fixed-parameter tractable distances to sparse graph classes, Algorithmica, 79, 139, 10.1007/s00453-016-0235-7 Golovach, 2015, Editing to a graph of given degrees, Theoret. Comput. Sci., 591, 72, 10.1016/j.tcs.2015.04.034 Froese, 2016, Win-win kernelization for degree sequence completion problems, J. Comput. System Sci., 82, 1100, 10.1016/j.jcss.2016.03.009 Dabrowski, 2017, Editing to a planar graph of given degrees, J. Comput. System Sci., 85, 168, 10.1016/j.jcss.2016.11.009 Golovach, 2017, Editing to a connected graph of given degrees, Inform. and Comput., 256, 131, 10.1016/j.ic.2017.04.013 Deborah, 2002, Optimal Hamiltonian completions and path covers for trees, and a reduction to maximum flow, ANZIAM J., 44, 193, 10.1017/S1446181100013894 Moran, 1991, Optimal covering of cacti by vertex-disjoint paths, Theoret. Comput. Sci., 84, 179, 10.1016/0304-3975(91)90159-Y Fomin, 2019, Editing to connected F-degree graph, SIAM J. Discrete Math., 33, 795, 10.1137/17M1129428 Haarberg, 2019 Bredereck, 2019, A parameterized algorithmics framework for degree sequence completion problems in directed graphs, Algorithmica, 81, 1584, 10.1007/s00453-018-0494-6 Mathieson, 2017, Graph editing problems with extended regularity constraints, Theoret. Comput. Sci., 677, 56, 10.1016/j.tcs.2017.03.019 Bodlaender, 2016, (Meta) kernelization, J. ACM, 63, 44:1, 10.1145/2973749 Boesch, 1977, The spanning subgraphs of Eulerian graphs, J. Graph Theory, 1, 79, 10.1002/jgt.3190010115 Lesniak, 1986, An Eulerian exposition, J. Graph Theory, 10, 277, 10.1002/jgt.3190100306 Dorn, 2013, Efficient algorithms for Eulerian extension and rural postman, SIAM J. Discrete Math., 27, 75, 10.1137/110834810 Diestel, 2012, Graph theory, vol. 173 Dabrowski, 2016, Editing to Eulerian graphs, J. Comput. System Sci., 82, 213, 10.1016/j.jcss.2015.10.003 Cai, 2011, Parameterized complexity of even/odd subgraph problems, J. Discrete Algorithms, 9, 231, 10.1016/j.jda.2011.03.004 Cygan, 2014, Parameterized complexity of Eulerian deletion problems, Algorithmica, 68, 41, 10.1007/s00453-012-9667-x Goyal, 2018, Finding even subgraphs even faster, J. Comput. System Sci., 97, 1, 10.1016/j.jcss.2018.03.001 Cechlárová, 2010, Computing the deficiency of housing markets with duplicate houses, vol. 6478, 72 Crowston, 2012, Parameterized Eulerian strong component arc deletion problem on tournaments, Inform. Process. Lett., 112, 249, 10.1016/j.ipl.2011.11.014 Höhn, 2012, On Eulerian extensions and their application to no-wait flowshop scheduling, J. Sched., 15, 295, 10.1007/s10951-011-0241-1 Sorge, 2011, From few components to an Eulerian graph by adding arcs, vol. 6986, 307 Sorge, 2012, A new view on rural postman based on Eulerian extension and matching, J. Discrete Algorithms, 16, 12, 10.1016/j.jda.2012.04.007 Zheleva, 2011, Social network data analytics, 277 Casas-Roma, 2017, A survey of graph-modification techniques for privacy-preserving on networks, J. Artificial Intelligence Res., 47, 341 Bazgan, 2016, Finding large degree-anonymous subgraphs is hard, Theoret. Comput. Sci., 622, 90, 10.1016/j.tcs.2016.02.004 Demaine, 2019, Structural sparsity of complex networks: Bounded expansion in random models and real-world graphs, J. Comput. System Sci., 105, 199, 10.1016/j.jcss.2019.05.004 Hartung, 2015, A refined complexity analysis of degree anonymization in graphs, Inform. and Comput., 243, 249, 10.1016/j.ic.2014.12.017 Bredereck, 2015, The complexity of degree anonymization by vertex addition, Theoret. Comput. Sci., 607, 16, 10.1016/j.tcs.2015.07.004 Talmon, 2017, The complexity of degree anonymization by graph contractions, Inform. and Comput., 256, 212, 10.1016/j.ic.2017.07.007 Golovach, 2017, Graph editing to a given degree sequence, Theoret. Comput. Sci., 665, 1, 10.1016/j.tcs.2016.12.007 Hartung, 2015, NP-hardness and fixed-parameter tractability of realizing degree sequences with directed acyclic graphs, SIAM J. Discrete Math., 29, 1931, 10.1137/130935756 Seidman, 1983, Network structure and minimum degree, Social Networks, 5, 269, 10.1016/0378-8733(83)90028-X Chitnis, 2018, Can we create large k-cores by adding few edges?, vol. 10846, 78 Li, 1992, On the minimum-cardinality-bounded-diameter and the bounded-cardinality-minimum-diameter edge addition problems, Oper. Res. Lett., 11, 303, 10.1016/0167-6377(92)90007-P Gao, 2013, The parametric complexity of graph diameter augmentation, Discrete Appl. Math., 161, 1626, 10.1016/j.dam.2013.01.016 Frati, 2015, Augmenting graphs to minimize the diameter, Algorithmica, 72, 995, 10.1007/s00453-014-9886-4 Dejter, 1993, Improving the diameter of a planar graph, Manuscript Robertson, 1995, Graph minors. XIII. The disjoint paths problem, J. Combin. Theory Ser. B, 63, 65, 10.1006/jctb.1995.1006 Lokshtanov, 2019, A strongly-uniform slicewise polynomial-time algorithm for the embedded planar diameter improvement problem, vol. 115, 25:1 Cohen, 2017, A polynomial-time algorithm for outerplanar diameter improvement, J. Comput. System Sci., 89, 315, 10.1016/j.jcss.2017.05.016 Golovach, 2015, Variants of plane diameter completion, vol. 43, 30 Kratochvíl, 1992, On the computational complexity of seidel’s switching, vol. 51, 161 Jelínková, 2011, Parameterized problems related to Seidel’s switching, Discrete Math. Theor. Comput. Sci., 13, 19 Kotzig, 1968, Eulerian lines in finite 4-valent graphs and their transformations, 219 Oum, 2005, Rank-width and vertex-minors, J. Combin. Theory Ser. B, 95, 79, 10.1016/j.jctb.2005.03.003 Cattanéo, 2015, Minimum degree up to local complementation: Bounds, parameterized complexity, and exact algorithms, vol. 9472, 259 Fomin, 2018, Partial complementation of graphs, vol. 101, 21:1 Fomin, 2018, Structured connectivity augmentation, SIAM J. Discrete Math., 32, 2612, 10.1137/17M1146233 Fomin, 2019, Modification to planarity is fixed parameter tractable, vol. 126, 28:1 Bose, 2009, Flips in planar graphs, Comput. Geom., 42, 60, 10.1016/j.comgeo.2008.04.001 Lubiw, 2015, Flip distance between two triangulations of a point set is NP-complete, Comput. Geom., 49, 17, 10.1016/j.comgeo.2014.11.001 Pilz, 2014, Flip distance between triangulations of a planar point set is APX-hard, Comput. Geom., 47, 589, 10.1016/j.comgeo.2014.01.001 Hanke, 1996, The edge-flipping distance of triangulations, J. UCS, 2, 570 Cleary, 2009, Rotation distance is fixed-parameter tractable, Inform. Process. Lett., 109, 918, 10.1016/j.ipl.2009.04.023 Sleator, 1988, Rotation distance, triangulations, and hyperbolic geometry, AMS J. Am. Math. Soc., 1, 647, 10.1090/S0894-0347-1988-0928904-4 Lucas, 2010, An improved kernel size for rotation distance in binary trees, Inform. Process. Lett., 110, 481, 10.1016/j.ipl.2010.04.022 Kanj, 2017, Computing the flip distance between triangulations, Discrete Comput. Geom., 58, 313, 10.1007/s00454-017-9867-x Feng, 2021, An improved FPT algorithm for the flip distance problem, Inform. and Comput., 281, 10.1016/j.ic.2021.104708 Easley, 2010 Sintos, 2014, Using strong triadic closure to characterize ties in social networks, 1466 Golovach, 2020, Parameterized aspects of strong subgraph closure, Algorithmica, 82, 2006, 10.1007/s00453-020-00684-9 Grüttemeier, 2020, On the relation of strong triadic closure and cluster deletion, Algorithmica, 82, 853, 10.1007/s00453-019-00617-1 Bulteau, 2021, Your rugby mates don’t need to know your colleagues: Triadic closure with edge colors, J. Comput. System Sci., 120, 75, 10.1016/j.jcss.2021.03.001 Grüttemeier, 2021, Destroying bicolored P3s by deleting few edges, Discrete Math. Theor. Comput. Sci., 23 Giannopoulou, 2021, Linear kernels for edge deletion problems to immersion-closed graph classes, SIAM J. Discrete Math., 35, 105, 10.1137/18M1228839 Fomin, 2020, On the parameterized complexity of graph modification to first-order logic properties, Theory Comput. Syst., 64, 251, 10.1007/s00224-019-09938-8