Three algorithmic problems

[BiK]

Hi guys,

I have recently wondered about efficient algorithms concerning three algorithmic problems:

1. Given a directed graph G = (V, E) find the symmetric complement G = (V, E') such that if (u,v) is in E then (u,v) and (v,u) are in E'. For any two vertices u, v in V there can be at most one edge in E' from u to v.

Two variants are:

a./ For two vertices u and v there can be more than one edge in E from u to v.
a./ For two vertices u and v there can not be more than one edge in E from u to v.

There should be an O(V+E) algorithm for this problem.

2. Given a directed graph G = (V, E), build the component graph of G in which the strongly connected components of G are replaced by a single vertex and in which there is at most one edge between strongly connected components u and v.

O(V+E) algorithm?

3. Given a directed graph G = (V, E), build a graph G' = (V, E') such that:
a./ G' has the same strongly connected components as G.
b./ G' has the same component graph (see 2) as G.
c./ E' is as small as possible.