2026-08-25T18:47:26Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27255 2026-08-25T13:18:19Z ddc:004 open_access

All-Pairs kth Mincuts: Combinatorial and Structural Results Baswana, Surender Roy, Anupam mincut second mincut kth mincut suboptimal cuts compact structure all pairs multi terminal cuts generalization of Gomory Hu tree ancestor tree generalization of all pairs mincuts Let G be an undirected graph on a set V of n vertices. For any non-empty subset A⊊ V, cut defined by A is the ordered pair (A,V\A). Suppose each cut is assigned a value, which is any arbitrary real number. Let u,v ∈ V be any pair of vertices. A cut is said to be a (u,v)-cut if it separates u and v. A (u,v)-cut of the minimum value is called a (u,v)-mincut. A 2nd (u,v)-mincut is a (u,v)-cut of second minimum value. We can define k-th mincut accordingly. We present the following results for the all-pairs k-th mincuts. (1) Distinct Values of all-pairs k-th Mincuts: There exist k spanning trees on V such that for any pair (u,v), the value of k-th (u,v)-mincut is equal to the capacity of an edge on the (u,v)-path in one of the k trees. We also show a matching lower bound of Ω(min{kn,n²}). Our result generalizes the well-known result by Gomory and Hu [JSIAM 1961] stating that there are at most n-1 distinct values of all-pairs mincuts. (2) Ancestor Trees for all-pairs k-th Mincuts: In 1991, Cheng and Hu [AOR 1991] invented a rooted binary tree, called ancestor tree, whose leaves are the vertices of the graph and each internal node stores a cut with the following property. For any pair (u,v), the cut stored at their lowest common ancestor (LCA) is a (u,v)-mincut. We introduce a tree called gen-ancestor tree, that generalizes the ancestor tree for k-th mincuts, and achieve the following result. There exists a set of 𝒪(klog n) gen-ancestor trees such that, for any pair (u,v), a k-th (u,v)-mincut is stored at the LCA of u and v in at least one of these trees. (3) Data Structures: We present the following data structures for all-pairs k-th mincuts. (i) There exists an 𝒪(nlog n) space data structure that can report the value of 2nd (u,v)-mincut in 𝒪(log n) time for any given pair (u,v). We generalize this data structure for k-th mincuts with a factor of k² in the space and query time. (ii) There exists an 𝒪(kn² log n) space data structure that can report a k-th (u,v)-mincut (A,V\A) in 𝒪(|A|) time for any given pair (u,v). For any constant k, the bounds stated above match, up to a logarithmic factor, the best-known bounds guaranteed by the data structure for all-pairs mincuts (Cheng and Hu [AOR 1991]). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Surender Baswana and Anupam Roy 2026 Is Part Of LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2026.119 urn:nbn:de:0030-drops-272553 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.119 eng https://creativecommons.org/licenses/by/4.0/legalcode