{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T08:15:45Z","timestamp":1767860145197,"version":"3.49.0"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2023,10,14]],"date-time":"2023-10-14T00:00:00Z","timestamp":1697241600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Tapas Mishra Memorial Chair at Indian Institute of Technology Kanpur"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2023,10,31]]},"abstract":"\n Let\n G<\/jats:italic>\n be a directed multi-graph on\n n<\/jats:italic>\n vertices and\n m<\/jats:italic>\n edges with a designated source vertex\n s<\/jats:italic>\n and a designated sink vertex\n t<\/jats:italic>\n . We study the (\n s,t<\/jats:italic>\n )-cuts of capacity minimum+1 and as an important application of them, we give a solution to the dual-edge sensitivity for (\n s,t<\/jats:italic>\n )-mincuts\u2014reporting an (\n s,t<\/jats:italic>\n )-mincut upon failure or insertion of any pair of edges.\n <\/jats:p>\n \n Picard and Queyranne [Mathematical Programming Studies, 13(1): 8\u201316 (1980)] showed that there exists a directed acyclic graph (DAG) that compactly stores all minimum (\n s,t<\/jats:italic>\n )-cuts of\n G<\/jats:italic>\n . This structure also acts as an oracle for the single-edge sensitivity of minimum (\n s,t<\/jats:italic>\n )-cut. For undirected multi-graphs, Dinitz and Nutov [STOC, 509\u2013518 (1995)] showed that there exists an \ud835\udcaa(\n n<\/jats:italic>\n ) size 2-level Cactus model that stores all global cuts of capacity minimum+1. However, for minimum+1 (\n s,t<\/jats:italic>\n )-cuts, no such compact structure exists till date. We present the following structural and algorithmic results on minimum+1 (\n s,t<\/jats:italic>\n )-cuts.\n \n \n (1)<\/jats:label>\n \n Structure:<\/jats:bold>\n There is an \ud835\udcaa(\n m<\/jats:italic>\n ) size 2-level DAG structure that stores all minimum+1\n (s,t)<\/jats:italic>\n -cuts of\n G<\/jats:italic>\n such that each minimum+1 (\n s,t<\/jats:italic>\n )-cut appears as 3-transversal cut\u2014it intersects any path in this structure at most thrice. We also show that there is an \ud835\udcaa(\n mn<\/jats:italic>\n ) size structure for storing and characterizing all minimum+1\n (s,t)<\/jats:italic>\n -cuts in terms of 1-transversal cuts.\n <\/jats:p>\n \n <\/jats:list-item>\n \n (2)<\/jats:label>\n \n Data structure:<\/jats:bold>\n There exists an \ud835\udcaa(\n \n n\n 2<\/jats:sup>\n <\/jats:italic>\n ) size data structure that, given a pair of vertices {u,v} that are not separated by an (\n s,t<\/jats:italic>\n )-mincut, can determine in \ud835\udcaa(1) time if there exists a minimum+1 (\n s,t<\/jats:italic>\n )-cut, say (\n A,B<\/jats:italic>\n ), such that\n s,u \u220a A<\/jats:italic>\n and\n v,t\u220a B<\/jats:italic>\n ; the corresponding cut can be reported in \ud835\udcaa(|\n B<\/jats:italic>\n |) time.\n <\/jats:p>\n <\/jats:list-item>\n \n (3)<\/jats:label>\n \n Sensitivity oracle:<\/jats:bold>\n There exists an \ud835\udcaa(\n n<\/jats:italic>\n 2<\/jats:sup>\n ) size data structure that solves the dual-edge sensitivity problem for\n (s,t)<\/jats:italic>\n -mincuts. It takes \ud835\udcaa(1) time to report the capacity of a resulting\n (s,t)<\/jats:italic>\n -mincut\n (A,B)<\/jats:italic>\n and \ud835\udcaa(|\n B<\/jats:italic>\n |) time to report the cut.\n <\/jats:p>\n <\/jats:list-item>\n \n (4)<\/jats:label>\n \n Lower bounds:<\/jats:bold>\n For the data structure problems addressed in results (2) and (3) above, we also provide a matching conditional lower bound. We establish a close relationship among three seemingly unrelated problems\u2014all-pairs directed reachability problem, the dual-edge sensitivity problem for (\n s,t<\/jats:italic>\n )-mincuts, and the problem of reporting the capacity of ({\n x,y<\/jats:italic>\n }, {\n u,v<\/jats:italic>\n })-mincut for any four vertices\n x,y,u,v<\/jats:italic>\n in\n G<\/jats:italic>\n . Assuming the Directed Reachability Hypothesis by Patrascu [SIAM J. Computing, 827\u2013847 (2011)] and Goldstein et\u00a0al. [WADS, 421\u2013436 (2017)], this leads to\n \n \\(\\tilde{\\Omega }(n^2)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n lower bounds on the space for the latter two problems.\n <\/jats:p>\n <\/jats:list-item>\n <\/jats:list>\n <\/jats:p>","DOI":"10.1145\/3623271","type":"journal-article","created":{"date-parts":[[2023,9,7]],"date-time":"2023-09-07T11:08:28Z","timestamp":1694084908000},"page":"1-41","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Minimum+1 (\n s, t<\/i>\n )-cuts and Dual-edge Sensitivity Oracle"],"prefix":"10.1145","volume":"19","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8657-7182","authenticated-orcid":false,"given":"Surender","family":"Baswana","sequence":"first","affiliation":[{"name":"Indian Institute of Technology Kanpur, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0902-0916","authenticated-orcid":false,"given":"Koustav","family":"Bhanja","sequence":"additional","affiliation":[{"name":"Indian Institute of Technology Kanpur, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1222-252X","authenticated-orcid":false,"given":"Abhyuday","family":"Pandey","sequence":"additional","affiliation":[{"name":"Limestone, Tower Research Capital LLC, United States"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,10,14]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1137\/17M114306X"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1137\/16M1087643"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-018-0452-3"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-022-00978-0"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977073.27"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1995.492466"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536431"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-021-00879-8"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2022.25"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977073.129"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1137\/090758039"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00064"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53536-3_12"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2016.130"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705429847"},{"key":"e_1_3_2_17_2","first-page":"290","article-title":"On the structure of the system of minimum edge cuts in a graph","author":"Dinitz Efim A.","year":"1976","unstructured":"Efim A. Dinitz, Alexander V. Karzanov, and Michael V. Lomonosov. 1976. On the structure of the system of minimum edge cuts in a graph. Issledovaniya po Diskretnoi Optimizatsii (1976), 290\u2013306.","journal-title":"Issledovaniya po Diskretnoi Optimizatsii"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1109\/ISTCS.1993.253480"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/225058.225268"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797330045"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009195"},{"key":"e_1_3_2_22_2","first-page":"754","volume-title":"Doklady Akademii Nauk","author":"Dinitz Yefim A.","year":"1970","unstructured":"Yefim A. Dinitz. 1970. An algorithm for the solution of the problem of maximal flow in a network with power estimation. In Doklady Akademii Nauk, Vol. 194. Russian Academy of Sciences, 754\u2013757."},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973068.56"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520002"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1956-045-5"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1137\/0222002"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585926"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1137\/19M1258530"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-62127-2_36"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1137\/0109047"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/3174803"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2017.127"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.163"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/331605.331608"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/234533.234534"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/3274663"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/357062.357071"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00017"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.4064\/fm-10-1-96-115"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/2767386.2767408"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520047"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/2976741"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1137\/09075336X"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0120902"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-55719-9_88"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3623271","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3623271","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:36:26Z","timestamp":1750178186000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3623271"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,10,14]]},"references-count":44,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,10,31]]}},"alternative-id":["10.1145\/3623271"],"URL":"https:\/\/doi.org\/10.1145\/3623271","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,10,14]]},"assertion":[{"value":"2022-10-26","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-08-26","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-10-14","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}