2
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ Do you care about structure/the graph being different each time? Because you can just make the complete graph on $k$ vertices. Or if you want it bipartite, make the complete bipartite graph $K_{k,k}$. $\endgroup$ – Ryan Sep 27 '16 at 20:26
  • $\begingroup$ Yes I'd like it to be different each time, even sparse if possible. A deterministic approach that, for example, gives the same degree sequence each time would be okay as a starting point ... but not the complete graph :) $\endgroup$ – user1798883 Sep 27 '16 at 22:00
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This is fantastic, thank you! Although the Harary paper is not for bipartite graphs, it's a great starting point. The reference to the relationship between min degree and edge-connectivity is extremely useful. In fact, from sampling experiments the equality between the two seems to be quite common -- as least in the bipartite instances I've tried -- so it'll be great to look at this literature. $\endgroup$ – user1798883 Sep 28 '16 at 18:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.