{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T18:36:31Z","timestamp":1770921391453,"version":"3.50.1"},"publisher-location":"Cham","reference-count":41,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032178008","type":"print"},{"value":"9783032178015","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-17801-5_40","type":"book-chapter","created":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T17:53:03Z","timestamp":1770918783000},"page":"547-562","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Optimal Approximations for\u00a0the\u00a0Requirement Cut Problem on\u00a0Sparse Graph Classes"],"prefix":"10.1007","author":[{"given":"Nadym","family":"Mallek","sequence":"first","affiliation":[]},{"given":"Kirill","family":"Simonov","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2026,2,13]]},"reference":[{"key":"40_CR1","doi-asserted-by":"publisher","unstructured":"Aluffi, P., Marcolli, M., Qaisar, W.: Motives of melonic graphs. Annales de l\u2019Institut Henri Poincar\u00e9 D Comb. Phys. Interact. 10(3), 503\u2013554 (2022). https:\/\/doi.org\/10.4171\/aihpd\/156","DOI":"10.4171\/aihpd\/156"},{"issue":"1\u20133","key":"40_CR2","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/j.tcs.2007.02.026","volume":"377","author":"A Avidor","year":"2007","unstructured":"Avidor, A., Langberg, M.: The multi-multiway cut problem. Theoret. Comput. Sci. 377(1\u20133), 35\u201342 (2007)","journal-title":"Theoret. Comput. Sci."},{"issue":"8","key":"40_CR3","doi-asserted-by":"publisher","first-page":"1003","DOI":"10.1007\/s11005-014-0699-9","volume":"104","author":"A Baratin","year":"2014","unstructured":"Baratin, A., Carrozza, S., Oriti, D., Ryan, J., Smerlak, M.: Melonic phase transition in group field theory. Lett. Math. Phys. 104(8), 1003\u20131017 (2014). https:\/\/doi.org\/10.1007\/s11005-014-0699-9","journal-title":"Lett. Math. Phys."},{"issue":"11","key":"40_CR4","doi-asserted-by":"publisher","first-page":"1222","DOI":"10.1109\/34.969114","volume":"23","author":"Y Boykov","year":"2001","unstructured":"Boykov, Y., Veksler, O., Zabih, R.: Fast approximate energy minimization via graph cuts. IEEE Trans. Pattern Anal. Mach. Intell. 23(11), 1222\u20131239 (2001). https:\/\/doi.org\/10.1109\/34.969114","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"issue":"6","key":"40_CR5","doi-asserted-by":"publisher","first-page":"1020","DOI":"10.1016\/j.jcss.2016.03.003","volume":"82","author":"K Bringmann","year":"2016","unstructured":"Bringmann, K., Hermelin, D., Mnich, M., van Leeuwen, E.J.: Parameterized complexity dichotomy for Steiner Multicut. J. Comput. Syst. Sci. 82(6), 1020\u20131043 (2016)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"40_CR6","doi-asserted-by":"publisher","first-page":"1463","DOI":"10.1137\/15M1045521","volume":"47","author":"N Buchbinder","year":"2018","unstructured":"Buchbinder, N., Seffi, J., Schwartz, R.: Simplex partitioning via exponential clocks and the multiway-cut problem. SIAM J. Comput. 47(4), 1463\u20131482 (2018). https:\/\/doi.org\/10.1137\/15M1045521","journal-title":"SIAM J. Comput."},{"key":"40_CR7","doi-asserted-by":"publisher","unstructured":"Carlson, C., Jafarov, J., Makarychev, K., Makarychev, Y., Shan, L.: Approximation Algorithm for Norm Multiway Cut. LIPIcs, vol. 274, ESA 2023 274, 32:1\u201332:14 (2023). https:\/\/doi.org\/10.4230\/LIPICS.ESA.2023.32, artwork Size: 14 pages, 676151 bytes ISBN: 9783959772952 Medium: application\/pdf Publisher: Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik","DOI":"10.4230\/LIPICS.ESA.2023.32"},{"key":"40_CR8","doi-asserted-by":"publisher","unstructured":"Chandrasekaran, K., Wang, W.: l_p-norm multiway cut. LIPIcs, vol. 204, ESA 2021 204, 29:1\u201329:15 (2021). https:\/\/doi.org\/10.4230\/LIPICS.ESA.2021.29, artwork Size: 15 pages, 879891 bytes ISBN: 9783959772044 Medium: application\/pdf Publisher: Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik","DOI":"10.4230\/LIPICS.ESA.2021.29"},{"issue":"1","key":"40_CR9","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1137\/S0895480104445095","volume":"20","author":"C Chekuri","year":"2006","unstructured":"Chekuri, C., Guha, S., Naor, J.S.: The Steiner k-cut problem. SIAM J. Discret. Math. 20(1), 261\u2013271 (2006). https:\/\/doi.org\/10.1137\/S0895480104445095","journal-title":"SIAM J. Discret. Math."},{"issue":"1","key":"40_CR10","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1002\/net.3230210106","volume":"21","author":"S Chopra","year":"1991","unstructured":"Chopra, S., Rao, M.R.: On the multiway cut polyhedron. Networks 21(1), 51\u201389 (1991). https:\/\/doi.org\/10.1002\/net.3230210106","journal-title":"Networks"},{"key":"40_CR11","doi-asserted-by":"publisher","unstructured":"Cong, J., Shinnerl, J.R., Du, D.Z., Pardalos, P.M. (eds.): Multilevel Optimization in VLSICAD, Combinatorial Optimization, vol.\u00a014. Springer, Boston (2003). https:\/\/doi.org\/10.1007\/978-1-4757-3748-6","DOI":"10.1007\/978-1-4757-3748-6"},{"issue":"3","key":"40_CR12","doi-asserted-by":"publisher","first-page":"564","DOI":"10.1006\/jcss.1999.1687","volume":"60","author":"G C\u0103linescu","year":"2000","unstructured":"C\u0103linescu, G., Karloff, H., Rabani, Y.: An improved approximation algorithm for multiway cut. J. Comput. Syst. Sci. 60(3), 564\u2013574 (2000)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"40_CR13","doi-asserted-by":"publisher","first-page":"864","DOI":"10.1137\/S0097539792225297","volume":"23","author":"E Dahlhaus","year":"1994","unstructured":"Dahlhaus, E., Johnson, D.S., Papadimitriou, C.H., Seymour, P.D., Yannakakis, M.: The complexity of multiterminal cuts. SIAM J. Comput. 23(4), 864\u2013894 (1994). https:\/\/doi.org\/10.1137\/S0097539792225297","journal-title":"SIAM J. Comput."},{"key":"40_CR14","doi-asserted-by":"crossref","unstructured":"Deng, X., Lin, B., Zhang, C.: Multi-multiway cut problem on graphs of bounded branch width. In: FAW-AAIM (2013). https:\/\/api.semanticscholar.org\/CorpusID:943999","DOI":"10.1007\/978-3-642-38756-2_32"},{"key":"40_CR15","doi-asserted-by":"publisher","unstructured":"Donde, V., et al.: Identification of severe multiple contingencies in electric power networks. In: Proceedings of the 37th Annual North American Power Symposium, pp. 59\u201366. IEEE, Ames, IA, USA (2005). https:\/\/doi.org\/10.1109\/NAPS.2005.1560502","DOI":"10.1109\/NAPS.2005.1560502"},{"issue":"4","key":"40_CR16","doi-asserted-by":"publisher","first-page":"1827","DOI":"10.1137\/090745441","volume":"23","author":"Y Emek","year":"2010","unstructured":"Emek, Y., Peleg, D.: A tight upper bound on the probabilistic embedding of series-parallel graphs. SIAM J. Discret. Math. 23(4), 1827\u20131841 (2010). https:\/\/doi.org\/10.1137\/090745441","journal-title":"SIAM J. Discret. Math."},{"key":"40_CR17","doi-asserted-by":"publisher","unstructured":"Fagginger\u00a0Auer, B., Bisseling, R.: Graph coarsening and clustering on the GPU. In: Bader, D., Meyerhenke, H., Sanders, P., Wagner, D. (eds.) Contemporary Mathematics, vol.\u00a0588, pp. 223\u2013240. American Mathematical Society, Providence, Rhode Island (2013). https:\/\/doi.org\/10.1090\/conm\/588\/11706. http:\/\/www.ams.org\/conm\/588","DOI":"10.1090\/conm\/588\/11706"},{"issue":"3","key":"40_CR18","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1016\/j.jcss.2004.04.011","volume":"69","author":"J Fakcharoenphol","year":"2004","unstructured":"Fakcharoenphol, J., Rao, S., Talwar, K.: A tight bound on approximating arbitrary metrics by tree metrics. J. Comput. Syst. Sci. 69(3), 485\u2013497 (2004)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"40_CR19","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U Feige","year":"1998","unstructured":"Feige, U.: A threshold of ln n for approximating set cover. J. ACM 45(4), 634\u2013652 (1998). https:\/\/doi.org\/10.1145\/285055.285059","journal-title":"J. ACM"},{"key":"40_CR20","doi-asserted-by":"publisher","unstructured":"Friedrich, T., Issac, D., Kumar, N., Mallek, N., Zeif, Z.: A primal-dual algorithm for multicommodity flows and multicuts in treewidth-2 graphs. In: Chakrabarti, A., Swamy, C. (eds.) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), vol.\u00a0245, pp. 55:1\u201355:18. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2022). https:\/\/doi.org\/10.4230\/LIPIcs.APPROX\/RANDOM.2022.55. https:\/\/drops.dagstuhl.de\/entities\/document\/10.4230\/LIPIcs.APPROX\/RANDOM.2022.55, iSSN: 1868-8969","DOI":"10.4230\/LIPIcs.APPROX\/RANDOM.2022.55"},{"key":"40_CR21","doi-asserted-by":"publisher","unstructured":"Friedrich, T., Issac, D., Kumar, N., Mallek, N., Zeif, Z.: Approximate max-flow min-multicut theorem for graphs of bounded treewidth. In: Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pp. 1325\u20131334. ACM, Orlando, FL, USA (2023). https:\/\/doi.org\/10.1145\/3564246.3585150","DOI":"10.1145\/3564246.3585150"},{"key":"40_CR22","doi-asserted-by":"publisher","unstructured":"Garg, N., Vazirani, V.V., Yannakakis, M.: Approximate max-flow min-(multi)cut theorems and their applications. In: Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, STOC 1993, pp. 698\u2013707. ACM Press, San Diego, California, USA (1993). https:\/\/doi.org\/10.1145\/167088.167266","DOI":"10.1145\/167088.167266"},{"key":"40_CR23","doi-asserted-by":"crossref","unstructured":"Goldschmidt, O., Hochbaum, D.S.: A polynomial algorithm for the k-cut problem for fixed k. Math. Oper. Res. 19(1), 24\u201337 (1994). https:\/\/www.jstor.org\/stable\/3690374","DOI":"10.1287\/moor.19.1.24"},{"issue":"3","key":"40_CR24","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1109\/TPAMI.2006.57","volume":"28","author":"L Grady","year":"2006","unstructured":"Grady, L., Schwartz, E.: Isoperimetric graph partitioning for image segmentation. IEEE Trans. Pattern Anal. Mach. Intell. 28(3), 469\u2013475 (2006)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"40_CR25","doi-asserted-by":"publisher","unstructured":"Gupta, A., Harris, D.G., Lee, E., Li, J.: Optimal bounds for the k-cut problem. J. ACM 69(1) (2021). https:\/\/doi.org\/10.1145\/3478018","DOI":"10.1145\/3478018"},{"issue":"4","key":"40_CR26","doi-asserted-by":"publisher","first-page":"322","DOI":"10.1016\/j.orl.2010.02.009","volume":"38","author":"A Gupta","year":"2010","unstructured":"Gupta, A., Nagarajan, V., Ravi, R.: An improved approximation algorithm for requirement cut. Oper. Res. Lett. 38(4), 322\u2013325 (2010)","journal-title":"Oper. Res. Lett."},{"issue":"2","key":"40_CR27","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1007\/s00493-004-0015-x","volume":"24","author":"A Gupta","year":"2004","unstructured":"Gupta, A., Newman, I., Rabinovich, Y., Sinclair, A.: Cuts, trees and L1-embeddings of graphs*. Combinatorica 24(2), 233\u2013269 (2004). https:\/\/doi.org\/10.1007\/s00493-004-0015-x","journal-title":"Combinatorica"},{"issue":"4","key":"40_CR28","doi-asserted-by":"publisher","first-page":"707","DOI":"10.1137\/0606068","volume":"6","author":"DS Hochbaum","year":"1985","unstructured":"Hochbaum, D.S., Shmoys, D.B.: An O(|V|$$^2$$) algorithm for the planar 3-cut problem. SIAM J. Algebraic Discret. Methods 6(4), 707\u2013712 (1985). https:\/\/doi.org\/10.1137\/0606068","journal-title":"SIAM J. Algebraic Discret. Methods"},{"issue":"3","key":"40_CR29","doi-asserted-by":"publisher","first-page":"344","DOI":"10.1287\/opre.11.3.344","volume":"11","author":"TC Hu","year":"1963","unstructured":"Hu, T.C.: Multi-commodity network flows. Oper. Res. 11(3), 344\u2013360 (1963). https:\/\/doi.org\/10.1287\/opre.11.3.344","journal-title":"Oper. Res."},{"key":"40_CR30","doi-asserted-by":"publisher","unstructured":"Jue, S., Klein, P.N.: A near-linear time minimum Steiner cut algorithm for planar graphs (2019). https:\/\/doi.org\/10.48550\/arXiv.1912.11103, [cs]","DOI":"10.48550\/arXiv.1912.11103"},{"key":"40_CR31","unstructured":"Junker, B.H., Schreiber, F. (eds.): Analysis of Biological Networks. Wiley Series on Bioinformatics. Wiley-Interscience, Hoboken (2008), oCLC: ocn166454234"},{"key":"40_CR32","doi-asserted-by":"crossref","unstructured":"Karger, D.R., Klein, P., Stein, C., Thorup, M., Young, N.E.: Rounding algorithms for a geometric embedding of minimum multiway cut. Math. Oper. Res. 29(3), 436\u2013461 (2004). https:\/\/www.jstor.org\/stable\/30035660","DOI":"10.1287\/moor.1030.0086"},{"issue":"12","key":"40_CR33","doi-asserted-by":"publisher","first-page":"497","DOI":"10.1002\/andp.18471481202","volume":"148","author":"G Kirchhoff","year":"1847","unstructured":"Kirchhoff, G.: Ueber die Aufl\u00f6sung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Str\u00f6me gef\u00fchrt wird. Ann. Phys. 148(12), 497\u2013508 (1847). https:\/\/doi.org\/10.1002\/andp.18471481202","journal-title":"Ann. Phys."},{"issue":"2","key":"40_CR34","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1006\/jagm.1996.0833","volume":"22","author":"PN Klein","year":"1997","unstructured":"Klein, P.N., Plotkin, S.A., Rao, S., Tardos, E.: Approximation algorithms for steiner and directed multicuts. J. Algorithms 22(2), 241\u2013269 (1997)","journal-title":"J. Algorithms"},{"key":"40_CR35","unstructured":"Mallek, N., Simonov, K.: Optimal approximations for the requirement cut problem on sparse graph classes (2025). https:\/\/arxiv.org\/abs\/2505.21433, [cs.DS]"},{"issue":"2","key":"40_CR36","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1007\/s00453-008-9171-5","volume":"56","author":"V Nagarajan","year":"2010","unstructured":"Nagarajan, V., Ravi, R.: Approximation algorithms for requirement cut on graphs. Algorithmica 56(2), 198\u2013213 (2010). https:\/\/doi.org\/10.1007\/s00453-008-9171-5","journal-title":"Algorithmica"},{"key":"40_CR37","doi-asserted-by":"publisher","unstructured":"Ne\u0161et\u0159il, J., de Mendez, P.O.: Bounded height trees and tree-depth. In: Sparsity. AC, vol. 28, pp. 115\u2013144. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-27875-4_6","DOI":"10.1007\/978-3-642-27875-4_6"},{"issue":"1","key":"40_CR38","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1137\/S0097539792251730","volume":"24","author":"H Saran","year":"1995","unstructured":"Saran, H., Vazirani, V.V.: Finding k cuts within twice the optimal. SIAM J. Comput. 24(1), 101\u2013108 (1995). https:\/\/doi.org\/10.1137\/S0097539792251730","journal-title":"SIAM J. Comput."},{"key":"40_CR39","doi-asserted-by":"publisher","unstructured":"Sharma, A., Vondr\u00e1k, J.: Multiway cut, pairwise realizable distributions, and descending thresholds. In: Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, STOC 2014, pp. 724\u2013733. Association for Computing Machinery, New York (2014). https:\/\/doi.org\/10.1145\/2591796.2591866","DOI":"10.1145\/2591796.2591866"},{"key":"40_CR40","doi-asserted-by":"publisher","unstructured":"Shuguang, L., Xiao, X.: Multi-multiway cuts with edge labels. In: 2009 4th International Conference on Computer Science & Education, pp. 1860\u20131863 (2009). https:\/\/doi.org\/10.1109\/ICCSE.2009.5228230","DOI":"10.1109\/ICCSE.2009.5228230"},{"issue":"3","key":"40_CR41","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1137\/0208032","volume":"8","author":"LG Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of enumeration and reliability problems. SIAM J. Comput. 8(3), 410\u2013421 (1979). https:\/\/doi.org\/10.1137\/0208032","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2026: Theory and Practice of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-17801-5_40","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T17:53:06Z","timestamp":1770918786000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-17801-5_40"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032178008","9783032178015"],"references-count":41,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-17801-5_40","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":"13 February 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SOFSEM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Current Trends in Theory and Practice of Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Krakow","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Poland","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2026","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"9 February 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13 February 2026","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":"sofsem2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/sofsem.uj.edu.pl\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}