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$.

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.)