Unfortunately, naively adapting Karger’s algorithm (i.e. by selecting vertices uniformly at random and merging them) does not give a reasonable probability of success for correctly selecting a specific subset.
Let
be the set minimizing the symmetric submodular function
. Let
. Since we do not know
or have any reason to suspect a specific cardinality of a beyond restricting
(because of symmetry).
The probability of selecting an element which is in
is
, since we must select
other elements for the optimal set out of
elements. Taking this repeatedly, we get
In the best case (when
), the probability of correctly selecting a subset is
, but in the worst case (when
) we get,
, the inverse of the
nd central binomial coefficient. This is in turn equal to
, where
is the
th Catalan number. In other words, we find that the probability of success using this method can be exponentially small for some values of
. (although our time complexity remains only
, since unlike graphs we can contract much faster)
Amplification? The probability of failure is
Using amplification
times, we find that to get a high probability of success, we need
, which is clearly exponential in
.
The problem we find is that we do not have enough information in each contraction, and are forced to blindly guess, while for hypergraphs we can choose the edge proportional to how many edges it can contract at once.
xhis is the same process as here: https://jeffe.cs.illinois.edu/teaching/algorithms/notes/08-mincut.pdf
😔
Try to form a group where you select each element with probability
But what if you had a set which “stemmed” from a smaller set that had the same pattern of decreases.
Is it true that the optimal solution
Symmetric submodularity is closed under union. For elements of size 1, it is trivial
In other words, that we want to show that
Assumptions:
—
Suppose
and let
. We must show that
For V=2,
and
, so the statement holds for the basis.
Assume that for
, the statement holds. Then we want to show for
, that
Take some arbitrary
since by the definition,
is positive
Handshake Lemma for Symmetric Submodular Functions
// Can be shown inductively
For hypergraphs
Let
Let
We are trying to contract a star. Select the center of the star
with probability
Then, contract vertex
from
with probability
For the pairs
crossing the cut with
as the center of the star,
, since the weight of any hyperedge crossing the cut is at most
, and we double count 2-edges.
Also observe that
.
By the handshake lemma,
Putting it all together, the probabilty of contracting any edge (given that we chose
as the center of the star) crossing the minimum cut is
The maximum number of vertices in
with the pair
crossing the cut is at most
, so the probability of crossing the cut given we chose
as the center of the star is at most
. There are at most
vertices in the minimum cut, so the probability of crossing the cut from a vertex in the minimum cut is
Let
In one round, the expected number of pairs to contract is.
So for the sake of making progress, I guess the expected number is fine after we have selected a center. Now I get why you have to do things “proportional” and I also have a lot better intuition for hyperedges (not that that means anything neccessarily). —
If you were to refuse to contract a pair
, every other vertex
—
I suppose the point of all minimum cut algorithms is to look at the proportion of weight crossing the cut, regardless of size. With constant rank, then this is obviously the same no matter what, but otherwise I guess its more complicated
I want to say that contracting proportional to the expected weight of a pair, then the weight of a pair should work? But then you can cross the cut easily if that side of the cut is too light
The probability of contracting a hyperedge is proportional to
, so the probability of contracting a hyperedge is
. The probability of contracting a pair is
.
There are exactly
vertices to contract in every hyperedge, so each hyperedge contributes
to the numerator of the probability.
First, I guess it is important to note that
.
, so
. This implies that
.
For the numerator,
, since the 2-edges are double-counted.
Since
is strictly greater than
by definition, we need to approximate it by using
and
. We know
and
. We can also compute (in linear time)
The maximum number of hyperedges containing the pair is
—
Emily says
Contract a star by
Choosing a vertex uniformly at random
Contract neighbors with probability
For graphs this is the same as contracting an edge uniformly at random
For hypergraphs this is
The probability of crossing the cut is
How many pairs do you contract in expectation?
We contract at least one thing because of the Handshake Lemma.
What about for symmetric submodular functions?
This holds true if
for
—
A thought, was is the relationship between
and
nah that doesn’t work for hypergraphs.
—
We are trying to contract a star. Select the center of the star
with probability
Then, contract vertex
from
with probability proportional to
Each pair is contracted with probability
Create a set
With probability
, contract
and repeat from a new vertex
. Otherwise, select
proportional to
and repeat the coin flip procedure.
Let
represent the probability of contracting a pair
which crosses the cut
The probability of selecting a set
which crosses the minimum cut is
Ok so the probability of contracting across the cut is the probability of contracting at any point.
Thus the probability of breaking the cut in one round is
The probability of contracting any pair is
. Thus, in expectation, we will contract a pair on the
th iteration.
This is repeated for
vertices, this gives so the algorithm takes
in expectation to contract all vertices.
Does this extend to symmetric submodular functions? Given vertices
in a hypergraph: For a contraction of a pair
with probability
, where
is a bias
, and
Note on submodularity: 2-edges may be double counted, by the cut function, thus for each pair
which crosses the minimum cut,
At most
pairs of vertices cross the minimum cut. Thus the summed probabilities of selecting across the minimum cut is:
For the optimal
We expect to try to attempt to contract
times
We will stop when the size of the graph is
,
. Thus we must contract
vertices.
. We want this to be
is the running time, where the second part is from running Queyranne’s algorithm
For example, with
and
, the probability of success is
, and the running time is