CODEWITHSUNDEEP
algorithm
aqjune
aqjune

Reputation: 552

Making a bipartite graph SCC by adding minimum edges

There's a bipartite graph B(E, V1, V2) such that e = (v1, v2) for e ∈ E, v1 ∈ V1, v2 ∈ V2. Edges in B are directional.

I'd like to make a graph G(E ∪ E', V2 ∪ V2) such that the graph G is strongly-connected component, with minimum sizeof(E'). (sizeof(A) is the number of elements in the set A) E' doesn't have to be V1 -> V2.

For an example, with V1 = {1, 2, 3} and V2 = {a, b}, there's a bipartite graph B(E, V1, V2) with E = {(1, a), (2, a), (2, b), (3, b)}. Then E' = {(a, 3), (a, 1), (b, 2)} makes all vertices in G(E ∪ E', V2 ∪ V2) strongly-connected.(whenever I choose vertex pair v1 and v2, there exists a path from v1 to v2)

Can someone give me some idea? Or is there a well-known algorithm about this?

Upvotes: 0

Views: 562

Answers (1)

Falk Hüffner
Falk Hüffner

Reputation: 5040

A theorem by Eswaran and Tarjan says that an acyclic digraph with r sources (i.e., vertices without incoming edges) and s sinks (i.e., vertices without outgoing edges) can be made strongly connected by adding max(r, s) edges (see e.g. here). Thus, you need to add max(sizeof(A), sizeof(B)) edges. The book also explains how to find a solution (a simple system of matching up vertices).

Upvotes: 1

Related Questions