7
$\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$
  • 3
    $\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
-1
$\begingroup$

I personally, do not see why this is left as unanswered.

Finding something in complement graph and finding that same thing in the graph is essentially have the same time complexity (up to constant factor).

Since swapping between edge $(u,v)$ and non-edge $(u,v)$ is just $O(1)$-time operation. We do not have to transform or convert anything just negate every query output.

$\endgroup$
  • 1
    $\begingroup$ It should be run in $O(|V|+|E|)$ time. Note $E$ is the set of edges in the original graph, not in the complement graph. $\endgroup$ – xskxzr Aug 26 at 11:31

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.