5
$\begingroup$

I'm looking for an algorithm that receives as input a vertex $s$, and finds the shortest paths from $s$ to all vertices in the complement graph (undirected). The algorithm should run in $O(V+E)$ time, where $E$ is the number of edges in the original graph (not the complement graph).

If $G$ is a graph, the complement graph is defined to be the following graph: $e$ is an edge in the complement graph, if and only if it isn't an edge in the original graph. In other words we delete all existing edges, and add all the edges that were missing from the original graph.

So first I of course thought of "building" the complement graph (replacing the vertices in the adjacency list with those that don't appear there), then running BFS on the new list, but of course that would mean that the run-time would be based on the edges in the complement graph, not the original one.

I also noticed of course that after running BFS on the original graph, any vertex that has a distance from $s$ that is greater than 1 (in the original graph) should become 1 in the complement graph (because if they weren't neighbors in the original graph, they are neighbors in the complement graph). But I couldn't get the algorithm to continue according to some specific rules as to when should the distance be updated and to what. Any suggestions?

$\endgroup$
  • 2
    $\begingroup$ A possible direction is to consider two cases: $|E| < c|V|^2$ and $|E| \geq c|V|^2$, for some constant $c < 1/2$. In the second case, the complement graph has $O(|E|)$ edges, so we are done. In the first case, the complement graph is very dense, which could help make the algorithm run faster. $\endgroup$ – Yuval Filmus Jun 30 '14 at 0:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.