Shortest path and series-parallel graph

A regional government wants to improve their existing infrastructure between a collection of towns $T$. In specific, the government want to build a minimum number of roads such that there is a route from each town to each other town. The government has been advised by a dubious consultant that in the resulting road network, the number of users of a given road is independent of the presence of alternative routes. The regional government wants to minimise the number of roads it has to built to ensure that one can travel from one town to the other. Furthermore, the government wants to maximize the benefits of the road network by maximizing the number of users of the roads built. Hence, the government wants to only build roads that are expected to be used often. To help the construction plans, the government has asked the dubious consultant to estimate, for each pair of cities, the number of road users that would use the road between these two cities (if that road was built). Now the regional government is looking for a construction plan for a minimum number of roads connecting all towns that see the highest total usage among them.

P1.1

Model the above problem as a graph problem: What are the nodes and edges in your graph, do the edges have weights, and what problems are you trying got answer on your graph?

• Nodes: Each town in the set of town $T$ is represented as a node in the graph. Denote the set of nodes as $V$
• Edges: Each potential road can be built between two pair of town. Denote it as $E$. Each edge weights represents the estimated number of users who would use the road should it is constructed. Denote the weight of an edge between nodes $i$ and $j$ as $w(i, j)$.

The problem can then be modelled as given a weighted undirected graph $\mathcal{G} = (V, E)$ representing towns and potential roads, find a maximum weight minimum spanning tree of $G$.

Explanation:

• We need to ensure there is a route from each town to every other town while minimising the number of roads being built, thus the minimum spanning tree of the graph.
• Among all possible MSTs, we want to find the one with the maximum total edge weight, thus maximum weight MSTs.

P1.2

Provide an algorithm $\text{ConstructionPlan}$ to find the minimum number of roads to build. Explain why your algorithm is correct.

Let $w(x, y)$ be the weight of the edge between nodes $x$ and $y$.

This is the Prim’s algorithm for finding MSTs. We instead replace the minimum weight with maximum weights to fit with problem description in P1.1

Correctness:

Invariant: $V \text{ contains all visited nodes}, E' \text{ contains edges of a maximum weight spanning tree over nodes in } V$

• At L4, invariant holds since $V = \{s\}$ and $E' = \emptyset$
• per iteration, we add $E'$ with the maximum weight edge $(u, v)$ from any visited nodes $u \in V$ to any unvisited node $v \in T \setminus V$ (L6-14). Then add $v$ to $V$ (L15), maintaining the invariant because:
  • $V_{\text{new}} = V \cup \{v\}$
  • $E'_{\text{new}} = E' \cup \{(u, v)\}$ is a maximum weight spanning tree over $V_{\text{new}}$ due to $(u, v)$ is the maximum weight edge connecting $V$ to $T \setminus V$.

The algorithm never create cycle in $E'$ since we only add edge from visited nodes to unvisited nodes, which cannot create a cycle.

Bound function:

Let $w(E')$ be the total weight of edges in $E'$. Per iteration, $w(E')$ is the maximum possible weight of any spanning tree over the nodes in $V$.

This holds initially when $V=\{s\}$ and $w(E') = 0$. Per iteration, we add the maximum weight edge $(u, v)$ to $E'$ from $V$ to $T \setminus V$. Bound function is maintained because:

• $w(E'_{\text{new}}) = w(E') + w(u, v) \geq w(E')$
• Any other spanning tree $T'$ over $V \cup \{v\}$ must contain an edge $(x,y)$ from $V$ to $\{v\}$, and $w(x,y) \leq w(u,v)$. Therefore, $w(T') \leq w(E' \cup \{(u,v)\} )$

The loop terminates when $|V| = |T|$, i.e all nodes are visited.

Thus the algorithm is correct. $\square$

P1.3

Explain which graph representation you used for your algorithm and what the complexity of your algorithm is using this graph representation.

Uses adjacency list representation of the graph $G=(T,E)$. Since we store a list of edges for each nodes, or for each node $u \in T$, we maintain a list $\text{Adj}[u]$ containing the node $v$ and weight $w(u,v)$ for every edge $(u,v) \in E$.

The time complexity of the algorithm is $\mathcal{O}(|T|^2\log|T| + |E|)$:

1. Initialising adjacency list: $\mathcal{O}(|E|)$, where the adjacency list takes $O(|E|)$ to populate
2. L4: Run for $|T|$ iterations
3. Inside the loop, find maximum weight edge takes from $Q$ takes $O(\log|T|)$. Therefore each iteration the while loop takes $O(|T|\log|T|)$
4. Adding extracted edge to $E'$ takes $O(1)$

Thus, the overall time complexity is $\mathcal{O}(|T|^2\log|T| + |E|)$. If the graph is complete, then $|E| = \frac{|T|(|T|-1)}{2} = O(|T|^2)$, and the time complexity is $\mathcal{O}(|T|^2\log|T|)$

The space complexity is $O(|T| + |E|)$

P1.4

What is the worst-case complexity of your solution if you use the other graph representation? Explain your answer

Worst case complexity of the algorithm using adjacency matrix representation is $\mathcal{O}(|T|^2\log|T|)$.

If adjacency matrix representation is used, or we use a $|T| \times |T|$ matrix $\text{Adj}$ to represent the graph, where $\text{Adj}[u][v]=w$ for an edge $(u,v)$ with weight $w$.

Initialising the matrix will take $O(|T|^2)$ time.

Adding edges from starting node $s$ to priority queue $Q$ will take $O(|T|\log|T|)$ time, as we need to scan row $\text{Adj}[s]$ which has $|T|$ elements.

Inside the while loop, for loop (L18-23) that iterates over the edges of the newly visited node $v$ now takes $O(|T|\log|T|)$ time, as we need to scane the row that has $|T|$ entries, and for each unvisited node, we insert the edge into $Q$ which takes $O(\log|T|)$ time. Therefore, the while loop will take $O(|T| \cdot (|T|\log |T|)) = O(|T|^2\log|T|)$

Thus, the total time complexity would be $O(|T|^2 + |T|^2\log|T|) = O(|T|^2\log|T|)$

Whereas the space complexity is $O(|T|^2)$. Could be more efficient for sparse graph where $|E| \ll |T|^2$.