Constrained Cuts, Flows, and Lattice-Linearity
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914212014456832 |
|---|---|
| author | Streit, Robert Garg, Vijay K. |
| author_facet | Streit, Robert Garg, Vijay K. |
| contents | 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 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$-transition predicates and strong advancement for improved complexity analyses of lattice-linear predicate algorithms in parallel settings, which is of independent interest. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_18141 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Constrained Cuts, Flows, and Lattice-Linearity Streit, Robert Garg, Vijay K. Data Structures and Algorithms Distributed, Parallel, and Cluster Computing 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 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$-transition predicates and strong advancement for improved complexity analyses of lattice-linear predicate algorithms in parallel settings, which is of independent interest. |
| title | Constrained Cuts, Flows, and Lattice-Linearity |
| topic | Data Structures and Algorithms Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2512.18141 |