Find if an edge doesn't belong to any $MST$ with some edges of unknown weights

Question

I've faced this problem with my homework.

We're given a weighted, undirected graph $G=(V,\ E,\ w)$ with weight function $w:E\rightarrow \mathbb{R_{\ge0}}$, someone deleted the weights of some edges $T\subseteq E$ so their weights are unknown. Describe an efficient algorithm that finds the following:

1. For every $e\in T$ if it belongs to every MST (no matter what the weights of $T$ are).
2. For every $e\in T$ if it doesn't belong to any MST (no matter what the weights of $T$ are).

More explanation: all the edges in $T$ don't have their weight now so we can't know what their weights were, therefore we can't use Kruskal or Prim algorithm unless we give them weights that will give us the results we want.

So I was thinking of a solution for the first part which is finding all bridge edges and of them to check the edges that are in $T$, these edges are for sure belongs to every $MST$ and that because they are the lightest edges in some $cut$ of the graph.

As for the second part, I know that we must find edges that are for sure the heaviest edges in any cycle but the problem is that we don't have the weights of these edges and we can't give them maximum weight in any cycle too because this would lead to wrong results.

If anyone could help I'll be thankful.

Answer 1

So, we are asked to find the answer to the following two question, regardless of whatever values we will reassign to $w(u)$ for all $u\in T$.

Does $e\in T$ belong to every MST?

Your approach is correct.

• If $e$ is a bridge, every MST must contain $e$ since an MST must be connected.
• Otherwise, $e$ is not a bridge. We can let the weight of $e$ be bigger than the weight of every other edge. Then no MST can contain $e$ since $e$ is the unique heaviest edge of any cycle that contains $e$.

Does $e\in T$ not belong to any MST?

If $G$ is a graph without loops, there is no such edge since we can assign weight $0$ to $e$. We can then run Kruskal's algorithm to select $e$ as the first edge to include, obtaining an MST that contains $e$ in the end.

Otherwise, every loop of $G$ that is in $T$ does not belong to any MST. In fact, any MST of any graph does not contain any loop since an MST is a tree.