{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T00:45:29Z","timestamp":1767314729360,"version":"3.48.0"},"publisher-location":"Cham","reference-count":33,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032118349","type":"print"},{"value":"9783032118356","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026]]},"DOI":"10.1007\/978-3-032-11835-6_25","type":"book-chapter","created":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T00:42:31Z","timestamp":1767314551000},"page":"345-359","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Efficient Parameterized Approximation"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0193-7239","authenticated-orcid":false,"given":"Stefan","family":"Kratsch","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0787-8428","authenticated-orcid":false,"given":"Pascal","family":"Kunz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,1,2]]},"reference":[{"key":"25_CR1","doi-asserted-by":"publisher","unstructured":"Agarwal, A., Charikar, M., Makarychev, K., Makarychev, Y.: $$O(\\sqrt{\\log n} )$$ approximation algorithms for Min UnCut, Min 2CNF deletion, and directed cut problems. In: Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing, pp. 573\u2013581 (2005). https:\/\/doi.org\/10.1145\/1060590.1060675","DOI":"10.1145\/1060590.1060675"},{"key":"25_CR2","doi-asserted-by":"publisher","unstructured":"Aprile, M., Drescher, M., Fiorini, S., Huynh, T.: A tight approximation algorithm for the cluster vertex deletion problem. Math. Program. 1\u201323 (2021). https:\/\/doi.org\/10.1007\/s10107-021-01744-w","DOI":"10.1007\/s10107-021-01744-w"},{"issue":"3","key":"25_CR3","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1137\/S0895480196305124","volume":"12","author":"V Bafna","year":"1999","unstructured":"Bafna, V., Berman, P., Fujito, T.: A 2-approximation algorithm for the undirected feedback vertex set problem. SIAM J. Discret. Math. 12(3), 289\u2013297 (1999). https:\/\/doi.org\/10.1137\/S0895480196305124","journal-title":"SIAM J. Discret. Math."},{"key":"25_CR4","doi-asserted-by":"publisher","unstructured":"Bansal, N., Khot, S.: Optimal long code test with one free bit. In: Proceedings of the 50th Annual Symposium on Foundations of Computer Science (FOCS), pp. 453\u2013462 (2009). https:\/\/doi.org\/10.1109\/FOCS.2009.23","DOI":"10.1109\/FOCS.2009.23"},{"issue":"4","key":"25_CR5","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1145\/1041680.1041683","volume":"36","author":"R Bar-Yehuda","year":"2004","unstructured":"Bar-Yehuda, R., Bendel, K., Freund, A., Rawitz, D.: Local ratio: a unified framework for approximation algorithms. ACM Comput. Surv. 36(4), 422\u2013463 (2004). https:\/\/doi.org\/10.1145\/1041680.1041683","journal-title":"ACM Comput. Surv."},{"issue":"1","key":"25_CR6","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/0004-3702(95)00004-6","volume":"83","author":"A Becker","year":"1996","unstructured":"Becker, A., Geiger, D.: Optimization of Pearl\u2019s method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem. Artif. Intell. 83(1), 167\u2013188 (1996). https:\/\/doi.org\/10.1016\/0004-3702(95)00004-6","journal-title":"Artif. Intell."},{"key":"25_CR7","doi-asserted-by":"publisher","unstructured":"Cao, Y.: Linear recognition of almost interval graphs. In: Proceedings of the 2016 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1096\u20131115 (2016). https:\/\/doi.org\/10.1137\/1.9781611974331.ch77","DOI":"10.1137\/1.9781611974331.ch77"},{"key":"25_CR8","doi-asserted-by":"publisher","unstructured":"Chalermsook, P., Fomin, F., Hamm, T., Korhonen, T., Nederlof, J., Orgo, L.: Polynomial-time approximation of Independent Set parameterized by treewidth. In: Proceedings of the 31st Annual European Symposium on Algorithms (ESA 2023), pp. 33:1\u201333:13 (2023). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2023.33","DOI":"10.4230\/LIPIcs.ESA.2023.33"},{"key":"25_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"328","DOI":"10.1007\/978-3-642-39206-1_28","volume-title":"Automata, Languages, and Programming","author":"C Chekuri","year":"2013","unstructured":"Chekuri, C., Naves, G., Shepherd, F.B.: Maximum edge-disjoint paths in k-sums of graphs. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013. LNCS, vol. 7965, pp. 328\u2013339. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-39206-1_28"},{"issue":"3","key":"25_CR10","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/0166-218X(81)90013-5","volume":"3","author":"D Corneil","year":"1981","unstructured":"Corneil, D., Lerchs, H., Burlingham, L.S.: Complement reducible graphs. Discret. Appl. Math. 3(3), 163\u2013174 (1981). https:\/\/doi.org\/10.1016\/0166-218X(81)90013-5","journal-title":"Discret. Appl. Math."},{"key":"25_CR11","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., et al.: Parameterized Algorithms. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-21275-3"},{"key":"25_CR12","doi-asserted-by":"publisher","unstructured":"Demaine, E.D., et al.: Structural rounding: Approximation algorithms for graphs near an algorithmically tractable class. In: Proceedings of the 27th Annual European Symposium on Algorithms (ESA), pp. 37:1\u201337:15 (2019). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2019.37","DOI":"10.4230\/LIPIcs.ESA.2019.37"},{"key":"25_CR13","doi-asserted-by":"crossref","unstructured":"Diestel, R.: Graph theory. Springer (2024)","DOI":"10.1007\/978-3-662-70107-2_7"},{"key":"25_CR14","doi-asserted-by":"publisher","unstructured":"Ene, A., Mnich, M., Pilipczuk, M., Risteski, A.: On routing disjoint paths in bounded treewidth graphs. In: Proceedings of the 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016), pp. 15:1\u201315:15 (2016). https:\/\/doi.org\/10.4230\/LIPIcs.SWAT.2016.15","DOI":"10.4230\/LIPIcs.SWAT.2016.15"},{"key":"25_CR15","doi-asserted-by":"publisher","unstructured":"Erlebach, T., Hoffmann, M., Kammer, F.: On temporal graph exploration. J. Comput. Syst. Sci. 119, 1\u201318 (2021). https:\/\/doi.org\/10.1016\/j.jcss.2021.01.005","DOI":"10.1016\/j.jcss.2021.01.005"},{"key":"25_CR16","doi-asserted-by":"publisher","unstructured":"Fleszar, K., Mnich, M., Spoerhase, J.: New algorithms for maximum disjoint paths based on tree-likeness. In: Proceedings of the 24th Annual European Symposium on Algorithms (ESA 2016), pp. 42:1\u201342:17 (2016). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2016.42","DOI":"10.4230\/LIPIcs.ESA.2016.42"},{"issue":"3","key":"25_CR17","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"M Garey","year":"1976","unstructured":"Garey, M., Johnson, D., Stockmeyer, L.: Some simplified NP-complete graph problems. Theoret. Comput. Sci. 1(3), 237\u2013267 (1976). https:\/\/doi.org\/10.1016\/0304-3975(76)90059-1","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"25_CR18","doi-asserted-by":"publisher","first-page":"1371","DOI":"10.1137\/15M1038876","volume":"30","author":"AC Giannopoulou","year":"2016","unstructured":"Giannopoulou, A.C., Lokshtanov, D., Saurabh, S., Such\u00fd, O.: Tree deletion set has a polynomial kernel (but no $$\\text{ OPT}^{O(1)}$$ approximation). SIAM J. Discret. Math. 30(3), 1371\u20131384 (2016). https:\/\/doi.org\/10.1137\/15M1038876","journal-title":"SIAM J. Discret. Math."},{"issue":"4","key":"25_CR19","doi-asserted-by":"publisher","first-page":"718","DOI":"10.1137\/0210055","volume":"10","author":"I Holyer","year":"1981","unstructured":"Holyer, I.: The NP-completeness of edge-coloring. SIAM J. Comput. 10(4), 718\u2013720 (1981). https:\/\/doi.org\/10.1137\/0210055","journal-title":"SIAM J. Comput."},{"key":"25_CR20","doi-asserted-by":"publisher","unstructured":"Inamdar, T., Kanesh, L., Kundu, M., Ramanujan, M.S., Saurabh, S.: FPT approximations for packing and covering problems parameterized by elimination distance and even less. In: Proceedings of the 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023), pp. 28:1\u201328:16 (2023). https:\/\/doi.org\/10.4230\/LIPIcs.FSTTCS.2023.28","DOI":"10.4230\/LIPIcs.FSTTCS.2023.28"},{"key":"25_CR21","doi-asserted-by":"publisher","unstructured":"Jansen, B.M.P., W\u0142odarczyk, M.: Lossy planarization: a constant-factor approximate kernelization for planar vertex deletion. In: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2022), p. 900\u2013913 (2022). https:\/\/doi.org\/10.1145\/3519935.3520021","DOI":"10.1145\/3519935.3520021"},{"key":"25_CR22","doi-asserted-by":"publisher","unstructured":"Kashaev, D., Sch\u00e4fer, G.: Round and bipartize for vertex cover approximation. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM 2023), pp. 20:1\u201320:20 (2023). https:\/\/doi.org\/10.4230\/LIPIcs.APPROX\/RANDOM.2023.20","DOI":"10.4230\/LIPIcs.APPROX\/RANDOM.2023.20"},{"issue":"3","key":"25_CR23","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/j.jcss.2007.06.019","volume":"74","author":"S Khot","year":"2008","unstructured":"Khot, S., Regev, O.: Vertex cover might be hard to approximate to within $$2-\\epsilon $$. J. Comput. Syst. Sci. 74(3), 335\u2013349 (2008). https:\/\/doi.org\/10.1016\/j.jcss.2007.06.019","journal-title":"J. Comput. Syst. Sci."},{"key":"25_CR24","unstructured":"Kratsch, S., Kunz, P.: Efficient parameterized approximation (2025), https:\/\/arxiv.org\/abs\/2501.14461"},{"key":"25_CR25","doi-asserted-by":"publisher","unstructured":"Kratsch, S., Wahlstr\u00f6m, M.: Compression via matroids: a randomized polynomial kernel for odd cycle transversal. ACM Trans. Algorithms 10(4) (2014). https:\/\/doi.org\/10.1145\/2635810","DOI":"10.1145\/2635810"},{"key":"25_CR26","doi-asserted-by":"publisher","unstructured":"Lavallee, B., Russell, H., Sullivan, B.D., van\u00a0der Poel, A.: Approximating vertex cover using structural rounding. In: Proceedings of the 22nd Workshop on Algorithm Engineering and Experiments (ALENEX), pp. 70\u201380 (2020). https:\/\/doi.org\/10.1137\/1.9781611976007.6","DOI":"10.1137\/1.9781611976007.6"},{"key":"25_CR27","doi-asserted-by":"publisher","unstructured":"Lokshtanov, D., Narayanaswamy, N.S., Raman, V., Ramanujan, M.S., Saurabh, S.: Faster parameterized algorithms using linear programming. ACM Trans. Algorithms 11(2) (2014). https:\/\/doi.org\/10.1145\/2566616","DOI":"10.1145\/2566616"},{"key":"25_CR28","doi-asserted-by":"publisher","first-page":"481","DOI":"10.1137\/1010115","volume":"10","author":"DW Matula","year":"1968","unstructured":"Matula, D.W.: A min-max theorem for graphs with application to graph coloring. SIAM Rev. 10, 481\u2013482 (1968). https:\/\/doi.org\/10.1137\/1010115","journal-title":"SIAM Rev."},{"issue":"4","key":"25_CR29","doi-asserted-by":"publisher","first-page":"857","DOI":"10.1007\/s00453-010-9412-2","volume":"61","author":"S Mishra","year":"2010","unstructured":"Mishra, S., Raman, V., Saurabh, S., Sikdar, S., Subramanian, C.R.: The complexity of K\u00f6nig subgraph problems and\u00a0above-guarantee vertex cover. Algorithmica 61(4), 857\u2013881 (2010). https:\/\/doi.org\/10.1007\/s00453-010-9412-2","journal-title":"Algorithmica"},{"issue":"3","key":"25_CR30","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/0020-0190(92)90041-S","volume":"41","author":"J Misra","year":"1992","unstructured":"Misra, J., Gries, D.: A constructive proof of Vizing\u2019s theorem. Inf. Process. Lett. 41(3), 131\u2013133 (1992). https:\/\/doi.org\/10.1016\/0020-0190(92)90041-S","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"25_CR31","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1007\/BF01580222","volume":"6","author":"GL Nemhauser","year":"1974","unstructured":"Nemhauser, G.L., Trotter, L.E., Jr.: Properties of vertex packing and independence system polyhedra. Math. Program. 6(1), 48\u201361 (1974). https:\/\/doi.org\/10.1007\/BF01580222","journal-title":"Math. Program."},{"issue":"1","key":"25_CR32","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1007\/BF01580444","volume":"8","author":"GL Nemhauser","year":"1975","unstructured":"Nemhauser, G.L., Trotter, L.E., Jr.: Vertex packings: structural properties and algorithms. Math. Program. 8(1), 232\u2013248 (1975). https:\/\/doi.org\/10.1007\/BF01580444","journal-title":"Math. Program."},{"key":"25_CR33","doi-asserted-by":"publisher","unstructured":"Robertson, N., Sanders, D.P., Seymour, P., Thomas, R.: Efficiently four-coloring planar graphs. In: Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing (STOC 1996), pp. 571\u2013575 (1996). https:\/\/doi.org\/10.1145\/237814.238005","DOI":"10.1145\/237814.238005"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-11835-6_25","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T00:42:33Z","timestamp":1767314553000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-11835-6_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032118349","9783032118356"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-11835-6_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"2 January 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WG","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Graph-Theoretic Concepts in Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Otzenhausen","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Germany","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 June 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13 June 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"51","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wg2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/algo.uni-trier.de\/wg2025\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}