The Semi-Connectivity Problem: Given a digraph G = (V,E), determine whether or n

Question

The Semi-Connectivity Problem: Given a digraph G = (V,E), determine whether or not G is semi-connected. G is semi-connected if and only if for every pair of its vertices u and v there is either a directed path from u to v or a directed path from v to u (or both). Below we investigate an efficient solution to this problem by using the Strongly Connected Components (SCC) algorithm.

a} Highlight the strongly connected components of digraph G below, and draw its SCC Component DAG on the right hand side. Is G semi-connected? Why?

b) State and prove a necessary and sufficient condition for the semi-connectivity of any digraph G expressed as a structural property of its SCC Component DAG.

c) Describe and analyze an efficient algorithm to solve the Semi-Connectivity Problem.

Explanation / Answer

O(V^3) solution could be to use floyd warshal all-to-all shortest path, but that's an overkill (in terms of time complexity).

It can be done in the following way
O(V+E).

A DAG is semi connected in a topological sort, for each i, there is an edge (vi,vi+1)

Proof:
---------------------

Given a DAG with topological sort v1,v2,v3,...,vn:

If there is no edge (vi,vi+1) for some i, then there is also no path (vi+1,vi) (because it's a topological sort of a DAG), and the graph is not semi connected.

If for every i there is an edge (vi,vi+1), then for each i,j (ivi->vi+1->...->vj-1->vj, and the graph is semi connected.

From this we can get the algorithm:

Find Maximal SCCs in the graph
Build the SCC graph G'=(U,E') such that U is a set of SCCs. E'= {(V1,V2) | there is v1 in V1 and v2 in V2 such that (v1,v2) is in E)
Do topological sort on G'
Check if for every i, there is edge Vi,Vi+1.
Correctness proof:

If the graph is semi connected, for a pair (v1,v2), such that there is a path v1->...->v2 - Let V1, V2 be their SCCs. There is a path from V1 to V2, and thus also from v1 to v2, since all nodes in V1 and V2 are strongly connected.

If the algorithm yielded true, than for any two given nodes v1, v2 - are in SCC V1 and V2. There is a path from V1 to V2 (without loss of generality), and thus also from v1 to v2.

As a side note, also every semi-connected graph has a root (vertex r that leads to all vertices):

Proof:
Assume there is no root. Define #(v) = |{u | there is a path from v to u}| (number of nodes that has a path from v to them).
Choose a such that #(a) = max{#(v) | for all v}.
a is not a root, so there is some node u that has no path from a to it. Since graph is semi connected, it means there is a path u->...->a. But that means #(u) >= #(a) + 1 (all nodes reachable from a and also u).
Contradiction to maximality of #(a), thus there is a root.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.