1
$\begingroup$

A problem similar to the MST problem can be constructed as follows: Given a weighted graph $G = (V,E,w)$ such that the weight $w_e$ for each $e \in E$ satisfies $0 < w_e < 1$, find a minimal set of edges $E' \subseteq E$ such that $E'$ spans $G$ and the quantity $$\prod_{e \in E'} (1 - w_e)$$ is maximized.

An easy solution to this problem is to transform $G$ to the graph $\overline{G} = (V, E, \overline{w})$ where $\overline{w}_e = -\log(1 - w_e)$ and find the minimum spanning tree of $\overline{G}$.

However, it also appears that finding the minimum spanning tree of $G$ might also suffice. It is not, however, obvious to me that this works. I have not managed to find any counterexample. I can, however, present a counterexample within a minimum path framework (a completely different problem), so in some sense the structure of the MST must be important.

Is it necessarily true that the MSTs of $\overline{G}$ and the MSTs of $G$ are the same? (Equivalently: Does an MST of $G$ maximize the product I defined?)

Note: I think there is a simpler proof when you only consider the MST returned by a specific algorithm, e.g. Prim's Algorithm. If we consider Prim's Algorithm, it would make the same choices at each iteration because $\overline{w}_e = -\log(1 - w_e)$ gives $\overline{w}_e$ as an increasing function of $w_e$.

There is a unique MST (up to isomorphism) for any graph with unique weights. Hence if the edge weights are unique, any MST is isomorphic to the MST produced by Prim's Algorithm and this is true. If the edge weights are not unique, then the MST is not necessarily unique up to isomorphism and thus it isn't even immediately clear that the two MSTs will give the same product (and thus we can't only consider the MST given by Prim's)

$\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.