Longest Path: Method of Random Orientations

In this post, we shall consider an NP-complete problem, namely that of determining whether a simple path of length k exists in a given graph, G = (V,E).

Formally,

LONGEST PATH PROBLEM

Input: undirected graph, G = (V,E), integer k \geq 0 .

Parameter: k

To find: Does G contain a simple path of length, k?

(Note: length refers to edge length here. In particular, a simple path of length k has k edges.)

The problem has a natural extension:-

EXTENDED LONGEST PATH PROBLEM

Input: undirected graph, G = (V,E), integer k \geq 0 .

Parameter: k

To find: All pairs of vertices (i,j) \in V \times V , such that there exists a simple path of length k between i and j in G.

=======

This article is based on the seminal paper on Color-Coding by Noga Alon, Raphael Yuster, Uri Zwick [1995]. The method of random orientations is mentioned in the paper prior to a description of the color-coding approach.

=======

We concern ourselves with the Extended Longest Path problem.

Consider the adjacency matrix, A of input graph, G. (A is an |V| \times |V| matrix, with 0 / 1 entries, which we interpret as integers.)

We have, A[i][j] \neq 0 iff there exists an edge {i,j} \in E .

(Note: A[i][j] represents the entry at the i^{th} row and j^th column of matrix A.)

Consider the matrix, A^2 = A \times A .

A^2[i][j] \neq 0 iff there exists a path of length two between i and j in G. (Why? Verify for yourself.)

Generalizing, we can make the following statement for the matrix A^k = A^{k-1} \times A .

A^k[i][j] \neq 0 iff there exists a path of length k between i and j in G. (Why? use induction to prove this.)

Question: Do all paths represented in the matrix entries correspond to simple paths of G?

In other words, is the following statement true:

A^k[i][j] \neq 0 iff there exists a simple path of length k between i and j in G.

By a little observation, it can be seen that for the matrix entry A^k[i][j] to be non-zero, the path between vertices i and j need not necessarily be simple. In other words, the path may contain cycles.

Hence, we can not infer from the fact of having A^k[i][j] \neq 0 , the conclusion that there exists a simple path of length k between i and j in G.

How do we fix this problem?

Consider a graph, H that does not have any cycles (i.e. acyclic graph). Clearly, all paths in H are necessarily simple. (For a path to not be simple, the path needs to contain a cycle, which is precluded by the fact of H being acyclic.)

Let B denote the adjacency matrix of acyclic graph, H.

We can make the following statements:-

B^k[i][j] \neq 0 iff there exists a path of length k between i and j in H.

And since all paths of H are necessarily simple, the above statement is equivalent to:-

B^k[i][j] \neq 0 iff there exists a simple path of length k between i and j in H.

Therefore, if the input graph is acyclic, raising the adjacency matrix to the power k solves the Extended Longest Path Problem.

—-

Question: How do we obtain an acyclic graph, H from the given input graph, G?

Prior to answering this question, we shall digress briefly to the look at the notion of a Directed Acyclic Graph (abbreviated as DAG).

Consider an undirected graph, G = (V,E) on n vertices. We shall construct a directed acyclic version of G.

Let \pi be a permutation of the vertices i.e. \pi : V -> \{1,...,|V|\} , (\pi is one-one and onto, i.e. bijective.)

Call the directed version of G as G_{dir} . The vertex set of G_{dir} is V (same as G). For every edge of G, we have a corresponding directed edge in G_{dir} .

For each edge \{i,j\} \in E of G, add edge (i,j) to G_{dir} iff \pi (i) < \pi (j) .

(i.e. Orient every edge of G from the vertex having lower \pi value to the vertex having greater \pi value. )

Claim 1. G_{dir} is acyclic.

Proof. Assume to the contrary that G_{dir} has a cycle, C = (v_1, v_2, ..., v_i, v_1) .

Hence, we have the following i inequalities:-

\pi (v_1) < \pi (v_2)

\pi (v_2) < \pi (v_3)

\pi (v_{i-1}) < \pi (v_i)

\pi (v_i) < \pi (v_1) .

From the first {i - 1} inequalities, we obtain:-

\pi (v_1) < \pi (v_i) , which is contrary to the i^{th} inequality.

Hence, G_{dir} is acyclic. QED.

==

Claim 2 (Converse of Claim 1.). Given a Directed Acyclic Graph, G = (V,E), we can obtain a bijection \pi : V {->} \{1,..., |V|\} , such that for every edge (i,j) \in E , the following condition holds:\pi (i) < \pi (j) .

Proof-sketch.

Given any directed acyclic graph, G = (V,E), we have:-

\exists v \in V such that \forall i \in V, (i,v) \notin E .

(In other words, we can find a vertex in V, which has no incoming edges.)

Assign \pi (v) = 1 for one such vertex, v.

Remove v from G to get a new directed acyclic graph. Find a vertex, u that satisfies the above condition in this new graph, assign \pi (u) = 2 .

Proceed in this manner until all vertices are assigned a value under the function, \pi .

End of proof-sketch.

===

We can now return to the question raised prior to the discussion on directed acyclic graphs.

To restate:

Question: How do we obtain an acyclic graph, H from the given input graph, G?

Solution: Take a random (What does “random” mean?) permutation \pi : V {->} \{1, ..., |V| \} . Create an directed acyclic version of G as outlined in the preceding discussion. Call this graph, G_{dir} .

(By “random”, we mean a permutation selected uniformly at random from the set of n! possible permutations of the vertex set, V.)

Denote the adjacency matrix of G_{dir} by B.

As seen earlier, we have:-

B^k [i][j] \neq 0 iff there exists a simple path in between i and j in $latex  G_{dir} $ of length k.

Since every simple path in G_{dir} is also a simple path in G (Why is this true?), we have:-

If B^k [i][j] \neq 0 , then \exists a simple path between i and j in G of length k.

Question: Is the converse of this above statement true?

In other words, is the following statement true:-

If there exists a simple path between i and j in G of length k, then B^k[i][j] \neq 0 .

Answer: No.

The above question can also be rephrased as:

Are all simple paths in G carried over into G_{dir} ?

(Take a simple path, p in G, and figure out for yourself how the edges of p need to be oriented for path, p to exist in G_{dir} . In particular, what does this imply about the \pi values of the vertices along the path?)

==

Now, we can ask the question:

Question: What is the probability that a particular simple path, p = (v_1, v_2, ..., v_k) of length k in G gets preserved in G_{dir} given that we take a random permutation, \pi : V {->} \{1, ..., |V| \} to obtain G_{dir} from G ?

Solution: There are only two ways in which path p can get preserved in G_{dir}

either as the directed path, p1 = (v_1, v_2, ..., v_k) ,

or as the directed path, p2 = (v_1, v_2, ..., v_k) .

Path p1 exists only if \pi (v_1) < \pi (v_2) <... < \pi (v_k) .

Path p2 exists only if \pi (v_1) > \pi (v_2) > ... > \pi (v_k) .

Note that we are not concerned with the \pi values of any of the other n-k vertices of G.

Hence, we obtain the following:

Probability that a particular path, p in G, of length k, is preserved in G_{dir} = 2 / (k+1)!.

(How do we get that?)

===

The above probability implies that to preserve any particular simple path of G (having length k), we need to take an expected number of (k+1)! / 2 random permutations.

===

Running time of the algorithm:

We can state the expected running time of the algorithm. We need to perform the following steps.

1. Given a particular random permutation, \pi : V {->} \{1, ..., |V| \}.

Raise the adjacency matrix, B  of G_{dir} to the power k.

This can be done via O(log k) matrix multiplications, each of which takes O(V^\omega) time. (Here \omega is the exponent for matrix multiplication (\omega < 2.376) . )

2. Repeating the same for an expected number of O( (k+1)! ) random permutations.

3. Keep track of of the n \times (n-1) / 2 pairs of vertices, for each of which we need to output a boolean Yes or No value (corresponding to whether or not a simple path of length k exists in G between that pair of vertices.) (Note: n = |V|).

Initialize all n \times (n-1) / 2 values of this global list to No at the beginning of the algorithm. For each permutation, if the matrix entry, B^k [i][j] \neq 0 and if the value corresponding to pair (i,j) is listed as No in the global list, change it to Yes.

Hence, the expected running time of the algorithm is O( (k+1)! .log k. V^\omega) .

(We have ignored certain polynomial (in the size of the graph) factors in the running time. That is justified owing to the “supremacy” of the (k+1)! term over other factors.)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: