8
$\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?

Improve this question
$\endgroup$
2
  • 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, 2014 at 0:41
  • 1
    $\begingroup$ A closely related question was posted here: math.stackexchange.com/questions/3976677/… $\endgroup$
    – Matthieu Latapy
    Jan 14, 2021 at 9:29

1 Answer 1

Reset to default
-2
$\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.

Improve this answer
$\endgroup$
1
  • 2
    $\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, 2019 at 11:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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