Spanning Tree Solution for challenge 3

[emmanuel2406]

We found a clever spanning tree heuristic to encourage the connectivity constraint for the final challenge

Overview of algorithm:

1. we calculate a statistically random spanning tree of a unweighted graph (using efficient linear algorithm such as Kruskal's).
2. we proved theoretically that every bad max cut that generates disconnected connected components in one of the partitioned sets will cut the cut the spanning tree is $\ge 2$ edges.
3. for good max cuts, we have the heuristic, that most of them will only cut a random spanning tree in one edge. However, the number of edges that the cut intersects with the spanning tree acts nonetheless as a good heuristic for connectivity.
4. This heuristic is only a measure of connectivity and does not maximize the number of edges in a good cut. We linearly combine this with the Hamiltonian objective from challenge 1 and fine-tune the weights. Note that the penalty coefficient should be quite large.

Repeated Sampling.

Note that this spanning tree heuristic has no false positives, however, there may be false negatives when good cuts have a higher than normal intersection with the segment tree.
To deal with this we sample k different segment trees for k small (k = 2, 3), and then this amplifies the probability of no false negatives.

Yours sincerely,
Harvard Bloch Heads

[mulliganaceous]

Hey, I have been thinking of this method for quite a while...
qubo2_annotated3.pdf

See page 4

[TumCucTom]

we had a similar idea couldn't actually implement it. Nice one guys!

[mulliganaceous]

I couldn't implement the whole thing at the very end...

No disconnections

This term is linear in $e_{vw}$.
$\sum_{(v, w) \notin E} e_{vw} = 0$

No intergroup pairings

This term is cubic in the $e$ and $x$. Let's see if this is compatible with our QUBO solver...
$\sum_{v = 0}^{N - 1} \sum_{w = 0}^{N - 1} (1 - x - y + 2xy) e_{vw} = 0$

All vertices must be used

These $N$ terms are linear in $e_{vw}$.
$\forall v \sum_{w = v + 1}^{N - 1} e_{vw} \geq 1 $