Shortest path in a complement graph algorithm

Question

I had a test today (Data Structures course), and one of the questions was the following: Given an undirected, non-weighted graph G=(V,E), you need to write an algorithm that for a given node s, returns the shortest path from s to all the nodes v' in the complement graph.

A Complement Graph G'=(E',V') contains an edge between any to nodes in G that don't share an edge, and only those.

The algorithm needs to run in O(V+E) (of the original graph).

I asked 50 different students, and not even one of them solved it correctly.

any Ideas? Thanks a lot, Barak.

Answer 1

The course staff have published the official answers to the test.

The answer is:

"The algorithm is based on a BFS with a few adaptations. For each node in the graph we will add 2 fields - next and prev. Using these two fields we can maintain two Doubly-Linked lists of nodes: L1,L2. At the beginning of every iteration of the algorithm, L1 has all the while nodes in the graph, and L2 is empty. The BFS code (without the initialization) is:

At the ending of the loop at lines 3-5, L1 contains all the white nodes that aren't adjacent to u in G, or in other words, all the white nodes that are adjacent to u in the complement graph. Therefore the runtime of the algorithm equals to the runtime of the original BFS on the complement graph. The time is O(V+E) because lines 4-5 are executed at most 2E times, and lines 7-9 are executed at most V times (Every node can get out of L1 only once)."

Note: this is the original solution translated from Hebrew.

I Hope you find it helpful, and thank you all for helping me out,

Barak.