COS 341, December 3, 1997

Handout Number 22

Diameters, Guess and Verify

Diameters

Let G be a graph on n vertices . Let d(i,j) denote the distance between vertices i,j in G (ie, the length of the shortest path from i to j in G). By convention, d(i,i)=0 for all i. It is easy to see that the triangle inequalities are satisfied, ie, for all i,j,k. The diameter is defined as . Clearly, .

Given an input G, we will give an algorithm that determines in time where s(n) is the time needed to compute the boolean matrix product of two boolean matrices.

Let denote the boolean matrix such that iff either i=j or is an edge in G; all other entries are 0. Thus, iff . The following generalization of the above statement is the key observation needed to develop our algorithm.

Lemma For all integers , iff .

Proof We prove by induction on t. The base case t=1 is true by an observation made in the paragraph before the Lemmma. For the inductive step, let t>1, and assume that the Lemma is true for all lesser values.

Observe that

We now establish the case for t. First one direction. Assume . By (1) there exists a vertex k such that . By the induction hypothesis applied to t-1 and 1, this vertex k satisfies and . This implies then .

Second, in the opposite direction, assume that . Let k be a vertex such that and ; we can take k to be j if i=j, and otherwise the last vertex before reaching j on the shortest path from i to j. By the induction hypothesis, and . It follows then from (1) that . This completes the inductive step in the proof of the Lemma.

Let D denote the boolean matrix with all its entries equal to 1. The Lemma implies that for all . It also implies that (entrywise) for all m. Thus, to determine , it suffices to find the smallest t such that . Recall that and thus the range of this t is between 1 and n-1.

To do this, first compute all the powers , where is the first time the matrix power becomes D. The running time spent in this round is . We have now determined that is in the range . The range is thus halved in this round.

In the second round, we compute all the powers , where is the first time the matrix power becomes D. The running time spent in this round is . We have now determined that is in the range . The search range is thus halved in this round.

We can similarly carry out the 3rd round, 4th round, until the range is reduced to zero. The total running time is which is , since and each .

We remark that in fact is the binary representation of the integer .

In Homework Set 8, you will be asked to modify the above search process and improve the running time to .

Guess and Verify

In this approach, when confronted with a recurrence relation, we guess an upper bound (or lower bound) expression for the function. Then verify by induction. The following example comes from the analysis of the running time T(n) of a backtracking algorithm for listing all the maximal independent sets of n-vertex input graphs:

We prove by induction that, for all ,

where are the Fibonacci numbers.

Before proceeding with the proof, we compute the values of T(n) and for . It turns out that the T(n)'s are 1,1,4,8,16,29, 51; the are 1,1,2,3,5,8,13.

For the base n=0, 1, (3) is clearly true since T(0)=T(1)=1 by definition. For the inductive step, let n>1 and assume that (3) is valid for all lesser values. We establish (3) for n.

If , then (3) is true by using the values we have computed for . We can thus assume that n > 6. Using the recurrence (2) and the induction hypothesis (3) for n-1 and n-2, we have

This completes the inductive proof of (3).

How did we come to the lucky guess (3)? Here is the rationale. First observe that, if the +n term is missing in the recurrence (2), then would be the solution. Since +n is such a small additional term compared with the terms, a reasonable guess is

for some constant, say, c=10. However, if you try to verify (4) by induction using the recurrence (2), you cannot carry out the inductive step, ie, you get

which does not complete the inductive step.

What we lacked is an additional term in T(n) such that they can absorb the +n term. A natural choice is to guess

However, the inductive step still falls a little short, since we get only

Thus, we want to make the additional term a little more negative. Also, we need to choose c carefully so that the negative new term does not kill the validity of the base case.

Let us make the guess in the general form

for some c,d >1, and see what parameters can make the inductive proof work.

Take the inductive step first. We have

To make the inductive step work, we need the condition , ie,

This means that, if d>1 is chosen, then the inductive step can be carried out if .

But the inductive step (and the base case n=0,1) needs to be done when n < 3d/(d-1). This can be accomplished by brute force, that is, by choosing the parameter c to be large enough. In fact, all we need is that equation (5) be satisfied for all n < 3d/(d-1). Equivalently, we need

If d=2 (hence 3d/(d-1)=6), it is sufficient to choose c to be at least as big as

which is less than 5.

• About this document ...