3
$\begingroup$

I'm trying to find a method to randomly split a connected planar graph $G$ into two connected components, such that the sum of the weights of vertices in each component are relatively close. (If there is a >10% difference difference, the split is simply not considered valid.) Additionally, I want to be able to calculate the chance that $G$ is split into these two components by this method.

I have solved the problem if we do not care about the size of components. Simply create a uniformly random spanning tree of $G$, and randomly remove one of it's edges, breaking it into two components $A,B$. Then, calculate the number spanning trees in each component, and and multiply by the number of edges between $A$ and $B$, $e(A,B)$. This gets how many spanning trees can possibly yield $G$. In any spanning tree, each edge gives a different split, and there are always $(n-1)$ possible edges we can remove. So: $$p(A,B) = t(A)t(B)e(A,B) \frac{1}{t(A \cup B)(n-1)}$$

(The last part is not really necessary because it stays constant, as I only need something which is proportional to the probability.)

I'm looking for an algorithm which can practically be done upon relatively small graphs, with order of roughly 50 vertices. The method must have non-zero probabilities for a large number of splits (hopefully all, but a partial result would still be great). Additionally, it must have a reasonable chance of giving a good split. (for example, I could use the method above, and every once in a while, a randomly chose edge will split the tree well, but I'm hoping to do better)

I have an additional method for my harder problem, which perhaps could be improved:

Let $m$ be the smallest weight of a vertex in $G$, and $W$ be the sum of all the vertex weights in $G$. Choose two vertices $v_a$ and $v_b$ in $G$. Say we are looking for split in which $v_a$ is in component $A$ and $v_b$ is in $B$. Let $x$ be a random integer in the range of $.45\frac{W}{m} < x < .55\frac{W}{m}$. Then, we look for a split such that the $\left \lfloor \frac{W_a}{m} \right \rfloor = x$, where $W_A$ is the summed weight of the vertices in $A$. In any given tree, there is at most one edge which satisfies these conditions. Proof: consider the path from $v_a$ to $v_b$, we must remove an edge from this path to split these two into different components. As you go down this path, $W_A$ changes by at least $m$. So, the number of possible edges is constant like before, except now it is one rather than $(n-1)$. With $X$ being the number of possible values of $x$ in $A \cup B$, we get:

$$ p(A,B) = t(A)t(B)e(A,B)\frac{1}{t(A \cup B)X}$$

This is assuming that $v_a$ and $v_b$ and chosen deterministically, if you want it to be random, that can be accounted for too if desired. However, the issue is that the probability of a split having $\left \lfloor \frac{W_a}{m} \right \rfloor = x$ is quite low in my graphs, as $W$ is 200 times large than $m$. This restriction makes the chance of a good edge go from 60% to 3.5%. Perhaps there is a way to better way to choose $x$ based on the structure of $G$, or just a better way entirely to do this.

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.