Towards the Characterization of Terminal Cut Functions: a Condition for Laminar Families
Preprint
Abstract
We study the following characterization problem. Given a set $T$ of terminals and a $(2^{|T|}-2)$-dimensional vector $\pi$ whose coordinates are indexed by proper subsets of $T$, is there a graph $G$ that contains $T$, such that for all subsets $\emptyset\subsetneq S\subsetneq T$, $\pi_S$ equals the value of the min-cut in $G$ separating $S$ from $T\setminus S$? The only known necessary conditions are submodularity and a special class of linear inequalities given by Chaudhuri, Subrahmanyam, Wagner and Zaroliagis. Our main result is a new class of linear inequalities concerning laminar families, that generalize all previous ones. Using our new class of inequalities, we can generalize Karger's approximate min-cut counting result to graphs with terminals.
Keywords
All Related Versions
This publication has 9 references indexed in Scilit:
- On (1 + ɛ)-Approximate Flow Sparsifiers2024
- Improved Guarantees for Vertex Sparsification in Planar GraphsSIAM Journal on Discrete Mathematics, 2020
- An Exponential Lower Bound for Cut Sparsifiers in Planar GraphsAlgorithmica, 2018
- Realizing symmetric set functions as hypergraph cut capacityDiscrete Mathematics, 2016
- On mimicking networks representing minimum terminal cutsInformation Processing Letters, 2014
- A Factor 2 Approximation Algorithm for the Generalized Steiner Network ProblemCombinatorica, 2001
- Characterizing Multiterminal Flow Networks and Computing Flows in Networks of Small TreewidthJournal of Computer and System Sciences, 1998
- Computing All Small Cuts in an Undirected NetworkSIAM Journal on Discrete Mathematics, 1997
- On the number of small cuts in a graphInformation Processing Letters, 1996