Please read the new rule regarding the restriction on the use of AI tools. ×

olivergrant's blog

Minimum cost subtree
By olivergrant, history, 8 months ago, In English

Hi! I have the following problem regarding MSTs.

Given a complete undirected graph $$$G = (V,E)$$$ of edges only costing either 1 or 2, find a subset of the edges $$$|E'|=k$$$ for some $$$k$$$ and vertices $$$V'$$$ such that $$$(V', E')$$$ form a tree and is of minimum cost.

The bounds for this problem is that $$$1 \le n \le 10^3$$$ and $$$1 \le k \le n - 1$$$

To me, this is very similar to an MST problem, but running a classic MST algorithm would be slow and I'm trying to do this in $$$O(|E|)$$$ time by making use of the complete graph property.

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

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by olivergrant (previous revision, new revision, compare).

→ Reply
»
8 months ago, # |
  Vote: I like it +39 Vote: I do not like it

Since all edges either have weight one or two and number of edges in answer is fixed, let us subtract one from weights of all edges (we will add k back to answer in the end). Now we have free edges and edges of uniform cost. Instead of searching for tree let us search for connect subgraph of size at least (k + 1), answer won't change. Firstly, take all free edges. That is, compress connected components. Now from those connected components we need to build subgraph of required size. We can make it greedily: sort components by size and take prefix of some largest components.

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

    Question: What is the purpose of subtracting one from weights of all edges?

    And also could you elaborate on greedily taking components. What if we're using too many edges in the compressed components?

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

      Question: What is the purpose of subtracting one from weights of all edges?

      This is to better understand the solution. If you think about why the greedy algorithm would work in this case, it is very simple: each of the components is free by itself, and only the connection between them has equal cost. However, if the edges have cost 1 and 2, then now each component has a cost that is not equal to the cost of the connection or any other component. In this case, the proof of the solution will not be so obvious.

      What if we're using too many edges in the compressed components?

      Each connected component has a spanning tree that has the minimum number of edges to connect the subgraph. So in this solution you don't use more than you need. You can build this tree using BFS or DFS.

      And I think I should make it clear that you don't need to compress components in the real solution — you just need to extract them, but as I see in your code here you've figured that out for yourself.

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

        Thanks a lot! Are there any similar problems as this? I'm curious because I want to build intuition like this.

        My final code is here for anyone who is curious:

        Spoiler
        → Reply
        • »
          »
          »
          »
          »
          8 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I don't know much about similar problems, but you can have a look at this. It has almost the same graph structure with bigger constraints, so I remembered it when I first saw this thread.

          And I'd like to add one thing to your solution. It's not a big deal, but you don't need to use DSU in this problem — the extraction of the connected components can be done with BFS or DFS, and then you'll have a smaller constant, I suppose.

          → Reply
  • »
    »
    8 months ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Also, sorting the components by size may not make the run time of the solution $$$O(|E|)$$$. Not sure if I'm doing something wrong here.

    Spoiler
    → Reply
    • »
      »
      »
      8 months ago, # ^ |
      ← Rev. 2   Vote: I like it +15 Vote: I do not like it

      Since the graph is complete you have $$$\mathcal{O}(E) = \mathcal{O}(n^2)$$$. The number of components is $$$\leq n$$$ so sorting it takes $$$\mathcal{O}(n\log n) = o(n^2)$$$.

      Sort the sizes in descending order and take them greedily one by one until the sum of the sizes is at least $$$k$$$. You can restore the edges you need by running dfs on the verticies of taken components.

      → Reply