{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T22:58:04Z","timestamp":1781305084033,"version":"3.54.1"},"publisher-location":"Cham","reference-count":26,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032286901","type":"print"},{"value":"9783032286918","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-28691-8_3","type":"book-chapter","created":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T22:35:06Z","timestamp":1781303706000},"page":"32-46","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Stronger Hardness for Maximum Robust Flow and Randomized Network Interdiction"],"prefix":"10.1007","author":[{"given":"Jannik","family":"Matuschke","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,6,13]]},"reference":[{"key":"3_CR1","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1002\/net.10008","volume":"39","author":"CC Aggarwal","year":"2002","unstructured":"Aggarwal, C.C., Orlin, J.B.: On multiroute maximum flows in networks. Networks 39, 43\u201352 (2002)","journal-title":"Networks"},{"key":"3_CR2","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1002\/net.10001","volume":"38","author":"YP Aneja","year":"2001","unstructured":"Aneja, Y.P., Chandrasekaran, R., Nair, K.P.K.: Maximizing residual flow under an arc destruction. Networks 38, 194\u2013198 (2001)","journal-title":"Networks"},{"key":"3_CR3","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1016\/j.disopt.2016.05.002","volume":"22","author":"JF Baffier","year":"2016","unstructured":"Baffier, J.F., Suppakitpaisarn, V., Hiraishi, H., Imai, H.: Parametric multiroute flow and its application to multilink-attack network. Discret. Optim. 22, 20\u201336 (2016)","journal-title":"Discret. Optim."},{"key":"3_CR4","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1016\/j.orl.2015.11.005","volume":"44","author":"D Bertsimas","year":"2016","unstructured":"Bertsimas, D., Nasrabadi, E., Orlin, J.B.: On the power of randomization in network interdiction. Oper. Res. Lett. 44, 114\u2013120 (2016)","journal-title":"Oper. Res. Lett."},{"key":"3_CR5","doi-asserted-by":"publisher","first-page":"1218","DOI":"10.1287\/opre.2013.1200","volume":"61","author":"D Bertsimas","year":"2013","unstructured":"Bertsimas, D., Nasrabadi, E., Stiller, S.: Robust and adaptive network flows. Oper. Res. 61, 1218\u20131242 (2013)","journal-title":"Oper. Res."},{"key":"3_CR6","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/s10107-003-0396-4","volume":"98","author":"D Bertsimas","year":"2003","unstructured":"Bertsimas, D., Sim, M.: Robust discrete optimization and network flows. Math. Program. 98, 49\u201371 (2003)","journal-title":"Math. Program."},{"key":"3_CR7","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/0890-5401(91)90075-D","volume":"91","author":"SR Buss","year":"1991","unstructured":"Buss, S.R., Hay, L.: On truth-table reducibility to sat. Inf. Comput. 91, 86\u2013102 (1991)","journal-title":"Inf. Comput."},{"key":"3_CR8","doi-asserted-by":"publisher","first-page":"340","DOI":"10.1137\/S0097539790178069","volume":"25","author":"R Chang","year":"1996","unstructured":"Chang, R., Kadin, J.: The boolean hierarchy and the polynomial hierarchy: a closer connection. SIAM J. Comput. 25, 340\u2013354 (1996)","journal-title":"SIAM J. Comput."},{"key":"3_CR9","doi-asserted-by":"publisher","first-page":"378","DOI":"10.1002\/net.21739","volume":"69","author":"SR Chestnut","year":"2017","unstructured":"Chestnut, S.R., Zenklusen, R.: Hardness and approximation for network flow interdiction. Networks 69, 378\u2013387 (2017)","journal-title":"Networks"},{"key":"3_CR10","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1016\/j.orl.2019.10.012","volume":"48","author":"Y Disser","year":"2019","unstructured":"Disser, Y., Matuschke, J.: The complexity of computing a robust flow. Oper. Res. Lett. 48, 18\u201323 (2019)","journal-title":"Oper. Res. Lett."},{"key":"3_CR11","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1002\/net.20188","volume":"50","author":"D Du","year":"2007","unstructured":"Du, D., Chandrasekaran, R.: The maximum residual flow problem: NP-hardness with two-arc destruction. Networks 50, 181\u2013182 (2007)","journal-title":"Networks"},{"key":"3_CR12","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/s10107-017-1170-3","volume":"171","author":"C Gottschalk","year":"2018","unstructured":"Gottschalk, C., Koster, A.M., Liers, F., Peis, B., Schmand, D., Wierz, A.: Robust flows over time: models and complexity results. Math. Program. 171, 55\u201385 (2018)","journal-title":"Math. Program."},{"key":"3_CR13","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric algorithms and combinatorial optimization, vol.\u00a02. Springer Science & Business Media (2012)"},{"key":"3_CR14","doi-asserted-by":"publisher","unstructured":"Gr\u00fcne, C., Wulf, L.: On the complexity of recoverable robust optimization in the polynomial hierarch (2025). https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2025.52","DOI":"10.4230\/LIPIcs.MFCS.2025.52"},{"key":"3_CR15","doi-asserted-by":"crossref","unstructured":"Gr\u00fcne, C., Wulf, L.: Completeness in the polynomial hierarchy for many natural problems in bilevel and robust optimization. In: Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science, vol. 15620, pp. 256\u2013269 (2025)","DOI":"10.1007\/978-3-031-93112-3_19"},{"key":"3_CR16","doi-asserted-by":"crossref","unstructured":"Guruganesh, G., Sanita, L., Swamy, C.: Improved region-growing and combinatorial algorithms for k-route cut problems. In: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 676\u2013695. SIAM (2014)","DOI":"10.1137\/1.9781611973730.46"},{"key":"3_CR17","doi-asserted-by":"crossref","unstructured":"Hemachandra, L.A.: The strong exponential hierarchy collapses. In: Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, pp. 110\u2013122 (1987)","DOI":"10.1145\/28395.28408"},{"key":"3_CR18","doi-asserted-by":"publisher","first-page":"960","DOI":"10.1145\/185675.306789","volume":"41","author":"C Lund","year":"1994","unstructured":"Lund, C., Yannakakis, M.: On the hardness of approximating minimization problems. J. ACM 41, 960\u2013981 (1994)","journal-title":"J. ACM"},{"key":"3_CR19","unstructured":"Matuschke, J.: Stronger hardness for maximum robust flow and randomized network interdiction (2025). https:\/\/arxiv.org\/abs\/2511.06505"},{"key":"3_CR20","doi-asserted-by":"publisher","first-page":"2082","DOI":"10.1137\/18M1218273","volume":"34","author":"J Matuschke","year":"2020","unstructured":"Matuschke, J., McCormick, S.T., Oriolo, G.: Rerouting flows when links fail. SIAM J. Discret. Math. 34, 2082\u20132107 (2020)","journal-title":"SIAM J. Discret. Math."},{"key":"3_CR21","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/j.orl.2016.11.005","volume":"45","author":"J Matuschke","year":"2017","unstructured":"Matuschke, J., McCormick, S.T., Oriolo, G., Peis, B., Skutella, M.: Protection of flows under targeted attacks. Oper. Res. Lett. 45, 53\u201359 (2017)","journal-title":"Oper. Res. Lett."},{"key":"3_CR22","unstructured":"Riege, T., Rothe, J.: Completeness in the boolean hierarchy: exact-four-colorability, minimal graph uncolorability, and exact domatic number problems. Electron. Colloquium Comput. Complex (2006)"},{"key":"3_CR23","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/BF01530952","volume":"10","author":"V Rutenburg","year":"1994","unstructured":"Rutenburg, V.: Propositional truth maintenance systems: classification and complexity analysis. Ann. Math. Artif. Intell. 10, 207\u2013231 (1994)","journal-title":"Ann. Math. Artif. Intell."},{"key":"3_CR24","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/0304-3975(87)90049-1","volume":"51","author":"KW Wagner","year":"1987","unstructured":"Wagner, K.W.: More complicated questions about maxima and minima, and some closures of NP. Theoret. Comput. Sci. 51, 53\u201380 (1987)","journal-title":"Theoret. Comput. Sci."},{"key":"3_CR25","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0895-7177(93)90236-R","volume":"17","author":"RK Wood","year":"1993","unstructured":"Wood, R.K.: Deterministic network interdiction. Math. Comput. Model. 17, 1\u201318 (1993)","journal-title":"Math. Comput. Model."},{"key":"3_CR26","doi-asserted-by":"publisher","first-page":"1441","DOI":"10.1016\/j.dam.2010.04.008","volume":"158","author":"R Zenklusen","year":"2010","unstructured":"Zenklusen, R.: Network flow interdiction on planar graphs. Discret. Appl. Math. 158, 1441\u20131455 (2010)","journal-title":"Discret. Appl. Math."}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-28691-8_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T22:35:09Z","timestamp":1781303709000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-28691-8_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032286901","9783032286918"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-28691-8_3","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 June 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The author has no competing interests to declare that are relevant to the content of this article.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declaration of Competing Interests"}},{"value":"IPCO","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Integer Programming and Combinatorial Optimization","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Padua","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Italy","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":"17 June 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 June 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ipco2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/events.math.unipd.it\/ipco2026\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}