Indian Computing Olympiad

Advanced Graph Algorithms→Roads (APIO 2008)

The Kingdom of New Asia contains N villages connected by M roads. Some roads are made of cobblestones, and others are made of concrete. Keeping roads free-of-charge needs a lot of money, and it seems impossible for the Kingdom to maintain every road. A new road maintaining plan is needed.

The King has decided that the Kingdom will keep as few free roads as possible, but every two distinct villages must be connected by one and only one path of free roads. Also, although concrete roads are more suitable for modern traffic, the King thinks walking on cobblestones is interesting. As a result, he decides that exactly K cobblestone roads will be kept free.

For example, suppose the villages and the roads in New Asia are as in Figure 1a. If the King wants to keep two cobblestone roads free, then the Kingdom can keep roads (1,2), (2,3), (3,4), and (3,5) free as in Figure 1b. This plan satisfies the King's criteria because (1) every two villages are connected via one and only one path of free roads, (2) there are as few free roads as possible, and (3) there are exactly two cobblestone roads: (2,3) and (3,4).

       1-------- 2                    1-------- 2
        .       . \                            .
         .     .   \                          .
          .   .     \                        .
            3 . . . . 4                    3 . . . . 4
              \     /                        \
                \ /                            \
                 5                              5

      

We have a graph with edges of two types, say coloured black (concrete) and blue (cobblestones). We want a spanning tree with exactly K blue edges.

We first delete the blue edges and compute the connected components. In any spanning tree, these components have to be connected by blue edges. If there are more than K+1 components, there can be no spanning tree using exactly K blue edges.

What if we have ≤ K components?

Recall Kruskal's algorithm for a minimum cost spanning tree. We set all weights to 1 and run Kruskal's algorithm as follows:

1. First add only blue edges that connect disjoint components (those that are joined by only black edges).
2. Once we have connected all components, we continue to add blue edges, till we have added K edges.
3. Once we have put in exactly K blue edges, we stop using blue edges and start adding only black edges.

This is correct because Kruskal's algorithm will find the spanning tree for any permutation of edges that are in sorted order. In particular, if all edges have equal weight, you can provide the edges to in any order. If at any stage we find that we cannot continue, this means that there is no possible spanning tree with exactly K blue edges and we stop and report failure.

---