###
Problem

Given an undirected graph, design a O(V*E) algorithm to detect whether there is a triangle in the graph or not.

###
Algorithm

The idea of the algorithm comes from Manber's book. The central observation is that in order to form a triangle, say (i, j, k), then the corresponding rows of the first two vertices i and j should have both 1 on the k-th column. We can simply do a linear intersection to check this. However, in addition, we have to check that vertex i appears in the j-th row and vice versa. Using adjacency matrix, the complexity is then O(V^3), with V being the number of vertices.
For sparse matrix, a O(V*E) algorithm is more efficient. Instead of using adjacency matrix, we now use adjacency lists. We can do the intersection using a procedure similar to merge-sort. More specifically, we perform the following:

- sort all the adjacency lists
- for each two pair of vertices
- intersects the edges to find common end points
- meanwhile check whether the pair is an edge

To see such an algorithm is O(V*E), we have to notice that each adjacency list has been intersected with all other V-1 adjacency lists. If we denote by \(L_i\) the length of the adjacency list incident on node i, then the total intersection time is: $$\Sigma_i (V-1)L_i = (V-1)\Sigma_i L_i = (V-1)E$$
We also notice that the cost of sorting the adjacency lists are:
$$\Sigma_i L_ilog(L_i) \leq \Sigma_i L_ilog(E) = ElogE$$
To sum up the complexity is O(ElogE+V*E) = O(V*E).

###
Code

class Graph{
List<Integer > [] adjLists; // adjacency lists
int n; // size of graph
}
boolean containsTriangle(Graph g) {
// sort all adjacency lists in arrays
Integer[][] arrays = new Integer[g.n][];
for (int i = 0; i < g.n, i++) {
arrays[i] = g.adjLists[i].toArray(new Integer[0]);
Arrays.sort(arrays[i]);
}
// iterate all pairs
for (int i = 0; i < g.n; i++) {
for (int j = i + 1; j < g.n; j++) {
// test intersection and connectivity
int pi = 0;
int pj = 0;
boolean intersected = false;
while (pi < arrays[i].length && pj < arrays[j].length) {
if (arrays[i][pi] == arrays[j][pj]) {
intersected = true;
break;
}
else if (arrays[i][pi] < arrays[j][pj]) {
pi++;
}
else {
pj++;
}
}
// check connectivity by checking whether i is in list of j
boolean connected = false;
for (Integer k : arrays[j]) {
if (k == i) {
connected = true;
break;
}
else if (k > i) {
break;
}
}
if (intersected && connected) return true; // early return
}
}
return false;
}

## No comments:

Post a Comment