mtkaya's blog

Check if an edge is contained in at least one MST
By mtkaya, history, 7 years ago, In English

Hi, I have a question related to MST.

Suppose that we are given a graph where we have limited knowledge of the edge weights: Example

Is it possible to find all edges that are contained in at least one MST?

Thank you...

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The problem statement is unclear. Are we to decide if an edge exists in a MST for all possible configurations of the question marks? Or if that edge exists in a MST for at least one possible configuration?

In either case it is possible to modify Kruskal's algorithm.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Question mark means there is an edge but length of the edge is unknown!

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Well yeah, but in that case there are edges which might be in at least one MST if the unknowns have favorable valuables, but which might also not be in a MST. Should we include those edges?

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I guess we should not

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          We will first find out whether each edge with a known weight definitely exists in some MST, then whether each edge with an unknown weight definitely exists in some MST. Both cases can be handled with a modified variant of Kruskal's algorithm.

          The worst case is when as many as possible edges with unknown values are in a MST. Let's make a DSU and add all the unknown edges to it. Now let's sort the edges with known weights by their weights and start processing the edges in blocks of equal weight. For each edge in a block, check if its endpoints are in different connectivity components (with the DSU), but don't merge them yet. If an edge's endpoints are in different connectivity components, the edge definitely exists in a MST. Once you've processed all the edges in a block, merge their endpoints in the DSU.

          Now for the edges with unknown weights. Make a new DSU and merge the endpoints of all edges with known weights. An edge with an unknown weight definitely exists in at least one MST if its endpoints are in different connectivity components in the DSU.

          The complexity of the first part is ; the complexity of the second part is , so the total complexity comes down to .

          → Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I believe what it means is that for each edge we need to determine if it's included in some MST, for any possible weights of the edges of the question marks.

    For that we could just immediately give all these edges a weight 0.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Your comment is as ambiguous as the statement, but I see what you mean because of the weight 0 thing. Anyway we still need to consider when the edges with unknown weights are in any MST.

      → Reply