×
Crespelle, Christophe; Drange, Pål Grønås; Fomin, Fedor V.; Golovach, Petr

A survey of parameterized algorithms and the complexity of edge modification. (English) Zbl 07698754

Comput. Sci. Rev. 48, Article ID 100556, 31 p. (2023).

Cited in 4 Documents

MSC:

68R10 Graph theory (including graph drawing) in computer science
05C85 Graph algorithms (graph-theoretic aspects)
68Q27 Parameterized complexity, tractability and kernelization
68-02 Research exposition (monographs, survey articles) pertaining to computer science

Keywords:

parameterized graph algorithms; graph modification; edge modification
Cite Review PDF
Full Text: DOI arXiv
OA License

References:

[1] Lewis, John M.; Yannakakis, Mihalis, The node-deletion problem for hereditary properties is NP-complete, J. Comput. System Sci., 20, 2, 219-230 (1980) · Zbl 0436.68029
[2] Yannakakis, Mihalis, Edge-deletion problems, SIAM J. Comput., 10, 2, 297-309 (1981) · Zbl 0468.05043
[3] Burzyn, Pablo; Bonomo, Flavia; Durán, Guillermo, NP-completeness results for edge modification problems, Discrete Appl. Math., 154, 13, 1824-1844 (2006) · Zbl 1110.68094
[4] Mancini, Federico, Graph modification problems related to graph classes (2008), University of Bergen, (Ph.D. dissertation)
[5] Natanzon, Assaf; Shamir, Ron; Sharan, Roded, Complexity classification of some edge modification problems, Discrete Appl. Math., 113, 1, 109-128 (2001) · Zbl 0982.68104
[6] Yannakakis, Mihalis, Computing the minimum fill-in is NP-complete, SIAM J. Algebr. Discrete Methods, 2, 1, 77-79 (1981) · Zbl 0496.68033
[7] Eswaran, Kapali P.; Tarjan, Robert E., Augmentation problems, SIAM J. Comput., 5, 4, 653-665 (1976) · Zbl 0346.05112
[8] Shamir, Ron; Sharan, Roded; Tsur, Dekel, Cluster graph modification problems, Discrete Appl. Math., 144, 1-2, 173-182 (2004) · Zbl 1068.68107
[9] Hammer, Peter L.; Simeone, Bruno, The splittance of a graph, Combinatorica, 275-284 (1981) · Zbl 0492.05043
[10] Cygan, Marek; Fomin, Fedor V.; Kowalik, Łukasz; Lokshtanov, Daniel; Marx, Dániel; Pilipczuk, Marcin; Pilipczuk, Michał; Saurabh, Saket, Parameterized Algorithms (2015), Springer · Zbl 1334.90001
[11] Fomin, Fedor V.; Lokshtanov, Daniel; Saurabh, Saket; Zehavi, Meirav, Kernelization. Theory of Parameterized Preprocessing (2019), Cambridge University Press · Zbl 1426.68003
[12] Golovach, Petr A.; van ’t Hof, Pim; Paulusma, Daniël, Obtaining planarity by contracting few edges, Theoret. Comput. Sci., 476, 38-46 (2013) · Zbl 1260.68156
[13] Guillemot, Sylvain; Marx, Dániel, A faster FPT algorithm for bipartite contraction, Inform. Process. Lett., 113, 22-24, 906-912 (2013) · Zbl 1284.68648
[14] Guo, Chengwei; Cai, Leizhen, Obtaining split graphs by edge contraction, Theoret. Comput. Sci., 607, 60-67 (2015) · Zbl 1332.68075
[15] Heggernes, Pinar; van ’t Hof, Pim; Lokshtanov, Daniel; Paul, Christophe, Obtaining a bipartite graph by contracting few edges, SIAM J. Discrete Math., 27, 4, 2143-2156 (2013) · Zbl 1285.05167
[16] Cai, Leizhen, Parameterized complexity of vertex colouring, Discrete Appl. Math., 127, 3, 415-429 (2003) · Zbl 1015.05027
[17] Downey, Rodney G.; Fellows, Michael R., Fixed-parameter tractability and completeness, (Proceedings of the 21st Manitoba Conference on Numerical Mathematics and Computing. Proceedings of the 21st Manitoba Conference on Numerical Mathematics and Computing, Congressus Numerantium, vol. 87 (1992)), 161-178 · Zbl 0768.68136
[18] Flum, Jörg; Grohe, Martin, Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series (2006), Springer-Verlag: Springer-Verlag Berlin · Zbl 1143.68016
[19] Downey, Rodney G.; Fellows, Michael R., Fundamentals of Parameterized Complexity. Texts in Computer Science (2013), Springer · Zbl 1358.68006
[20] Grohe, Martin, Logic, graphs, and algorithms, (Logic and Automata—History and Perspectives (2007), Amsterdam University Press) · Zbl 1312.68101
[21] Niedermeier, Rolf, Invitation to fixed-parameter algorithms, (Oxford Lecture Series in Mathematics and Its Applications, vol. 31 (2006), Oxford University Press: Oxford University Press Oxford) · Zbl 1095.68038
[22] Bodlaender, Hans L.; Downey, Rodney G.; Fellows, Michael R.; Hermelin, Danny, On problems without polynomial kernels, J. Comput. System Sci., 75, 8, 423-434 (2009) · Zbl 1192.68288
[23] Impagliazzo, Russell; Paturi, Ramamohan; Zane, Francis, Which problems have strongly exponential complexity?, J. Comput. System Sci., 63, 4, 512-530 (2001) · Zbl 1006.68052
[24] Golumbic, Martin C., Algorithmic Graph Theory and Perfect Graphs (1980), Academic Press: Academic Press New York · Zbl 0541.05054
[25] Brandstädt, Andreas; Le, Van Bang; Spinrad, Jeremy P., Graph classes. A survey, (SIAM Monographs on Discrete Mathematics and Applications (1999), SIAM) · Zbl 0919.05001
[26] Kawarabayashi, Ken-ichi; Reed, Bruce A., Computing crossing number in linear time, (Proceedings of the 39th Annual ACM Symposium on Theory of Computing. Proceedings of the 39th Annual ACM Symposium on Theory of Computing, STOC (2007), ACM), 382-390 · Zbl 1232.90339
[27] Lokshtanov, Daniel, Wheel-free deletion is W[2]-hard, (Proceedings of the 3rd International Workshop on Parameterized and Exact Computation. Proceedings of the 3rd International Workshop on Parameterized and Exact Computation, IWPEC. Proceedings of the 3rd International Workshop on Parameterized and Exact Computation. Proceedings of the 3rd International Workshop on Parameterized and Exact Computation, IWPEC, Lecture Notes in Computer Science, vol. 5018 (2008), Springer), 141-147 · Zbl 1142.68366
[28] Guillemot, Sylvain; Havet, Frédéric; Paul, Christophe; Perez, Anthony, On the (non-)existence of polynomial kernels for \(P_l\)-free edge modification problems, Algorithmica, 65, 4, 900-926 (2013) · Zbl 1262.68048
[29] Cai, Yufei, Polynomial kernelisation of \(H\)-free edge modification problems (2012), The Chinese University of Hong Kong, (Master’s thesis)
[30] Fomin, Fedor V.; Villanger, Yngve, Subexponential parameterized algorithm for minimum fill-in, SIAM J. Comput., 42, 6, 2197-2216 (2013) · Zbl 1285.68055
[31] Drange, Pål Grønås; Fomin, Fedor V.; Pilipczuk, Michał; Villanger, Yngve, Exploring the subexponential complexity of completion problems, ACM Trans. Comput. Theory, 7, 4, 14:1-14:38 (2015) · Zbl 1347.68180
[32] Drange, Pål Grønås; Pilipczuk, Michał, A polynomial kernel for trivially perfect editing, Algorithmica, 80, 12, 3481-3524 (2018) · Zbl 1397.05070
[33] Cai, Leizhen, Fixed-parameter tractability of graph modification problems for hereditary properties, Inform. Process. Lett., 58, 4, 171-176 (1996) · Zbl 0875.68702
[34] Liu, Yunlong; Wang, Jianxin; Guo, Jiong, An overview of kernelization algorithms for graph modification problems, Tsinghua Sci. Technol., 19, 4, 346-357 (2014)
[35] Abu-Khzam, Faisal N., A kernelization algorithm for \(d\)-hitting set, J. Comput. System Sci., 76, 7, 524-531 (2010) · Zbl 1197.68083
[36] Guo, Jiong; Komusiewicz, Christian; Niedermeier, Rolf; Uhlmann, Johannes, A more relaxed model for graph-based data clustering: \(s\)-plex cluster editing, SIAM J. Discrete Math., 24, 4, 1662-1683 (2010) · Zbl 1221.05293
[37] Bessy, Stéphane; Perez, Anthony, Polynomial kernels for proper interval completion and related problems, Inform. and Comput., 231, 89-108 (2013) · Zbl 1358.68117
[38] Drange, Pål Grønås; Dregi, Markus F.; Lokshtanov, Daniel; Sullivan, Blair D., On the threshold of intractability, J. Comput. System Sci., 124, 1-25 (2022) · Zbl 1478.68104
[39] Bathie, Gabriel; Bousquet, Nicolas; Cao, Yixin; Ke, Yuping; Pierron, Théo, (Sub)linear kernels for edge modification problems toward structured graph classes, Algorithmica, 84, 11, 3338-3364 (2022) · Zbl 07608293
[40] Cao, Yixin; Ke, Yuping, Improved kernels for edge modification problems, (Proceedings of the 16th International Symposium on Parameterized and Exact Computation. Proceedings of the 16th International Symposium on Parameterized and Exact Computation, IPEC. Proceedings of the 16th International Symposium on Parameterized and Exact Computation. Proceedings of the 16th International Symposium on Parameterized and Exact Computation, IPEC, Leibniz International Proceedings in Informatics (LIPIcs), vol. 214 (2021), Schloss Dagstuhl — Leibniz-Zentrum für Informatik), 13:1-13:14 · Zbl 1514.68232
[41] Dumas, Maël; Perez, Anthony; Todinca, Ioan, A cubic vertex-kernel for trivially perfect editing, (Proceedings of the 46th International Symposium on Mathematical Foundations of Computer Science. Proceedings of the 46th International Symposium on Mathematical Foundations of Computer Science, MFCS. Proceedings of the 46th International Symposium on Mathematical Foundations of Computer Science. Proceedings of the 46th International Symposium on Mathematical Foundations of Computer Science, MFCS, Leibniz International Proceedings in Informatics (LIPIcs), vol. 202 (2021), Schloss Dagstuhl — Leibniz-Zentrum für Informatik), 45:1-45:14 · Zbl 07724218
[42] Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michał; van Leeuwen, Erik Jan; Wrochna, Marcin, Polynomial kernelization for removing induced claws and diamonds, Theory Comput. Syst., 60, 4, 615-636 (2017) · Zbl 1368.68222
[43] Drange, Pål Grønås, Parameterized Graph Modification Algorithms (2015), University of Bergen, (Ph.D. dissertation)
[44] Chen, Jianer; Meng, Jie, A \(2 k\) kernel for the cluster editing problem, J. Comput. System Sci., 78, 1, 211-220 (2012) · Zbl 1238.68062
[45] Cao, Yixin; Chen, Jianer, Cluster editing: Kernelization based on edge cuts, Algorithmica, 64, 1, 152-169 (2012) · Zbl 1253.68144
[46] Brügmann, Daniel; Komusiewicz, Christian; Moser, Hannes, On generating triangle-free graphs, Electron. Notes Discrete Math., 32, 51-58 (2009) · Zbl 1267.05246
[47] Yuan, Hanchun; Ke, Yuping; Cao, Yixin, Polynomial kernels for paw-free edge modification problems, Theoret. Comput. Sci., 891, 1-12 (2021) · Zbl 1514.68232
[48] Eiben, Eduard; Lochet, William; Saurabh, Saket, A polynomial kernel for paw-free editing, (Proceedings of the 15th International Symposium on Parameterized and Exact Computation. Proceedings of the 15th International Symposium on Parameterized and Exact Computation, IPEC. Proceedings of the 15th International Symposium on Parameterized and Exact Computation. Proceedings of the 15th International Symposium on Parameterized and Exact Computation, IPEC, Leibniz International Proceedings in Informatics (LIPIcs), vol. 180 (2020), Schloss Dagstuhl — Leibniz-Zentrum für Informatik), 10:1-10:15 · Zbl 07651181
[49] Sandeep, R. B.; Sivadasan, Naveen, Parameterized lower bound and improved kernel for diamond-free edge deletion, (Proceedings of the 10th International Symposium on Parameterized and Exact Computation. Proceedings of the 10th International Symposium on Parameterized and Exact Computation, IPEC. Proceedings of the 10th International Symposium on Parameterized and Exact Computation. Proceedings of the 10th International Symposium on Parameterized and Exact Computation, IPEC, Leibniz International Proceedings in Informatics (LIPIcs), vol. 43 (2015), Schloss Dagstuhl — Leibniz-Zentrum für Informatik), 365-376 · Zbl 1378.68092
[50] Cao, Yixin; Rai, Ashutosh; Sandeep, R. B.; Ye, Junjie, A polynomial kernel for diamond-free editing, Algorithmica, 84, 1, 197-215 (2022) · Zbl 1518.68253
[51] Tsur, Dekel, Kernel for \(K_t\)-free edge deletion, Inform. Process. Lett., 167, Article 106082 pp. (2021) · Zbl 1512.05377
[52] Cai, Leizhen; Cai, Yufei, Incompressibility of \(H\)-free edge modification problems, Algorithmica, 71, 3, 731-757 (2015) · Zbl 1312.68096
[53] Guo, Jiong, Problem kernels for NP-complete edge deletion problems: Split and related graphs, (Proceedings of the 18th International Symposium on Algorithms and Computation. Proceedings of the 18th International Symposium on Algorithms and Computation, ISAAC. Proceedings of the 18th International Symposium on Algorithms and Computation. Proceedings of the 18th International Symposium on Algorithms and Computation, ISAAC, Lecture Notes in Computer Science, vol. 4835 (2007), Springer), 915-926 · Zbl 1193.68194
[54] Gramm, Jens; Guo, Jiong; Hüffner, Falk; Niedermeier, Rolf, Data reduction and exact algorithms for clique cover, ACM J. Exp. Algorithmics, 13, 2.2.2-2:2.15 (2009) · Zbl 1284.05286
[55] Fellows, Michael R.; Langston, Michael A.; Rosamond, Frances A.; Shaw, Peter, Efficient parameterized preprocessing for cluster editing, (Proceedings of the International Symposium on Fundamentals of Computation Theory. Proceedings of the International Symposium on Fundamentals of Computation Theory, FCT. Proceedings of the International Symposium on Fundamentals of Computation Theory. Proceedings of the International Symposium on Fundamentals of Computation Theory, FCT, Lecture Notes in Computer Science, vol. 4639 (2007), Springer), 312-321 · Zbl 1135.68511
[56] Kratsch, Stefan; Wahlström, Magnus, Two edge modification problems without polynomial kernels, Discrete Optim., 10, 3, 193-199 (2013) · Zbl 1506.68040
[57] Nastos, James; Gao, Yong, Bounded search tree algorithms for parametrized cograph deletion: Efficient branching rules by exploiting structures of special graph classes, Discrete Math. Algorithms Appl., 4, 01, Article 1250008 pp. (2012) · Zbl 1247.05243
[58] Liu, Yunlong; Wang, Jianxin; Guo, Jiong; Chen, Jianer, Complexity and parameterized algorithms for cograph editing, Theoret. Comput. Sci., 461, 45-54 (2012) · Zbl 1253.68179
[59] Fellows, Michael R.; Guo, Jiong; Komusiewicz, Christian; Niedermeier, Rolf; Uhlmann, Johannes, Graph-based data clustering with overlaps, Discrete Optim., 8, 1, 2-17 (2011) · Zbl 1248.90070
[60] Cygan, Marek; Kowalik, Łukasz; Pilipczuk, Marcin, Open problems from Workshop on Kernels. Worker (2013)
[61] Beineke, Lowell W., Characterizations of derived graphs, J. Combin. Theory, 9, 129-135 (1970) · Zbl 0202.55702
[62] Aravind, N. R.; Sandeep, R. B.; Sivadasan, Naveen, On polynomial kernelization of \(\mathcal{H} \)-free edge deletion, Algorithmica, 79, 3, 654-666 (2017) · Zbl 1380.68211
[63] Böcker, Sebastian; Baumbach, Jan, Cluster editing, (Proceedings of the 9th Conference on Computability in Europe (CiE). Proceedings of the 9th Conference on Computability in Europe (CiE), Lecture Notes in Computer Science, vol. 7921 (2013), Springer), 33-44 · Zbl 1387.68177
[64] Gramm, Jens; Guo, Jiong; Hüffner, Falk; Niedermeier, Rolf, Graph-modeled data clustering: Exact algorithms for clique generation, Theory Comput. Syst., 38, 4, 373-392 (2005) · Zbl 1084.68117
[65] Guo, Jiong, A more effective linear kernelization for cluster editing, Theoret. Comput. Sci., 410, 8-10, 718-726 (2009) · Zbl 1162.68025
[66] Böcker, Sebastian; Damaschke, Peter, Even faster parameterized cluster deletion and cluster editing, Inform. Process. Lett., 111, 14, 717-721 (2011) · Zbl 1260.05156
[67] Böcker, Sebastian, A golden ratio parameterized algorithm for cluster editing, J. Discrete Algorithms, 16, 79-89 (2012) · Zbl 1257.05164
[68] van Bevern, René; Froese, Vincent; Komusiewicz, Christian, Parameterizing edge modification problems above lower bounds, Theory Comput. Syst., 62, 3, 739-770 (2018) · Zbl 1386.68075
[69] Li, Shaohua; Pilipczuk, Marcin; Sorge, Manuel, Cluster editing parameterized above modification-disjoint \(P_3\)-packings, (Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science. Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science, STACS. Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science. Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science, STACS, Leibniz International Proceedings in Informatics (LIPIcs), vol. 187 (2021), Schloss Dagstuhl — Leibniz-Zentrum für Informatik), 49:1-49:16
[70] Xia, Ge; Zhang, Yong, Kernelization for cycle transversal problems, Discrete Appl. Math., 160, 7-8, 1224-1231 (2012) · Zbl 1242.05142
[71] Liu, Yunlong; Wang, Jianxin; You, Jie; Chen, Jianer; Cao, Yixin, Edge deletion problems: Branching facilitated by modular decomposition, Theoret. Comput. Sci., 573, 63-70 (2015) · Zbl 1318.68128
[72] Ghosh, Esha; Kolay, Sudeshna; Kumar, Mrinal; Misra, Pranabendu; Panolan, Fahad; Rai, Ashutosh; Ramanujan, M. S., Faster parameterized algorithms for deletion to split graphs, Algorithmica, 71, 4, 989-1006 (2015) · Zbl 1325.68108
[73] Nastos, James; Gao, Yong, Familial groups in social networks, Social Networks, 35, 3, 439-450 (2013)
[74] Kaplan, Haim; Shamir, Ron; Tarjan, Robert E., Tractability of parameterized completion problems on chordal, strongly chordal, and proper interval graphs, SIAM J. Comput., 28, 5, 1906-1922 (1999) · Zbl 0928.68124
[75] Natanzon, Assaf; Shamir, Ron; Sharan, Roded, A polynomial approximation algorithm for the minimum fill-in problem, SIAM J. Comput., 30, 4, 1067-1079 (2000) · Zbl 0969.68194
[76] Agrawal, Akanksha; Lokshtanov, Daniel; Misra, Pranabendu; Saurabh, Saket; Zehavi, Meirav, Feedback vertex set inspired kernel for chordal vertex deletion, ACM Trans. Algorithms, 15, 1, 11:1-11:28 (2019) · Zbl 1454.68088
[77] Jansen, Bart M. P.; Pilipczuk, Marcin, Approximation and kernelization for chordal vertex deletion, SIAM J. Discrete Math., 32, 3, 2258-2301 (2018) · Zbl 1394.05124
[78] Cao, Yixin; Marx, Dániel, Chordal editing is fixed-parameter tractable, Algorithmica, 75, 1, 118-137 (2016) · Zbl 1344.68095
[79] Marx, Dániel, Chordal deletion is fixed-parameter tractable, Algorithmica, 57, 4, 747-768 (2010) · Zbl 1220.05066
[80] Villanger, Yngve; Heggernes, Pinar; Paul, Christophe; Telle, Jan Arne, Interval completion is fixed parameter tractable, SIAM J. Comput., 38, 5, 2007-2020 (2009) · Zbl 1227.05241
[81] Cao, Yixin, An efficient branching algorithm for interval completion (2013), CoRR, abs/1306.3181
[82] Cao, Yixin, Linear recognition of almost interval graphs, (Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms. Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA (2016), SIAM), 1096-1115 · Zbl 1410.68284
[83] Bliznets, Ivan; Fomin, Fedor V.; Pilipczuk, Marcin; Pilipczuk, Michał, Subexponential parameterized algorithm for interval completion, ACM Trans. Algorithms, 14, 3, 35:1-35:62 (2018) · Zbl 1454.68094
[84] Agrawal, Akanksha; Misra, Pranabendu; Saurabh, Saket; Zehavi, Meirav, Interval vertex deletion admits a polynomial kernel, (Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms. Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA (2019), SIAM), 1711-1730 · Zbl 1432.68185
[85] Cao, Yixin; Marx, Dániel, Interval deletion is fixed-parameter tractable, ACM Trans. Algorithms, 11, 3, 21:1-21:35 (2015) · Zbl 1398.68220
[86] Liu, Yunlong; Wang, Jianxin; Xu, Chao; Guo, Jiong; Chen, Jianer, An effective branching strategy based on structural relationship among multiple forbidden induced subgraphs, J. Comb. Optim., 29, 1, 257-275 (2015) · Zbl 1319.05127
[87] Nishimura, Naomi; Ragde, Prabhakar; Thilikos, Dimitrios M., On graph powers for leaf-labeled trees, J. Algorithms, 42, 1, 69-108 (2002) · Zbl 0990.68100
[88] Dom, Michael; Guo, Jiong; Hüffner, Falk; Niedermeier, Rolf, Error compensation in leaf power problems, Algorithmica, 44, 4, 363-381 (2006) · Zbl 1095.68080
[89] Bessy, Stéphane; Paul, Christophe; Perez, Anthony, Polynomial kernels for \(3\)-leaf power graph modification problems, Discrete Appl. Math., 158, 16, 1732-1744 (2010) · Zbl 1231.05131
[90] Dom, Michael; Guo, Jiong; Hüffner, Falk; Niedermeier, Rolf, Extending the tractability border for closest leaf powers, (Proceedings of the 31st International Workshop on Graph-Theoretic Concepts in Computer Science. Proceedings of the 31st International Workshop on Graph-Theoretic Concepts in Computer Science, WG. Proceedings of the 31st International Workshop on Graph-Theoretic Concepts in Computer Science. Proceedings of the 31st International Workshop on Graph-Theoretic Concepts in Computer Science, WG, Lecture Notes in Computer Science, vol. 3787 (2005), Springer), 397-408 · Zbl 1171.68496
[91] Dom, Michael; Guo, Jiong; Hüffner, Falk; Niedermeier, Rolf, Closest 4-leaf power is fixed-parameter tractable, Discrete Appl. Math., 156, 18, 3345-3361 (2008) · Zbl 1156.05057
[92] Dumas, Maël; Perez, Anthony; Todinca, Ioan, Polynomial kernels for strictly chordal edge modification problems, (Proceedings of the 16th International Symposium on Parameterized and Exact Computation. Proceedings of the 16th International Symposium on Parameterized and Exact Computation, IPEC. Proceedings of the 16th International Symposium on Parameterized and Exact Computation. Proceedings of the 16th International Symposium on Parameterized and Exact Computation, IPEC, Leibniz International Proceedings in Informatics (LIPIcs), vol. 214 (2021), Schloss Dagstuhl — Leibniz-Zentrum für Informatik), 17:1-17:16 · Zbl 07803595
[93] Crespelle, Christophe; Gras, Benjamin; Perez, Anthony, Completion to chordal distance-hereditary graphs: A quartic vertex-kernel, (Proceedings of the 47th International Workshop on Graph-Theoretic Concepts in Computer Science. Proceedings of the 47th International Workshop on Graph-Theoretic Concepts in Computer Science, WG. Proceedings of the 47th International Workshop on Graph-Theoretic Concepts in Computer Science. Proceedings of the 47th International Workshop on Graph-Theoretic Concepts in Computer Science, WG, Lecture Notes in Computer Science, vol. 12911 (2021), Springer), 156-168 · Zbl 07538574
[94] Courcelle, Bruno; Makowsky, Johann A.; Rotics, Udi, On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic, Discrete Appl. Math., 108, 1-2, 23-52 (2001) · Zbl 0972.05023
[95] Kim, Eun Jung; Kwon, O-joung, A polynomial kernel for distance-hereditary vertex deletion, Algorithmica, 83, 7, 2096-2141 (2021) · Zbl 1522.68245
[96] Robertson, Neil; Seymour, Paul D., Graph minors. XX. Wagner’s conjecture, J. Combin. Theory Ser. B, 92, 2, 325-357 (2004) · Zbl 1061.05088
[97] Robertson, Neil; Seymour, Paul D., Graph minors. XI. Circuits on a surface, J. Combin. Theory Ser. B, 60, 1, 72-106 (1994) · Zbl 0799.05016
[98] Adler, Isolde; Grohe, Martin; Kreutzer, Stephan, Computing excluded minors, (Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms. Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA (2008), SIAM), 641-650 · Zbl 1192.68810
[99] Fomin, Fedor V.; Lokshtanov, Daniel; Misra, Neeldhara; Saurabh, Saket, Planar \(F\)-deletion: Approximation, kernelization and optimal FPT algorithms, (Proceedings of the 53rd Annual Symposium on Foundations of Computer Science. Proceedings of the 53rd Annual Symposium on Foundations of Computer Science, FOCS (2012), IEEE), 470-479
[100] Reed, Bruce A.; Smith, Kaleigh; Vetta, Adrian, Finding odd cycle transversals, Oper. Res. Lett., 32, 4, 299-301 (2004) · Zbl 1052.05061
[101] Wernicke, Sebastian, On the algorithmic tractability of single nucleotide polymorphism (SNP) analysis and related problems, (Diplomarbeit (2003), WSI für Informatik, Universität Tübingen)
[102] Guo, Jiong; Gramm, Jens; Hüffner, Falk; Niedermeier, Rolf; Wernicke, Sebastian, Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization, J. Comput. System Sci., 72, 8, 1386-1396 (2006) · Zbl 1119.68134
[103] Pilipczuk, Marcin; Pilipczuk, Michał; Wrochna, Marcin, Edge bipartization faster than \(2^k\), Algorithmica, 81, 3, 917-966 (2019) · Zbl 1418.68171
[104] Kratsch, Stefan; Wahlström, Magnus, Compression via matroids: A randomized polynomial kernel for odd cycle transversal, ACM Trans. Algorithms, 10, 4, 20 (2014) · Zbl 1398.68250
[105] Feng, Qilong; Zhou, Qian; Li, Shaohua, Randomized parameterized algorithms for co-path set problem, (Proceedings of the Annual International Workshop Frontiers in Algorithmics. Proceedings of the Annual International Workshop Frontiers in Algorithmics, FAW. Proceedings of the Annual International Workshop Frontiers in Algorithmics. Proceedings of the Annual International Workshop Frontiers in Algorithmics, FAW, Lecture Notes in Computer Science, vol. 8497 (2014), Springer), 82-93 · Zbl 1407.68534
[106] van ’t Hof, Pim; Villanger, Yngve, Proper interval vertex deletion, Algorithmica, 65, 4, 845-867 (2013) · Zbl 1262.68052
[107] Heggernes, Pinar; van ’t Hof, Pim; Jansen, Bart M. P.; Kratsch, Stefan; Villanger, Yngve, Parameterized complexity of vertex deletion into perfect graph classes, Theoret. Comput. Sci., 511, 172-180 (2013) · Zbl 1407.68223
[108] Marx, Dániel, What’s next? Future directions in parameterized complexity, (The Multivariate Algorithmic Revolution and beyond — Essays Dedicated To Michael R. Fellows on the Occasion of His 60th Birthday. The Multivariate Algorithmic Revolution and beyond — Essays Dedicated To Michael R. Fellows on the Occasion of His 60th Birthday, Lecture Notes in Computer Science, vol. 7370 (2012), Springer), 469-496 · Zbl 1358.68143
[109] Demaine, Erik D.; Fomin, Fedor V.; Hajiaghayi, MohammadTaghi; Thilikos, Dimitrios M., Subexponential parameterized algorithms on bounded-genus graphs and \(H\)-minor-free graphs, J. ACM, 52, 6, 866-893 (2005) · Zbl 1326.05152
[110] Bodlaender, Hans L.; Demaine, Erik D.; Fellows, Michael R.; Guo, Jiong; Hermelin, Danny; Lokshtanov, Daniel; Müller, Moritz; Raman, Venkatesh; van Rooij, Johan; Rosamond, Frances A., Open problems in parameterized and exact computation from IWPEC 2008 (2008), Department of Information and Computing Sciences, Utrecht University
[111] Alon, Noga; Lokshtanov, Daniel; Saurabh, Saket, Fast FAST, (Proceedings of the 36th International Colloquium of Automata, Languages and Programming. Proceedings of the 36th International Colloquium of Automata, Languages and Programming, ICALP. Proceedings of the 36th International Colloquium of Automata, Languages and Programming. Proceedings of the 36th International Colloquium of Automata, Languages and Programming, ICALP, Lecture Notes in Computer Science, vol. 5555 (2009), Springer), 49-58 · Zbl 1248.68547
[112] Dom, Michael; Guo, Jiong; Hüffner, Falk; Niedermeier, Rolf; Truß, Anke, Fixed-parameter tractability results for feedback set problems in tournaments, J. Discrete Algorithms, 8, 1, 76-86 (2010) · Zbl 1191.68349
[113] Bessy, Stéphane; Fomin, Fedor V.; Gaspers, Serge; Paul, Christophe; Perez, Anthony; Saurabh, Saket; Thomassé, Stéphan, Kernels for feedback arc set in tournaments, J. Comput. System Sci., 77, 6, 1071-1078 (2011) · Zbl 1235.05134
[114] Bodlaender, Hans L.; Heggernes, Pinar; Villanger, Yngve, Faster parameterized algorithms for minimum fill-in, Algorithmica, 61, 4, 817-838 (2011) · Zbl 1230.68100
[115] Bouchitté, Vincent; Todinca, Ioan, Treewidth and minimum fill-in: Grouping the minimal separators, SIAM J. Comput., 31, 1, 212-232 (2001) · Zbl 0987.05085
[116] Bouchitté, Vincent; Todinca, Ioan, Listing all potential maximal cliques of a graph, Theoret. Comput. Sci., 276, 1-2, 17-32 (2002) · Zbl 1002.68104
[117] Fomin, Fedor V.; Kratsch, Dieter; Todinca, Ioan; Villanger, Yngve, Exact algorithms for treewidth and minimum fill-in, SIAM J. Comput., 38, 3, 1058-1079 (2008) · Zbl 1163.05320
[118] Komusiewicz, Christian; Uhlmann, Johannes, Cluster editing with locally bounded modifications, Discrete Appl. Math., 160, 15, 2259-2270 (2012) · Zbl 1252.05178
[119] Drange, Pål Grønås; Reidl, Felix; Villaamil, Fernando S.; Sikdar, Somnath, Fast biclustering by dual parameterization, (Proceedings of the 10th International Symposium on Parameterized and Exact Computation. Proceedings of the 10th International Symposium on Parameterized and Exact Computation, IPEC. Proceedings of the 10th International Symposium on Parameterized and Exact Computation. Proceedings of the 10th International Symposium on Parameterized and Exact Computation, IPEC, Leibniz International Proceedings in Informatics (LIPIcs), vol. 43 (2015), Schloss Dagstuhl — Leibniz-Zentrum für Informatik), 402-413 · Zbl 1378.68072
[120] Bliznets, Ivan; Cygan, Marek; Komosa, Paweł; Pilipczuk, Michał; Mach, Lukáš, Lower bounds for the parameterized complexity of minimum fill-in and other completion problems, ACM Trans. Algorithms, 16, 2, 1-31 (2020) · Zbl 1484.68152
[121] Damaschke, Peter; Mogren, Olof, Editing simple graphs, J. Graph Algorithms Appl., 18, 4, 557-576 (2014) · Zbl 1305.05220
[122] Aravind, N. R.; Sandeep, R. B.; Sivadasan, Naveen, Dichotomy results on the hardness of \(H\)-free edge modification problems, SIAM J. Discrete Math., 31, 1, 542-561 (2017) · Zbl 1370.68225
[123] Fomin, Fedor V.; Kratsch, Stefan; Pilipczuk, Marcin; Pilipczuk, Michał; Villanger, Yngve, Tight bounds for parameterized complexity of cluster editing with a small number of clusters, J. Comput. System Sci., 80, 7, 1430-1447 (2014) · Zbl 1311.68076
[124] Bliznets, Ivan; Fomin, Fedor V.; Pilipczuk, Marcin; Pilipczuk, Michał, A subexponential parameterized algorithm for proper interval completion, SIAM J. Discrete Math., 29, 4, 1961-1987 (2015) · Zbl 1330.68102
[125] Bodlaender, Hans L.; Heggernes, Pinar; Lokshtanov, Daniel, Graph modification problems (Dagstuhl Seminar 14071), Dagstuhl Rep., 4, 2, 38-59 (2014)
[126] Borgatti, Stephen P.; Everett, Martin G., Models of core/periphery structures, Social Networks, 21, 4, 375-395 (2000)
[127] Kovác, Ivan; Selecéniová, Ivana; Steinová, Monika, On the clique editing problem, (Proceedings of the 39th International Symposium on Mathematical Foundations of Computer Science. Proceedings of the 39th International Symposium on Mathematical Foundations of Computer Science, MFCS. Proceedings of the 39th International Symposium on Mathematical Foundations of Computer Science. Proceedings of the 39th International Symposium on Mathematical Foundations of Computer Science, MFCS, Lecture Notes in Computer Science, vol. 8635 (2014), Springer), 469-480 · Zbl 1426.68220
[128] Meesum, Syed Mohammad; Misra, Pranabendu; Saurabh, Saket, Reducing rank of the adjacency matrix by graph modification, Theoret. Comput. Sci., 654, 70-79 (2016) · Zbl 1353.05117
[129] Meesum, Syed Mohammad; Saurabh, Saket, Rank reduction of oriented graphs by vertex and edge deletions, Algorithmica, 80, 10, 2757-2776 (2018) · Zbl 1391.68091
[130] Cao, Yixin; Sandeep, R. B., Minimum fill-in: Inapproximability and almost tight lower bounds, Inform. and Comput., 271, Article 104514 pp. (2020) · Zbl 1435.68111
[131] Cao, Yixin, Unit interval editing is fixed-parameter tractable, Inform. and Comput., 253, 109-126 (2017) · Zbl 1359.68230
[132] Bliznets, Ivan; Cygan, Marek; Komosa, Paweł; Pilipczuk, Michał, Hardness of approximation for \(H\)-free edge modification problems, ACM Trans. Comput. Theory, 10, 2, 9:1-9:32 (2018) · Zbl 1427.68105
[133] Chen, Yijia; Flum, Jörg; Müller, Moritz, Lower bounds for kernelizations and other preprocessing procedures, Theory Comput. Syst., 48, 4, 803-839 (2011) · Zbl 1234.68118
[134] Fernau, Henning; Fluschnik, Till; Hermelin, Danny; Krebs, Andreas; Molter, Hendrik; Niedermeier, Rolf, Diminishable parameterized problems and strict polynomial kernelization, Computability, 9, 1, 1-24 (2020) · Zbl 1485.68117
[135] Chen, Duhong; Eulenstein, Oliver; Fernández-Baca, David; Sanderson, Michael J., Minimum-flip supertrees: Complexity and algorithms, IEEE/ACM Trans. Comput. Biol. Bioinform., 3, 2, 165-173 (2006)
[136] Böcker, Sebastian; Bui, Quang Bao Anh; Truß, Anke, Improved fixed-parameter algorithms for minimum-flip consensus trees, ACM Trans. Algorithms, 8, 1 (2012) · Zbl 1295.68128
[137] Komusiewicz, Christian; Uhlmann, Johannes, A cubic-vertex kernel for flip consensus tree, Algorithmica, 68, 1, 81-108 (2014) · Zbl 1290.68047
[138] Guo, Jiong; Hüffner, Falk; Komusiewicz, Christian; Zhang, Yong, Improved algorithms for bicluster editing, (Proceedings of Theory and Applications of Models of Computation. Proceedings of Theory and Applications of Models of Computation, TAMC. Proceedings of Theory and Applications of Models of Computation. Proceedings of Theory and Applications of Models of Computation, TAMC, Lecture Notes in Computer Science, vol. 4978 (2008), Springer), 445-456 · Zbl 1139.68420
[139] Tsur, Dekel, Faster parameterized algorithm for bicluster editing, Inform. Process. Lett., 168, Article 106095 pp. (2021) · Zbl 1512.05378
[140] Fernau, Henning, Two-layer planarization: Improving on parameterized algorithmics, J. Graph Algorithms Appl., 9, 2, 205-238 (2005) · Zbl 1108.68062
[141] Fernau, Henning; Fomin, Fedor V.; Lokshtanov, Daniel; Mnich, Matthias; Philip, Geevarghese; Saurabh, Saket, Social choice meets graph drawing: how to get subexponential time algorithms for ranking and drawing problems, Tsinghua Sci. Technol., 19, 4, 374-386 (2014)
[142] Kobayashi, Yasuaki; Tamaki, Hisao, A fast and simple subexponential fixed parameter algorithm for one-sided crossing minimization, Algorithmica, 72, 3, 778-790 (2015) · Zbl 1328.68151
[143] Zehavi, Meirav, Parameterized analysis and crossing minimization problems, Comp. Sci. Rev., 45, Article 100490 pp. (2022) · Zbl 1507.68232
[144] Lokshtanov, Daniel; Narayanaswamy, N. S.; Raman, Venkatesh; Ramanujan, M. S.; Saurabh, Saket, Faster parameterized algorithms using linear programming, ACM Trans. Algorithms, 11, 2, 15 (2014) · Zbl 1398.68254
[145] Cygan, Marek; Kowalik, Łukasz; Pilipczuk, Marcin, Open problems from Update Meeting on Graph Separation Problems. Graph Cuts (2013)
[146] Majumdar, Diptapriyo; Neogi, Rian; Raman, Venkatesh; Vaishali, S., Tractability of Kőnig edge deletion problems, Theoret. Comput. Sci., 796, 207-215 (2019) · Zbl 1435.68125
[147] Bock, Adrian; Chandrasekaran, Karthekeyan; Könemann, Jochen; Peis, Britta; Sanitá, Laura, Finding small stabilizers for unstable graphs, Math. Program., 154, 1, 173-196 (2015) · Zbl 1337.05085
[148] Jr., Lester R. Ford; Fulkerson, Delbert R., Maximal flow through a network, Canad. J. Math., 8, 399-404 (1956) · Zbl 0073.40203
[149] Dahlhaus, Elias; Johnson, David S.; Papadimitriou, Christos H.; Seymour, Paul D.; Yannakakis, Mihalis, The complexity of multiterminal cuts, SIAM J. Comput., 23, 4, 864-894 (1994) · Zbl 0809.68075
[150] Marx, Dániel, Parameterized graph separation problems, Theoret. Comput. Sci., 351, 3, 394-406 (2006) · Zbl 1086.68104
[151] Xiao, Mingyu, Simple and improved parameterized algorithms for multiterminal cuts, Theory Comput. Syst., 46, 4, 723-736 (2010) · Zbl 1213.68472
[152] Cao, Yixin; Chen, Jianer; Fan, Jia-Hao, An \(O^\ast ( 1 . 8 4^k )\) parameterized algorithm for the multiterminal cut problem, Inform. Process. Lett., 114, 4, 167-173 (2014) · Zbl 1302.68210
[153] Klein, Philip N.; Marx, Dániel, Solving planar \(k\)-terminal cut in \(\mathcal{O} ( n^{c \sqrt{ k}} )\) time, (Proceedings of the 39th International Colloquium of Automata, Languages and Programming. Proceedings of the 39th International Colloquium of Automata, Languages and Programming, ICALP. Proceedings of the 39th International Colloquium of Automata, Languages and Programming. Proceedings of the 39th International Colloquium of Automata, Languages and Programming, ICALP, Lecture Notes in Computer Science, vol. 7391 (2012), Springer), 569-580 · Zbl 1272.68157
[154] Lokshtanov, Daniel; Ramanujan, M. S., Parameterized tractability of multiway cut with parity constraints, (Proceedings of the 39th International Colloquium of Automata, Languages and Programming. Proceedings of the 39th International Colloquium of Automata, Languages and Programming, ICALP. Proceedings of the 39th International Colloquium of Automata, Languages and Programming. Proceedings of the 39th International Colloquium of Automata, Languages and Programming, ICALP, Lecture Notes in Computer Science, vol. 7391 (2012), Springer), 750-761 · Zbl 1272.68146
[155] Chandrasekaran, Karthekeyan; Mnich, Matthias; Mozaffari, Sahand, Odd multiway cut in directed acyclic graphs, SIAM J. Discrete Math., 34, 2, 1385-1408 (2020) · Zbl 1443.68123
[156] Chitnis, Rajesh H.; Hajiaghayi, MohammadTaghi; Marx, Dániel, Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset, SIAM J. Comput., 42, 4, 1674-1696 (2013) · Zbl 1312.68097
[157] Chen, Jianer; Liu, Yang; Lu, Songjian; O’Sullivan, Barry; Razgon, Igor, A fixed-parameter algorithm for the directed feedback vertex set problem, J. ACM, 55, 5 (2008) · Zbl 1231.68149
[158] Even, Guy; Naor, Joseph (Seffi); Schieber, Baruch; Sudan, Madhu, Approximating minimum feedback sets and multicuts in directed graphs, Algorithmica, 20, 2, 151-174 (1998) · Zbl 0897.68078
[159] Chitnis, Rajesh H.; Cygan, Marek; Hajiaghayi, MohammadTaghi; Marx, Dániel, Directed subset feedback vertex set is fixed-parameter tractable, ACM Trans. Algorithms, 11, 4, 28 (2015) · Zbl 1398.68222
[160] Xiao, Mingyu; Nagamochi, Hiroshi, An FPT algorithm for edge subset feedback edge set, Inform. Process. Lett., 112, 1-2, 5-9 (2012) · Zbl 1233.68142
[161] Kratsch, Stefan; Li, Shaohua; Marx, Dániel; Pilipczuk, Marcin; Wahlström, Magnus, Multi-budgeted directed cuts, Algorithmica, 82, 8, 2135-2155 (2020) · Zbl 1477.68236
[162] Claudio, L. Lucchesi; Younger, Daniel Haven, A minimax theorem for directed graphs, J. Lond. Math. Soc., 2-17, 3, 369-374 (1978) · Zbl 0392.05029
[163] Garg, Naveen; Vazirani, Vijay V.; Yannakakis, Mihalis, Primal-dual approximation algorithms for integral flow and multicut in trees, Algorithmica, 18, 1, 3-20 (1997) · Zbl 0873.68075
[164] Guo, Jiong; Niedermeier, Rolf, Fixed-parameter tractability and data reduction for multicut in trees, Networks, 46, 3, 124-135 (2005) · Zbl 1081.68070
[165] Bousquet, Nicolas; Daligault, Jean; Thomassé, Stéphan, Multicut is FPT, SIAM J. Comput., 47, 1, 166-207 (2018) · Zbl 1380.05184
[166] Marx, Dániel; Razgon, Igor, Fixed-parameter tractability of multicut parameterized by the size of the cutset, SIAM J. Comput., 43, 2, 355-388 (2014) · Zbl 1304.68078
[167] Pilipczuk, Marcin; Wahlström, Magnus, Directed multicut is W[1]-hard, even for four terminal pairs, ACM Trans. Comput. Theory, 10, 3, 1-18 (2018) · Zbl 1427.68252
[168] Kratsch, Stefan; Pilipczuk, Marcin; Pilipczuk, Michał; Wahlström, Magnus, Fixed-parameter tractability of multicut in directed acyclic graphs, SIAM J. Discrete Math., 29, 1, 122-144 (2015) · Zbl 1326.05053
[169] Chitnis, Rajesh H.; Feldmann, Andreas E., FPT inapproximability of directed cut and connectivity problems, (Proceedings of the 14th International Symposium on Parameterized and Exact Computation. Proceedings of the 14th International Symposium on Parameterized and Exact Computation, IPEC. Proceedings of the 14th International Symposium on Parameterized and Exact Computation. Proceedings of the 14th International Symposium on Parameterized and Exact Computation, IPEC, Leibniz International Proceedings in Informatics (LIPIcs), vol. 148 (2019), Schloss Dagstuhl — Leibniz-Zentrum für Informatik), 8:1-8:20 · Zbl 07650216
[170] Bringmann, Karl; Hermelin, Danny; Mnich, Matthias; van Leeuwen, Erik Jan, Parameterized complexity dichotomy for Steiner Multicut, J. Comput. System Sci., 82, 6, 1020-1043 (2016) · Zbl 1342.68155
[171] Golovach, Petr A.; Thilikos, Dimitrios M., Paths of bounded length and their cuts: Parameterized complexity and algorithms, Discrete Optim., 8, 1, 72-86 (2011) · Zbl 1248.90071
[172] Fluschnik, Till; Hermelin, Danny; Nichterlein, André; Niedermeier, Rolf, Fractals for kernelization lower bounds, SIAM J. Discrete Math., 32, 1, 656-681 (2018) · Zbl 1388.68112
[173] Dvorák, Pavel; Knop, Dusan, Parameterized complexity of length-bounded cuts and multicuts, Algorithmica, 80, 12, 3597-3617 (2018) · Zbl 1400.90258
[174] Bazgan, Cristina; Fluschnik, Till; Nichterlein, André; Niedermeier, Rolf; Stahlberg, Maximilian, A more fine-grained complexity analysis of finding the most vital edges for undirected shortest paths, Networks, 73, 1, 23-37 (2019) · Zbl 1407.90090
[175] Bentert, Matthias; Heeger, Klaus; Knop, Dušan, Length-bounded cuts: Proper interval graphs and structural parameters, J. Comput. System Sci., 126, 21-43 (2022) · Zbl 1505.68032
[176] Kolman, Petr, On algorithms employing treewidth for \(L\)-bounded cut problems, J. Graph Algorithms Appl., 22, 2, 177-191 (2018) · Zbl 1384.05147
[177] Fan, Chenglin; Raichel, Benjamin; Van Buskirk, Gregory, Metric violation distance: Hardness and approximation, Algorithmica, 84, 5, 1441-1465 (2022) · Zbl 1537.68042
[178] Fan, Chenglin; Raichel, Benjamin; Van Buskirk, Gregory, Metric violation distance: Revisited and extended (2018), CoRR, abs/1807.08078
[179] Fan, Chenglin; Gilbert, Anna C.; Raichel, Benjamin; Sonthalia, Rishi; Van Buskirk, Gregory, Generalized metric repair on graphs, (Proceedings of the 17th Scandinavian Symposium and Workshops on Algorithm Theory. Proceedings of the 17th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT. Proceedings of the 17th Scandinavian Symposium and Workshops on Algorithm Theory. Proceedings of the 17th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT, Leibniz International Proceedings in Informatics (LIPIcs), vol. 162 (2020), Schloss Dagstuhl — Leibniz-Zentrum für Informatik), 25:1-25:22 · Zbl 07759293
[180] Lokshtanov, Daniel; Marx, Dániel, Clustering with local restrictions, Inform. and Comput., 222, 278-292 (2013) · Zbl 1266.05122
[181] Fomin, Fedor V.; Golovach, Petr A.; Korhonen, Janne H., On the parameterized complexity of cutting a few vertices from a graph, (Proceedings of the 38th International Symposium on Mathematical Foundations of Computer Science. Proceedings of the 38th International Symposium on Mathematical Foundations of Computer Science, MFCS. Proceedings of the 38th International Symposium on Mathematical Foundations of Computer Science. Proceedings of the 38th International Symposium on Mathematical Foundations of Computer Science, MFCS, Lecture Notes in Computer Science, vol. 8087 (2013), Springer), 421-432 · Zbl 1398.68231
[182] Cygan, Marek; Lokshtanov, Daniel; Pilipczuk, Marcin; Pilipczuk, Michał; Saurabh, Saket, Minimum bisection is fixed-parameter tractable, SIAM J. Comput., 48, 2, 417-450 (2019) · Zbl 1421.68069
[183] van Bevern, René; Feldmann, Andreas E.; Sorge, Manuel; Suchý, Ondrej, On the parameterized complexity of computing graph bisections, (Proceedings of the 39th International Workshop on Graph-Theoretic Concepts in Computer Science. Proceedings of the 39th International Workshop on Graph-Theoretic Concepts in Computer Science, WG. Proceedings of the 39th International Workshop on Graph-Theoretic Concepts in Computer Science. Proceedings of the 39th International Workshop on Graph-Theoretic Concepts in Computer Science, WG, Lecture Notes in Computer Science, vol. 8165 (2013), Springer), 76-87 · Zbl 1318.68098
[184] Kim, Eun Jung; Paul, Christophe; Sau, Ignasi; Thilikos, Dimitrios M., Parameterized algorithms for min-max multiway cut and list digraph homomorphism, J. Comput. System Sci., 86, 191-206 (2017) · Zbl 1370.68131
[185] Chitnis, Rajesh H.; Egri, László; Marx, Dániel, List \(H\)-coloring a graph by removing few vertices, Algorithmica, 78, 1, 110-146 (2017) · Zbl 1361.05085
[186] 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. · Zbl 07774390
[187] Downey, Rodney G.; Estivill-Castro, Vladimir; Fellows, Michael R.; Prieto, Elena; Rosamond, Frances A., Cutting up is hard to do: the parameterised complexity of \(k\)-cut and related problems, Electron. Notes Theor. Comput. Sci., 78, 209-222 (2003) · Zbl 1270.68112
[188] ichi Kawarabayashi, Ken; Thorup, Mikkel, The minimum \(k\)-way cut of bounded size is fixed-parameter tractable, (Proceedings of the 52nd Annual Symposium on Foundations of Computer Science. Proceedings of the 52nd Annual Symposium on Foundations of Computer Science, FOCS (2011), IEEE Computer Society), 160-169 · Zbl 1292.68094
[189] Marx, Dániel; O’Sullivan, Barry; Razgon, Igor, Finding small separators in linear time via treewidth reduction, ACM Trans. Algorithms, 9, 4, 30:1-30:35 (2013) · Zbl 1301.05337
[190] Komusiewicz, Christian; Kratsch, Dieter; Le, Van Bang, Matching cut: Kernelization, single-exponential time FPT, and exact exponential algorithms, Discrete Appl. Math., 283, 44-58 (2020) · Zbl 1442.05224
[191] Gomes, Guilherme; Sau, Ignasi, Finding cuts of bounded degree: Complexity, FPT and exact algorithms, and kernelization, Algorithmica, 83, 6, 1677-1706 (2021) · Zbl 1516.68062
[192] Ray, Sibabrata; Deogun, Jitender S., Computational complexity of weighted integrity, J. Combin. Math. Combin. Comput., 16, 65-73 (1994) · Zbl 0817.05039
[193] Drange, Pål Grønås; Dregi, Markus F.; van ’t Hof, Pim, On the computational complexity of vertex integrity and component order connectivity, Algorithmica, 76, 4, 1181-1202 (2016) · Zbl 1355.68115
[194] Gross, Daniel; Heinig, Monika; Iswara, Lakshmi; William Kazmierczak, L.; Luttrell, Kristi; Saccoman, John T.; Suffel, Charles, A survey of component order connectivity models of graph theoretic networks, WSEAS Trans. Math., 12, 9, 895-910 (2013)
[195] Clark, Lane H.; Entringer, Roger C.; Fellows, Michael R., Computational complexity of integrity, J. Combin. Math. Combin. Comput., 2, 179-191 (1987) · Zbl 0636.05033
[196] Fellows, Michael R.; immersion order, Sam Stueckle. The, Forbidden subgraphs and the complexity of network integrity, J. Combin. Math. Combin. Comput., 6, 23-32 (1989) · Zbl 0691.05026
[197] Barefoot, Curtis A.; Entringer, Roger; Swart, Henda, Vulnerability in graphs — a comparative survey, J. Combin. Math. Combin. Comput., 1, 38, 13-22 (1987) · Zbl 0646.05042
[198] Bang-Jensen, Jørgen; Eiben, Eduard; Gutin, Gregory; Wahlström, Magnus; Yeo, Anders, Component order connectivity in directed graphs, Algorithmica, 84, 9, 2767-2784 (2022) · Zbl 1533.68099
[199] Bagga, Kunwarjit S.; Beineke, Lowell W.; Lipman, Marc J.; Pippert, Raymond E., Edge-integrity: a survey, Discrete Math., 124, 1-3, 3-12 (1994) · Zbl 0796.05061
[200] Kratsch, Dieter; Kloks, Ton; Müller, Haiko, Measuring the vulnerability for classes of intersection graphs, Discrete Appl. Math., 77, 3, 259-270 (1997) · Zbl 0881.05118
[201] Watanabe, Toshimasa; Nakamura, Akira, Edge-connectivity augmentation problems, J. Comput. System Sci., 35, 1, 96-144 (1987) · Zbl 0622.68057
[202] Cai, Guo-Ray; Sun, Yu-Geng, The minimum augmentation of any graph to a \(k\)-edge-connected graph, Networks, 19, 1, 151-172 (1989) · Zbl 0672.05057
[203] Frank, András, Augmenting graphs to meet edge-connectivity requirements, SIAM J. Discrete Math., 5, 1, 25-53 (1992) · Zbl 0782.05054
[204] Vegh, László A., Augmenting undirected node-connectivity by one, SIAM J. Discrete Math., 25, 2, 695-718 (2011) · Zbl 1294.05107
[205] Jackson, Bill; Jordán, Tibor, Independence free graphs and vertex connectivity augmentation, J. Combin. Theory Ser. B, 94, 1, 31-77 (2005) · Zbl 1059.05064
[206] Nagamochi, Hiroshi, An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree, Discrete Appl. Math., 126, 1, 83-113 (2003) · Zbl 1012.68226
[207] Guo, Jiong; Uhlmann, Johannes, Kernelization and complexity results for connectivity augmentation problems, Networks, 56, 2, 131-142 (2010) · Zbl 1213.68453
[208] Marx, Dániel; Végh, László A., Fixed-parameter algorithms for minimum-cost edge-connectivity augmentation, ACM Trans. Algorithms, 11, 4, 27 (2015) · Zbl 1398.68255
[209] Basavaraju, Manu; Fomin, Fedor V.; Golovach, Petr A.; Misra, Pranabendu; Ramanujan, M. S.; Saurabh, Saket, Parameterized algorithms to preserve connectivity, (Proceedings of the 41st International Colloquium on Automata, Languages, and Programming. Proceedings of the 41st International Colloquium on Automata, Languages, and Programming, ICALP. Proceedings of the 41st International Colloquium on Automata, Languages, and Programming. Proceedings of the 41st International Colloquium on Automata, Languages, and Programming, ICALP, Lecture Notes in Computer Science, vol. 8572 (2014), Springer), 800-811 · Zbl 1412.68078
[210] Hüffner, Falk; Komusiewicz, Christian; Sorge, Manuel, Finding highly connected subgraphs, (Proceedings of the Conference on Current Trends in Theory and Practice of Computer Science. Proceedings of the Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM. Proceedings of the Conference on Current Trends in Theory and Practice of Computer Science. Proceedings of the Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM, Lecture Notes in Computer Science, vol. 8939 (2015), Springer), 254-265 · Zbl 1432.68358
[211] Adler, Isolde; Kolliopoulos, Stavros G.; Thilikos, Dimitrios M., Planar disjoint-paths completion, Algorithmica, 76, 2, 401-425 (2016) · Zbl 1350.68121
[212] Gutin, Gregory Z.; Ramanujan, M. S.; Reidl, Felix; Wahlström, Magnus, Path-contractions, edge deletions and connectivity preservation, J. Comput. System Sci., 101, 1-20 (2019) · Zbl 1412.68084
[213] Liu, Hong; Zhang, Peng; Zhu, Daming, On editing graphs into \(2\)-club clusters, (Proceedings of Joint International Conference Frontiers in Algorithmics and Algorithmic Aspects in Information and Management (FAW-AAIM), vol. 7285 (2012), Springer), 235-246 · Zbl 1304.68063
[214] Abu-Khzam, Faisal N., On the complexity of multi-parameterized cluster editing, J. Discrete Algorithms, 45, 26-34 (2017) · Zbl 1419.68056
[215] Misra, Neeldhara; Panolan, Fahad; Saurabh, Saket, Subexponential algorithm for \(d\)-cluster edge deletion: Exception or rule?, J. Comput. System Sci., 113, 150-162 (2020) · Zbl 1445.68171
[216] Hüffner, Falk; Komusiewicz, Christian; Liebtrau, Adrian; Niedermeier, Rolf, Partitioning biological networks into highly connected clusters with maximum edge coverage, IEEE/ACM Trans. Comput. Biol. Bioinform., 11, 3, 455-467 (2014)
[217] Bliznets, Ivan; Karpov, Nikolay, Parameterized algorithms for partitioning graphs into highly connected clusters, (Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science. Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science, MFCS. Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science. Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science, MFCS, Leibniz International Proceedings in Informatics (LIPIcs), vol. 83 (2017), Schloss Dagstuhl — Leibniz-Zentrum für Informatik), 6:1-6:14 · Zbl 1441.68105
[218] Golovach, Petr A.; Thilikos, Dimitrios M., Clustering to given connectivities, (Proceedings of the 14th International Symposium on Parameterized and Exact Computation. Proceedings of the 14th International Symposium on Parameterized and Exact Computation, IPEC. Proceedings of the 14th International Symposium on Parameterized and Exact Computation. Proceedings of the 14th International Symposium on Parameterized and Exact Computation, IPEC, Leibniz International Proceedings in Informatics (LIPIcs), vol. 115 (2019), Schloss Dagstuhl — Leibniz-Zentrum für Informatik), 17:1-19:17 · Zbl 07650226
[219] Böcker, Sebastian; Briesemeister, Sebastian; Bui, Quang Bao Anh; Truß, Anke, Going weighted: Parameterized algorithms for cluster editing, Theoret. Comput. Sci., 410, 52, 5467-5480 (2009) · Zbl 1178.68373
[220] Luo, Junjie; Molter, Hendrik; Nichterlein, André; Niedermeier, Rolf, Parameterized dynamic cluster editing, Algorithmica, 83, 1, 1-44 (2021) · Zbl 1508.68268
[221] Chen, Jiehua; Molter, Hendrik; Sorge, Manuel; Suchý, Ondrej, Cluster editing in multi-layer and temporal graphs, (Proceedings of the 29th International Symposium on Algorithms and Computation. Proceedings of the 29th International Symposium on Algorithms and Computation, ISAAC. Proceedings of the 29th International Symposium on Algorithms and Computation. Proceedings of the 29th International Symposium on Algorithms and Computation, ISAAC, Leibniz International Proceedings in Informatics (LIPIcs), vol. 123 (2018), Schloss Dagstuhl — Leibniz-Zentrum für Informatik), 24:1-24:13 · Zbl 1533.68219
[222] Bocci, Cristiano; Capresi, Chiara; Meeks, Kitty; Sylvester, John, A new temporal interpretation of cluster editing, (Proceedings of the 33rd International Workshop on Combinatorial Algorithms. Proceedings of the 33rd International Workshop on Combinatorial Algorithms, IWOCA. Proceedings of the 33rd International Workshop on Combinatorial Algorithms. Proceedings of the 33rd International Workshop on Combinatorial Algorithms, IWOCA, Lecture Notes in Computer Science, vol. 13270 (2022), Springer), 214-227 · Zbl 07577701
[223] Moser, Hannes; Thilikos, Dimitrios M., Parameterized complexity of finding regular induced subgraphs, J. Discrete Algorithms, 7, 2, 181-190 (2009) · Zbl 1187.68351
[224] Mathieson, Luke; Szeider, Stefan, Editing graphs to satisfy degree constraints: A parameterized approach, J. Comput. System Sci., 78, 1, 179-191 (2012) · Zbl 1242.68124
[225] Garey, Michael R.; Johnson, David S., (Freeman, W. H., Computers and Intractability: A Guide To the Theory of NP-Completeness (1979)) · Zbl 0411.68039
[226] Stewart, Iain A., Deciding whether a planar graph has a cubic subgraph is NP-complete, Discrete Math., 126, 1-3, 349-357 (1994) · Zbl 0795.68150
[227] Stewart, Iain A., Finding regular subgraphs in both arbitrary and planar graphs, Discrete Appl. Math., 68, 3, 223-235 (1996) · Zbl 0855.68071
[228] Stewart, Iain A., On locating cubic subgraphs in bounded-degree connected bipartite graphs, Discrete Math., 163, 1-3, 319-324 (1997) · Zbl 0873.68097
[229] Mathieson, Luke, The Parameterized Complexity of Degree Constrained Editing Problems (2009), Durham University, (Ph.D. dissertation) · Zbl 1207.05200
[230] Frick, Markus; Grohe, Martin, Deciding first-order properties of locally tree-decomposable structures, J. ACM, 48, 6, 1184-1206 (2001) · Zbl 1323.03014
[231] Bulian, Jannis; Dawar, Anuj, Fixed-parameter tractable distances to sparse graph classes, Algorithmica, 79, 1, 139-158 (2017) · Zbl 1379.68160
[232] Golovach, Petr A., Editing to a graph of given degrees, Theoret. Comput. Sci., 591, 72-84 (2015) · Zbl 1322.68142
[233] Froese, Vincent; Nichterlein, André; Niedermeier, Rolf, Win-win kernelization for degree sequence completion problems, J. Comput. System Sci., 82, 6, 1100-1111 (2016) · Zbl 1345.68156
[234] Dabrowski, Konrad Kazimierz; Golovach, Petr A.; van ’t Hof, Pim; Paulusma, Daniël; Thilikos, Dimitrios M., Editing to a planar graph of given degrees, J. Comput. System Sci., 85, 168-182 (2017) · Zbl 1356.68096
[235] Golovach, Petr A., Editing to a connected graph of given degrees, Inform. and Comput., 256, 131-147 (2017) · Zbl 1376.68066
[236] Deborah, S. Franzblau; Raychaudhuri, Arundhati, Optimal Hamiltonian completions and path covers for trees, and a reduction to maximum flow, ANZIAM J., 44, 2, 193-204 (2002) · Zbl 1009.05088
[237] Moran, Shlomo; Wolfstahl, Yaron, Optimal covering of cacti by vertex-disjoint paths, Theoret. Comput. Sci., 84, 2, 179-197 (1991) · Zbl 0741.68082
[238] Fomin, Fedor V.; Golovach, Petr A.; Panolan, Fahad; Saurabh, Saket, Editing to connected \(F\)-degree graph, SIAM J. Discrete Math., 33, 2, 795-836 (2019) · Zbl 1429.68189
[239] Haarberg, Øyvind Stette, Complexity of edge editing to a connected graph of bounded degrees (2019), Department of Informatics, University of Bergen, (Master’s thesis)
[240] Bredereck, Robert; Froese, Vincent; Koseler, Marcel; Millani, Marcelo G.; Nichterlein, André; Niedermeier, Rolf, A parameterized algorithmics framework for degree sequence completion problems in directed graphs, Algorithmica, 81, 4, 1584-1614 (2019) · Zbl 1421.68108
[241] Mathieson, Luke, Graph editing problems with extended regularity constraints, Theoret. Comput. Sci., 677, 56-68 (2017) · Zbl 1370.68137
[242] Bodlaender, Hans L.; Fomin, Fedor V.; Lokshtanov, Daniel; Penninkx, Eelko; Saurabh, Saket; Thilikos, Dimitrios M., (Meta) kernelization, J. ACM, 63, 5, 44:1-44:69 (2016) · Zbl 1425.68137
[243] Boesch, Francis T.; Suffel, Charles L.; Tindell, Ralph, The spanning subgraphs of Eulerian graphs, J. Graph Theory, 1, 1, 79-84 (1977) · Zbl 0363.05042
[244] Lesniak, Linda M.; Oellermann, Ortrud R., An Eulerian exposition, J. Graph Theory, 10, 3, 277-297 (1986) · Zbl 0717.05054
[245] Dorn, Frederic; Moser, Hannes; Niedermeier, Rolf; Weller, Mathias, Efficient algorithms for Eulerian extension and rural postman, SIAM J. Discrete Math., 27, 1, 75-94 (2013) · Zbl 1267.05131
[246] Diestel, Reinhard, Graph theory, (Graduate Texts in Mathematics, vol. 173 (2012), Springer) · Zbl 1375.05002
[247] Dabrowski, Konrad Kazimierz; Golovach, Petr A.; van ’t Hof, Pim; Paulusma, Daniël, Editing to Eulerian graphs, J. Comput. System Sci., 82, 2, 213-228 (2016) · Zbl 1346.05150
[248] Cai, Leizhen; Yang, Boting, Parameterized complexity of even/odd subgraph problems, J. Discrete Algorithms, 9, 3, 231-240 (2011) · Zbl 1225.05228
[249] Cygan, Marek; Marx, Dániel; Pilipczuk, Marcin; Pilipczuk, Michał; Schlotter, Ildikó, Parameterized complexity of Eulerian deletion problems, Algorithmica, 68, 1, 41-61 (2014) · Zbl 1284.05157
[250] Goyal, Prachi; Misra, Pranabendu; Panolan, Fahad; Philip, Geevarghese; Saurabh, Saket, Finding even subgraphs even faster, J. Comput. System Sci., 97, 1-13 (2018) · Zbl 1404.68050
[251] Cechlárová, Katarina; Schlotter, Ildikó, Computing the deficiency of housing markets with duplicate houses, (Proceedings of the 5th International Symposium on Parameterized and Exact Computation. Proceedings of the 5th International Symposium on Parameterized and Exact Computation, IPEC. Proceedings of the 5th International Symposium on Parameterized and Exact Computation. Proceedings of the 5th International Symposium on Parameterized and Exact Computation, IPEC, Lecture Notes in Computer Science, vol. 6478 (2010), Springer), 72-83 · Zbl 1310.91109
[252] Crowston, Robert; Gutin, Gregory; Jones, Mark; Yeo, Anders, Parameterized Eulerian strong component arc deletion problem on tournaments, Inform. Process. Lett., 112, 6, 249-251 (2012) · Zbl 1242.68113
[253] Höhn, Wiebke; Jacobs, Tobias; Megow, Nicole, On Eulerian extensions and their application to no-wait flowshop scheduling, J. Sched., 15, 3, 295-309 (2012) · Zbl 1280.90050
[254] Sorge, Manuel; van Bevern, René; Niedermeier, Rolf; Weller, Mathias, From few components to an Eulerian graph by adding arcs, (Proceedings of the 37th International Workshop on Graph-Theoretic Concepts in Computer Science. Proceedings of the 37th International Workshop on Graph-Theoretic Concepts in Computer Science, WG. Proceedings of the 37th International Workshop on Graph-Theoretic Concepts in Computer Science. Proceedings of the 37th International Workshop on Graph-Theoretic Concepts in Computer Science, WG, Lecture Notes in Computer Science, vol. 6986 (2011), Springer), 307-318 · Zbl 1341.05144
[255] Sorge, Manuel; van Bevern, René; Niedermeier, Rolf; Weller, Mathias, A new view on rural postman based on Eulerian extension and matching, J. Discrete Algorithms, 16, 12-33 (2012) · Zbl 1255.68076
[256] Zheleva, Elena; Getoor, Lise, Social network data analytics, (Social Network Data Analytics. Social Network Data Analytics, chapter Privacy in Social Networks: A Survey (2011), Springer US), 277-306 · Zbl 1275.91007
[257] Casas-Roma, Jordi; Herrera-Joancomartí, Jordi; Torra, Vicenç, A survey of graph-modification techniques for privacy-preserving on networks, J. Artificial Intelligence Res., 47, 3, 341-366 (2017)
[258] Bazgan, Cristina; Bredereck, Robert; Hartung, Sepp; Nichterlein, André; Woeginger, Gerhard J., Finding large degree-anonymous subgraphs is hard, Theoret. Comput. Sci., 622, 90-110 (2016) · Zbl 1335.68095
[259] Demaine, Erik D.; Reidl, Felix; Rossmanith, Peter; Villaamil, Fernando S.; Sikdar, Somnath; Sullivan, Blair D., Structural sparsity of complex networks: Bounded expansion in random models and real-world graphs, J. Comput. System Sci., 105, 199-241 (2019) · Zbl 1425.05149
[260] Hartung, Sepp; Nichterlein, André; Niedermeier, Rolf; Suchý, Ondrej, A refined complexity analysis of degree anonymization in graphs, Inform. and Comput., 243, 249-262 (2015) · Zbl 1327.68134
[261] Bredereck, Robert; Froese, Vincent; Hartung, Sepp; Nichterlein, André; Niedermeier, Rolf; Talmon, Nimrod, The complexity of degree anonymization by vertex addition, Theoret. Comput. Sci., 607, 16-34 (2015) · Zbl 1332.68164
[262] Talmon, Nimrod; Hartung, Sepp, The complexity of degree anonymization by graph contractions, Inform. and Comput., 256, 212-225 (2017) · Zbl 1376.68069
[263] Golovach, Petr A.; Mertzios, George B., Graph editing to a given degree sequence, Theoret. Comput. Sci., 665, 1-12 (2017) · Zbl 1356.68098
[264] Hartung, Sepp; Nichterlein, André, NP-hardness and fixed-parameter tractability of realizing degree sequences with directed acyclic graphs, SIAM J. Discrete Math., 29, 4, 1931-1960 (2015) · Zbl 1330.68114
[265] Seidman, Stephen B., Network structure and minimum degree, Social Networks, 5, 3, 269-287 (1983)
[266] Chitnis, Rajesh H.; Talmon, Nimrod, Can we create large \(k\)-cores by adding few edges?, (Proceedings of the 13th International Computer Science Symposium in Russia (CSR). Proceedings of the 13th International Computer Science Symposium in Russia (CSR), Lecture Notes in Computer Science, vol. 10846 (2018), Springer), 78-89 · Zbl 1485.68177
[267] Li, Chung-Lun; Thomas McCormick, S.; Simchi-Levi, David, On the minimum-cardinality-bounded-diameter and the bounded-cardinality-minimum-diameter edge addition problems, Oper. Res. Lett., 11, 5, 303-308 (1992) · Zbl 0763.90085
[268] Gao, Yong; Hare, Donovan R.; Nastos, James, The parametric complexity of graph diameter augmentation, Discrete Appl. Math., 161, 10-11, 1626-1631 (2013) · Zbl 1287.05035
[269] Frati, Fabrizio; Gaspers, Serge; Gudmundsson, Joachim; Mathieson, Luke, Augmenting graphs to minimize the diameter, Algorithmica, 72, 4, 995-1010 (2015) · Zbl 1319.68156
[270] Dejter, Italo J.; Fellows, Michael R., Improving the diameter of a planar graph, Manuscript (1993)
[271] Robertson, Neil; Seymour, Paul D., Graph minors. XIII. The disjoint paths problem, J. Combin. Theory Ser. B, 63, 1, 65-110 (1995) · Zbl 0823.05038
[272] Lokshtanov, Daniel; de Oliveira Oliveira, Mateus; Saurabh, Saket, A strongly-uniform slicewise polynomial-time algorithm for the embedded planar diameter improvement problem, (Proceedings of the 13th International Symposium on Parameterized and Exact Computation. Proceedings of the 13th International Symposium on Parameterized and Exact Computation, IPEC. Proceedings of the 13th International Symposium on Parameterized and Exact Computation. Proceedings of the 13th International Symposium on Parameterized and Exact Computation, IPEC, Leibniz International Proceedings in Informatics (LIPIcs), vol. 115 (2019), Schloss Dagstuhl — Leibniz-Zentrum für Informatik), 25:1-25:13 · Zbl 1520.68123
[273] Cohen, Nathann; Gonçalves, Daniel; Kim, Eun Jung; Paul, Christophe; Sau, Ignasi; Thilikos, Dimitrios M.; Weller, Mathias, A polynomial-time algorithm for outerplanar diameter improvement, J. Comput. System Sci., 89, 315-327 (2017) · Zbl 1372.05216
[274] Golovach, Petr A.; Requilé, Clément; Thilikos, Dimitrios M., Variants of plane diameter completion, (Proceedings of the 10th International Symposium on Parameterized and Exact Computation. Proceedings of the 10th International Symposium on Parameterized and Exact Computation, IPEC. Proceedings of the 10th International Symposium on Parameterized and Exact Computation. Proceedings of the 10th International Symposium on Parameterized and Exact Computation, IPEC, Leibniz International Proceedings in Informatics (LIPIcs), vol. 43 (2015), Schloss Dagstuhl — Leibniz-Zentrum für Informatik), 30-42 · Zbl 1378.68078
[275] Kratochvíl, Jan; Nešetřil, Jaroslav; Zýka, Ondřej, On the computational complexity of seidel’s switching, (Proceedings of the 4th Czechoslovakian Symposium on Combinatorics, Graphs and Complexity. Proceedings of the 4th Czechoslovakian Symposium on Combinatorics, Graphs and Complexity, Annals of Discrete Mathematics, vol. 51 (1992), North-Holland: North-Holland Amsterdam), 161-166 · Zbl 0768.68047
[276] Jelínková, Eva; Suchý, Ondrej; Hlinený, Petr; Kratochvíl, Jan, Parameterized problems related to Seidel’s switching, Discrete Math. Theor. Comput. Sci., 13, 2, 19-44 (2011) · Zbl 1283.68164
[277] Kotzig, Anton, Eulerian lines in finite \(4\)-valent graphs and their transformations, (Proceedings of the Tihany Theory of Graphs Colloquium (1968), Academic Press: Academic Press New York), 219-230 · Zbl 0159.54201
[278] Oum, Sang-il, Rank-width and vertex-minors, J. Combin. Theory Ser. B, 95, 1, 79-100 (2005) · Zbl 1070.05023
[279] Cattanéo, David; Perdrix, Simon, Minimum degree up to local complementation: Bounds, parameterized complexity, and exact algorithms, (Proceedings of the 26th International Symposium on Algorithms and Computation. Proceedings of the 26th International Symposium on Algorithms and Computation, ISAAC. Proceedings of the 26th International Symposium on Algorithms and Computation. Proceedings of the 26th International Symposium on Algorithms and Computation, ISAAC, Lecture Notes in Computer Science, vol. 9472 (2015), Springer), 259-270 · Zbl 1472.68110
[280] Fomin, Fedor V.; Golovach, Petr A.; Strømme, Torstein J. F.; Thilikos, Dimitrios M., Partial complementation of graphs, (Proceedings of the 16th Scandinavian Symposium and Workshops on Algorithm Theory. Proceedings of the 16th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT. Proceedings of the 16th Scandinavian Symposium and Workshops on Algorithm Theory. Proceedings of the 16th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT, Leibniz International Proceedings in Informatics (LIPIcs), vol. 101 (2018), Schloss Dagstuhl — Leibniz-Zentrum für Informatik), 21:1-21:13 · Zbl 1477.68225
[281] Fomin, Fedor V.; Golovach, Petr A.; Thilikos, Dimitrios M., Structured connectivity augmentation, SIAM J. Discrete Math., 32, 4, 2612-2635 (2018) · Zbl 1400.05134
[282] Fomin, Fedor V.; Golovach, Petr A.; Thilikos, Dimitrios M., Modification to planarity is fixed parameter tractable, (Leibniz International Proceedings in Informatics (LIPIcs), vol. 126 (2019), Schloss Dagstuhl — Leibniz-Zentrum für Informatik), 28:1-28:17 · Zbl 07559137
[283] Bose, Prosenjit; Hurtado, Ferran, Flips in planar graphs, Comput. Geom., 42, 1, 60-80 (2009) · Zbl 1146.05016
[284] Lubiw, Anna; Pathak, Vinayak, Flip distance between two triangulations of a point set is NP-complete, Comput. Geom., 49, 17-23 (2015) · Zbl 1333.65022
[285] Pilz, Alexander, Flip distance between triangulations of a planar point set is APX-hard, Comput. Geom., 47, 5, 589-604 (2014) · Zbl 1293.65032
[286] Hanke, Sabine; Ottmann, Thomas; Schuierer, Sven, The edge-flipping distance of triangulations, J. UCS, 2, 8, 570-579 (1996) · Zbl 0955.68122
[287] Cleary, Sean; John, Katherine St., Rotation distance is fixed-parameter tractable, Inform. Process. Lett., 109, 16, 918-922 (2009) · Zbl 1205.68531
[288] Sleator, Daniel D.; Tarjan, Robert E.; Thurston, William P., Rotation distance, triangulations, and hyperbolic geometry, AMS J. Am. Math. Soc., 1, 3, 647-681 (1988) · Zbl 0653.51017
[289] Lucas, Joan M., An improved kernel size for rotation distance in binary trees, Inform. Process. Lett., 110, 12-13, 481-484 (2010) · Zbl 1233.68147
[290] Kanj, Iyad A.; Sedgwick, Eric; Xia, Ge, Computing the flip distance between triangulations, Discrete Comput. Geom., 58, 2, 313-344 (2017) · Zbl 1371.05063
[291] Feng, Qilong; Li, Shaohua; Meng, Xiangzhong; Wang, Jianxin, An improved FPT algorithm for the flip distance problem, Inform. and Comput., 281, Article 104708 pp. (2021) · Zbl 1518.68410
[292] Easley, David A.; Kleinberg, Jon M., Networks, Crowds, and Markets: Reasoning About a Highly Connected World (2010), Cambridge University Press · Zbl 1205.91007
[293] Sintos, Stavros; Tsaparas, Panayiotis, Using strong triadic closure to characterize ties in social networks, (Proceedings of the 20th International Conference on Knowledge Discovery and Data Mining (KDD) (2014), ACM), 1466-1475
[294] Golovach, Petr A.; Heggernes, Pinar; Konstantinidis, Athanasios L.; Lima, Paloma T.; Papadopoulos, Charis, Parameterized aspects of strong subgraph closure, Algorithmica, 82, 7, 2006-2038 (2020) · Zbl 1442.68168
[295] Grüttemeier, Niels; Komusiewicz, Christian, On the relation of strong triadic closure and cluster deletion, Algorithmica, 82, 4, 853-880 (2020) · Zbl 1435.68235
[296] Bulteau, Laurent; Grüttemeier, Niels; Komusiewicz, Christian; Sorge, Manuel, Your rugby mates don’t need to know your colleagues: Triadic closure with edge colors, J. Comput. System Sci., 120, 75-96 (2021) · Zbl 1477.68210
[297] Grüttemeier, Niels; Komusiewicz, Christian; Schestag, Jannik; Sommer, Frank, Destroying bicolored \(P_3\) s by deleting few edges, Discrete Math. Theor. Comput. Sci., 23, 1 (2021) · Zbl 1498.05097
[298] Giannopoulou, Archontia; Pilipczuk, Michał; Raymond, Jean-Florent; Thilikos, Dimitrios M.; Wrochna, Marcin, Linear kernels for edge deletion problems to immersion-closed graph classes, SIAM J. Discrete Math., 35, 1, 105-151 (2021) · Zbl 1461.05164
[299] Fomin, Fedor V.; Golovach, Petr A.; Thilikos, Dimitrios M., On the parameterized complexity of graph modification to first-order logic properties, Theory Comput. Syst., 64, 2, 251-271 (2020) · Zbl 1434.68208
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.