Constrained Cuts, Flows, and Lattice-Linearity
Robert Streit, Vijay K. Garg · 2025
Read Constrained Cuts, Flows, and Lattice-Linearity by Robert Streit, Vijay K. Garg (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-18141.txt.
Introduction
Robert Streit and Vijay K. Garg study minimum cuts in directed graphs whose edges carry capacities. It is known that all the min cuts of such a graph form a distributive lattice, and the paper recasts that lattice in a form built for parallel algorithms.
They describe the lattice as a regular predicate whose forbidden elements can be advanced in constant parallel time once a max flow is computed. From there they build parallel methods for min cut problems with extra constraints stated as lattice linear predicates. They also compute the irreducible elements of the sublattice of min cuts that meet a regular predicate, which yields a compact way to list all such cuts. Adding constraints is NP hard in general, they prove, but their poset slicing gives exact methods that beat brute force search.
Catalog record
| CREATOR | Robert Streit, Vijay K. Garg |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 56 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2512-18141
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Constrained Cuts, Flows, and Lattice-Linearity Thanks: Partially supported by NSF CNS-1812349, and the Cullen Trust for Higher Education Endowed Professorship. Robert Streit, Vijay K. Garg Abstract In a capacitated directed graph, it is known that the set of all min-cuts forms a distributive lattice [ 1 , 2 ] . Here, we describe this lattice as a regular predicate whose forbidden elements can be advanced in constant parallel time after precomputing a max-flow, so as to obtain parallel algorithms for min-cut problems with additional constraints encoded by lattice-linear predicates [ 3 ] . Some nice algorithmic applications follow. First, we use these methods to compute the irreducibles of the sublattice of min-cuts satisfying a regular predicate. By Birkhoff’s theorem [ 4 ] this gives a succinct representation of such cuts, and so we also obtain a general algorithm for enumerating this sublattice. Finally, though we prove computing min-cuts satisfying additional constraints is 𝖭𝖯 \mathsf{NP} -hard in general, we use poset slicing [ 5 , 6 ] for exact algorithms (with constraints not necessarily encoded by lattice-linear predicates) with better complexity than exhaustive search. We also introduce k k -transition predicates and strong advancement for improved complexity analyses of lattice-linear predicate algorithms in parallel settings, which is of independent interest. I Introduction Network problems are fundamental in combinatorial optimization, with applications such as transportation [ 7 ] , communication reliability [ 8 ] , and image processing [ 9 ] . Famously, the Max-Flow Min-Cut Theorem [ 10 ] establishes that the maximum flow (henceforth max-flow) value from a source s to a sink t in a capacitated graph equals the minimum capacity of a cut separating them (henceforth min-cut ). So, the prevailing method for generating min-cuts is running efficient max-flow algorithms (like [ 11 , 12 , 13 , 14 , 15 ] ) and operating on the resulting residual graph. Fig. 1 : An (s,t) -flow network with a unique min-cut and 2^{n} possible integral max-flows. The min-cut is that given by partitioning around the edges intersecting with the dashed lined. For any i , a max-flow saturates exactly one of the paths through a_{i} or b_{i} . Hence, there are 2^{n} integral flows. s a_{1} b_{1} a_{2} b_{2} \vdots a_{n} b_{n} c_{1} c_{2} \vdots c_{n} t 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 However, if one asks for a specific min-cut satisfying additional constraints for downstream applications, then generating the right min-cut is less straightforward. Complicating the matter is the sizes of the solution spaces, and a duality lacking clear association between the identities of flows and cuts. For example, there is an (s,t) -flow network with a single max-flow and an exponential number of min-cuts. One places n vertices, each with unit capacity edges between itself and s and itself and t . Then, the only max-flow will saturate every edge, while there are 2^{n} min-cuts corresponding to choosing either the edge to s or edge to t for each vertex. See Figure 3 . Conversely, there is a network with a single min-cut and exponential number of max-flows, which is best explained by examining Figure 1 . So, an efficient algorithm for min-cuts under additional constraints must use additional structure. One such structure is the distributive lattice of min-cuts [ 1 , 2 ] . Recently, [ 3 ] showed that many problems on distributive lattices can be solved in a simple and unifying way using lattice-linear predicate detection . The idea is to model the problem as satisfaction of a lattice-linear predicate, which informally is such that the satisfying preimage forms a semilattice under some meet operation. Lattice-linear predicate detection can be solved by a universal procedure admitting simple parallel algorithmic implementations [ 3 ] . Due to its generality, this idea has been applied to a diverse selection of problems detailed in Section II . And, although identifying min-cuts satisfying additional constraints is \mathsf{NP} -hard in general (see Section V ), by modeling min-cut computations through a lattice-linear predicate we provide an efficient method, Algorithm 2 , for min-cuts satisfying additional constraints encoded by lattice-linear predicates. We give some examples of lattice-linear predicates pertaining to min-cut problems in Section III-B . In particular, we propose implicational cuts that can be used to preserve some graph structure of interest in one side of the cut, and describe uniformly directed cuts , examined in prior literature in the context of network reliability problems [ 16 , 17 ] and efficient estimators of random variables on networks [ 18 , 19 ] , as lattice-linear predicates as well. TABLE I : Our algorithmic contributions. T_{B} and W_{B} are the (parallel) time and work complexities of computing forbidden vertices of the lattice-linear predicate over the cuts on a graph with n vertices and m edges, while T_{\text{MF}} and W_{\text{MF}} are the same for max-flows. The exception to this is Algorithm 5 , where T_{B} and W_{B} are the complexities of evaluating B . Algorithm Time Work Notes Min-cuts satisfying lattice-linear B (Alg. 2 ) O(T_{\text{MF}}+nT_{B}) O(W_{\text{MF}}+n(m+W_{B})) General lattice-linear O(T_{\text{MF}}+kT_{B}) O(W_{\text{MF}}+k(m+W_{B})) k -transition with strong advancement Irreducibles of min-cuts satisfying regular B (Alg. 3 ) O(T_{\text{MF}}+nT_{B}) O(W_{\text{MF}}+n^{2}(m+n+W_{B})) General regular O(T_{\text{MF}}+kT_{B}) O(W_{\text{MF}}+kn(m+n+W_{B})) k -transition with strong advancement Enumerating min-cuts satisfying regular B (Alg. 4 ) O(\log n) delay O(n^{2}) delay Complexity per listed cut, precomputation omitted. Min-cut satisfying B\wedge B_{\text{reg}} , B_{\text{reg}} regular and B general (Alg. 5 ) O(T_{\text{MF}}+nT_{\text{reg}}+(R\log n)\,T_{B}) O\bigl(W_{\mathrm{MF}}+n^{2}\bigl(m+n+W_{\mathrm{reg}}\bigr)+(Rn^{2})\,W_{B}\bigr) R is number of min-cuts satisfying B_{\text{reg}} With that said, the appeal of lattice-linear predicate detection lies in its flexibility. Because of this, we are able to derive many algorithmic applications in Section VI . Specifically, we begin by examining methods for computing the irreducibles of the sublattice of min-cuts satisfying a regular predicate, that is a predicate whose satisfying preimage is closed under meet and join, in Section VI-A . This has downstream application towards constraint based extensions of recent works proposing efficient algorithms for diverse solutions to min-cuts and other combinatorial optimization problems on distributive lattices which operate on the irreducibles [ 20 , 21 , 22 ] . Furthermore, in Section V-B we introduce k -transition predicates , which allow us to get improved instance dependent guarantees for the parallel time complexities of lattice-linear predicate detection algorithms based on the structure of the given predicate. We use this notion to tighten the analysis of our algorithms, and show that one can identify irreducible min-cuts (in absence of any other constraints) in parallel time equivalent to computing a single max-flow. Then, using the succinct representation provided by the irreducibles, we propose an enumeration algorithm in Section VI-B based off traversing the ideals of the subposet of irreducible elements of min-cuts satisfying any regular predicate. The generality of this method allows one to apply our algorithm to list the (unconstrained) min-cuts, the uniformly directed min-cuts, and any other constraint satisfying min-cuts defined by regular predicates without the need to modify the algorithm or rederive new results. Finally, in Section VI-C we use our enumeration method to obtain a poset-slicing [ 5 , 6 ] algorithm for identifying min-cuts satisfying general (possibly non-lattice-linear) predicates, with complexity better than simple