{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,8]],"date-time":"2026-03-08T22:17:00Z","timestamp":1773008220922,"version":"3.50.1"},"reference-count":26,"publisher":"Wiley","issue":"3","license":[{"start":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T00:00:00Z","timestamp":1767916800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/4.0\/"},{"start":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T00:00:00Z","timestamp":1767916800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/doi.wiley.com\/10.1002\/tdm_license_1.1"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["GRK 2982, 516090167"],"award-info":[{"award-number":["GRK 2982, 516090167"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Networks"],"published-print":{"date-parts":[[2026,4]]},"abstract":"<jats:title>ABSTRACT<\/jats:title>\n                  <jats:p>\n                    The minimum \u2010\u2010cut problem is one of the most\u2010studied problems in discrete optimization and has a unique complexity status in multi\u2010objective optimization. Even though the single\u2010objective version of the problem can be solved in polynomial time, it has been shown in the seminal work of Papadimitriou and Yannakakis (2000) that there does not exist a multi\u2010objective fully polynomial\u2010time approximation scheme (MFPTAS) for the minimum \u2010\u2010cut problem unless . This holds both for the case of  objective functions with arc capacities in  and for  objective functions with general capacities, and even for tractable instances where the number of non\u2010dominated points is only quadratic in the input size. In this article, we strengthen these results by showing that, assuming , there does not exist an MFPTAS for the minimum \u2010\u2010cut problem with two objectives and arc capacities in , nor for the minimum \u2010\u2010cut problem with two objectives and arc capacities in . This advancement is particularly interesting since the considered problem variants are the only known problems in multi\u2010objective optimization that do not admit an MFPTAS even though their single\u2010objective versions are solvable in polynomial time and the problems are\n                    <jats:italic>tractable<\/jats:italic>\n                    , that is, the numbers of non\u2010dominated points are polynomial (even linear) in the input size. Furthermore, we complement this result by showing that, on graphs of bounded tree\u2010width, the minimum \u2010\u2010cut problem with polynomially bounded arc capacities can be solved exactly in polynomial time for any constant number of objectives.\n                  <\/jats:p>","DOI":"10.1002\/net.70023","type":"journal-article","created":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T13:31:35Z","timestamp":1767965495000},"page":"312-321","update-policy":"https:\/\/doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Tractable but Hard to Approximate: The Bi\u2010Objective Minimum s\u2010t\u2010Cut Problem With Binary Capacities"],"prefix":"10.1002","volume":"87","author":[{"given":"Jan","family":"Boeckmann","sequence":"first","affiliation":[{"name":"Johannes Kepler University Linz Institute for Business Analytics and Technology Transformation  Linz Austria"}]},{"given":"Stephan","family":"Helfrich","sequence":"additional","affiliation":[{"name":"Karlsruhe Institute of Technology, Operations of Critical Infrastructures Institute of Information Security and Dependability (KASTEL)  Karlsruhe Germany"}]},{"given":"Oliver","family":"Bachtler","sequence":"additional","affiliation":[{"name":"RPTU Kaiserslautern\u2010Landau Department of Mathematics  Kaiserslautern Germany"}]},{"given":"Stefan","family":"Ruzika","sequence":"additional","affiliation":[{"name":"RPTU Kaiserslautern\u2010Landau Department of Mathematics  Kaiserslautern Germany"}]},{"given":"Clemens","family":"Thielen","sequence":"additional","affiliation":[{"name":"Technical University of Munich Campus Straubing for Biotechnology and Sustainability  Straubing Germany"}]}],"member":"311","published-online":{"date-parts":[[2026,1,9]]},"reference":[{"key":"e_1_2_15_2_1","volume-title":"Network Flows","author":"Ahuja R. K.","year":"1993"},{"key":"e_1_2_15_3_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.21739"},{"key":"e_1_2_15_4_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.19.1.24"},{"key":"e_1_2_15_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2021.07.008"},{"key":"e_1_2_15_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/0109047"},{"key":"e_1_2_15_7_1","volume-title":"Multicriteria Optimization","author":"Ehrgott M.","year":"2005"},{"key":"e_1_2_15_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-57311-8_5"},{"key":"e_1_2_15_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-46618-2_15"},{"key":"e_1_2_15_10_1","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.2020.1028"},{"key":"e_1_2_15_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2000.892068"},{"key":"e_1_2_15_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13962-8_20"},{"key":"e_1_2_15_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224\u2010021\u201010066\u20105"},{"key":"e_1_2_15_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2017.07.003"},{"key":"e_1_2_15_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2008.04.004"},{"key":"e_1_2_15_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107\u2010023\u201001987\u20109"},{"key":"e_1_2_15_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453\u2010019\u201000609\u20101"},{"key":"e_1_2_15_18_1","series-title":"LNCS","first-page":"308","volume-title":"Proceedings of the 13th International Computer Science Symposium in Russia (CSR)","author":"Wojtczak D.","year":"2018"},{"key":"e_1_2_15_19_1","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.12.1.57.11901"},{"key":"e_1_2_15_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.09.003"},{"key":"e_1_2_15_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/800119.803884"},{"key":"e_1_2_15_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719796"},{"key":"e_1_2_15_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304\u20103975(97)00228\u20104"},{"key":"e_1_2_15_24_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxm037"},{"key":"e_1_2_15_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793251219"},{"key":"e_1_2_15_26_1","volume-title":"On Tree\u2010Decompositions and Their Algorithmic Implications for Bounded\u2010Treewidth Graphs","author":"Satzinger C.","year":"2014"},{"key":"e_1_2_15_27_1","series-title":"Graduate Texts in Mathematics","volume-title":"Graph Theory","author":"Diestel R.","year":"2016"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.70023","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/full-xml\/10.1002\/net.70023","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.70023","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,8]],"date-time":"2026-03-08T20:16:40Z","timestamp":1773001000000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.70023"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,1,9]]},"references-count":26,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,4]]}},"alternative-id":["10.1002\/net.70023"],"URL":"https:\/\/doi.org\/10.1002\/net.70023","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,1,9]]},"assertion":[{"value":"2025-04-23","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-12-06","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-01-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}