Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
Is there a constructive way to generate a graph with a fixed min cut equal to $k$? One approach is to generate a random graph and then try to make edges alterations (additions, deletions, swaps) to get the desired min cut -- but I am wondering if there is a more systematic procedure?
Ideally I would want to generate a random instance of a graph with min-cut=$k$, and I would want it to be bipartite, but insight on any part of this question would be helpful!
Thanks in advance!
In his 1962 paper "The Maximum Connectivity of a Graph", Harary describes a way to construct for integers $p$ and $q$ with $q\ge p-1$ a way to construct a graph with $p$ vertices and $q$ edges that is $k=\lfloor 2q/p\rfloor$-connected. Roughly, the idea is to give indices from $0$ to $p-1$ to the $p$ vertices and then add edges between vertices whose indices (modulo $p$) differ by at most $k/2$ (the exact construction depends on whether or not $2q/p$ is an integer).
One could start with these graphs and then perturb them by adding and removing edges without changing the connectivity. The graphs will not be bipartite, however.
Another easy way of creating random graphs with a certain edge-connectivity value is to exploit those cases in which edge-connectivity and minimum degree are identical since creating random graphs with a fixed minimum degree is much easier. Such conditions, also for bipartite graphs, are discussed for example in the paper On equality of edge-connectivity and minimum degree of a graph by Plesník and Znám.
