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:
- For every $e\in T$ if it belongs to every MST (no matter what the weights of $T$ are).
- 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.