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.