Algorithms: Design and Analysis, Part 1 - Problem Set 4 - Question 2

Problem:

Consider the following problem: given an undirected graph $ G $ with $ n $ vertices and $ m $ edges, and two vertices $ s $ and $ t $, does there exist at least one $ s-t $ path?

Suppose instead that $ G $ is given in its adjacency *matrix* representation. What running time is required, in the worst case, to solve the computational problem stated above? (Assume that $ G $ has no parallel edges.)

Solution:

With $ O(n^2) $ time, we can build the adjacency list and then use DFS to figure out the solution.

The lower bound is much harder to claim. Imagine the algorithm is running against an adversary who is responsible for providing adjacency matrix values, and it follows the following algorithm in returning values.

Function answer(from, to)
{
  if (from == to)
    return 1
  if (from > to)
    return answer(to, from)
  if from == s or from == t
    if there exist more than one entry not read yet with the same from
      return 0
    else
      return 1
  else if to == s or to == t
    if there exist more than one entry not read yet with the same to
      return 0
    else
      return 1  
  else if to == s or to == t
    if there exist more than two entries not read yet with the same from
      return 0
    else
      return 1    
}

The essence of the algorithm above is simply return 0 as much as possible, maintaining s-t is a chain, s and t has degree 1, and every other node has degree exactly 2.

The algorithm who can win the adversary must read all entries, that proves the lower bound of $ O(n^2) $.

Therefore the running time $ \theta(n^2) $.