Computer Engineering(CE)
Question 1: Algorithms
August 2015
Solution 1
Solution of this problem can be accomplished with a modified version Prim's algorithm. The necessary modification of the algorithm is two-fold. The first modification is that before we run Prim, we must remove (and store) all edges in the graph that cross environmentally sensitive areas. Then we run Prim's algorithm on this modified graph, finding the minimum spanning tree of our subset of edges (or trees, since it is possible that we have partitioned the graph into disjoint parts when we removed edges; suppose Prim's algorithm stops before we have reached all vertices, then pick an un-visited vertex and run Prim from this vertex; repeat until all vertices have been visited). If we are able to find a spanning set of the graph without using one environmentally impactful edge, we are done.
Clearly, at this point in the algorithm it is possible that we have not found a spanning tree for the entire graph. Here is where the second part of the algorithm is implemented. Recall the set of edges that were removed from the graph earlier. First, we remove any edges that have vertices that are both in the MST(s) of the modified graph. We then take the low-cost edge from the remainder of the environmentally impactful list such that one of its vertices is in the current tree and add it back into the modified set; if the graph is now spanned, we are done. If the graph is still not spanned, then repeat the procedure allowing one more impactful edge. We repeat this until we span the graph.
The operations necessary for this algorithm that go above and beyond Prim's algorithm are as follows:
$ \bullet $ Find all environmentally impactful edges, remove them, and store them
$ \bullet $ Permanently remove all edges that connect two vertices currently in the modified tree
$ \bullet $ Add an edge to the modified tree
$ \bullet $ Check to see if the modified spanning tree spans the full tree
Finding the bad edges requires a sweep through all edges, and thus takes $ O(E) $ time. Removing and adding edges both take constant time, while checking that the tree is spanned (not necessarily minimally) takes $ O(E) $ time (check every edge for its vertices, if vertices not already represented then add them to list of vertices; check this list against list of all vertices in the full tree). One may need to perform these modified steps a total of $ E $ times in the case that every road is environmentally impactful and there are no pairs of edges that connect the same two houses. In such a case, we have that the algorithm takes $ O(E^2 + E + V\log V) = O(E^2+V\log V) $ time.
In terms of correctness, we can be sure that Prim's algorithm is correct when it initially operates on the modified graph, so it must have a minimal cost and contain (trivially) the minimal number of bad edges. If we cannot span the graph, we permanently remove all bad edges that have both vertices in the same partition of the current tree and relax our bad edge constraint to admit the low-cost bad edge that has one vertex in the current tree. We can eliminate the bad edges with two same-partition vertices since we cannot use them to access any new vertices or join partitions. Suppose we were to add one of these bad edges to the current tree at some iteration. Then, even if we were able to decrease cost by addition of this edge, we would be using a sub-optimal number of bad edges to span our tree, which violates our constraint on bad edges.
It is also easy to see that addition of the low-cost one-vertex or partition-joining vertex is the optimal choice for our MST. We have already ensured that all non-harmful edges are in some partition of the graph, so it is impossible for us to "uncover" cheap roads by taking a less-than-greedy path at this stage of the algorithm. Also note that, as discussed in the previous paragraph, the uncovering of cheap bad edges cannot serve us either (unless such a bad edge leads us to an as-yet undiscovered vertex, which we are compelled to visit eventually in any case).
At the end of the algorithm, it is clear that we have spanned the tree with the minimal number of bad edges since we do not admit a bad edge unless we are unable to span the tree without one. In addition, it is clear that we have spanned the tree with minimum cost subject to the bad edge constraint. Suppose that the following claim is not true; then since we know that we have used the minimum number of bad edges in our spanning tree, there must be an edge remaining in the list of bad edges that has lower cost than one of the bad edges in the span (there cannot be a good edge in the list since we never placed good edges in this list). Then if we make the required replacement, we will have replaced a bad edge with the low edge from the list of bad edges. However, we have already stated that we add the low bad edge that meets our constraints at every iteration, so this new low edge cannot be any lower than any of the edges that we have added before. Thus our algorithm must be correct.
