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