{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:37:11Z","timestamp":1787323031614,"version":"build-2736575974"},"reference-count":14,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2022,9]]},"abstract":"<jats:p>Gomory--Hu (GH) trees are a classical sparsification technique for graph connectivity. For an edge-capacitated undirected graph $G=(V,E)$ and subset $Z \\subseteq V$ of terminals, a GH tree is an edge-capacitated tree $T=(Z,E(T))$ such that for every $u,v \\in Z$, the value of the minimum capacity $uv$ cut in $G$ is the same as in $T$. It is well-known that there does not always exist a GH tree which is a subgraph (or minor if $Z \\neq V$) of $G$. We characterize those graph-terminal pairs $(G,Z)$ which always admit such a tree. We show that these are the graphs which have no terminal-$K_{2,3}$ minor, that is, a $K_{2,3}$ minor whose nodes each corresponds to a terminal. We then show that the pairs $(G,Z)$ which forbid such $K_{2,3}$ terminal-minors arise, roughly speaking, from so-called Okamura--Seymour instances, planar graphs whose outside face contains all terminals. One consequence is a result on cut-sufficient pairs $(G,H)$, that is, multiflow instances where the cut condition is sufficient to guarantee a multiflow for any capacity\/demand weights on $G\/H$. Our results characterize the pairs $(G,Z)$ where $G$ is a graph, $Z \\subseteq V(G)$, such that $(G,H)$ is cut-sufficient for any demand graph $H$ on $Z$.<\/jats:p>","DOI":"10.1137\/20m1356968","type":"journal-article","created":{"date-parts":[[2022,7,5]],"date-time":"2022-07-05T10:07:48Z","timestamp":1657015668000},"page":"1567-1585","source":"Crossref","is-referenced-by-count":4,"title":["When Do Gomory--Hu Subtrees Exist?"],"prefix":"10.1137","volume":"36","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5460-9995","authenticated-orcid":true,"given":"Guyslain","family":"Naves","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bruce","family":"Shepherd","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2022,7,5]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2213980"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973075.96"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2012.11.002"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1137\/0109047"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1137\/0203015"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-24488-9"},{"key":"atypb7","volume-title":"North-Holland","author":"Lomonosov M. V.","year":"1985"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1016\/S0095-8956(81)80012-3"},{"key":"atypb9","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency","author":"Schrijver A.","year":"2003"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(80)90158-2"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230100108"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(81)80033-9"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1145\/322203.322207"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(80)80039-4"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/20M1356968","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:37:37Z","timestamp":1787319457000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/20M1356968"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,5]]},"references-count":14,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,9]]}},"alternative-id":["10.1137\/20M1356968"],"URL":"https:\/\/doi.org\/10.1137\/20m1356968","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,7,5]]}}}