Search code examples
algorithmgraphdirected-graphstrongly-connected-graph

Minimum number of edges for a disconnected directed graph to make it strongly connected

Consider an example of a disconnected directed graph G={V,E} with vertices V={a,b,c,d} and edges E={(a->b),(a->c)} where vertex d is isolated.

According to the answer here: (Minimal addition to strongly connected graph), the minimum number of edges required to ensure this graph turns out to be 3.

How to find where to add these edges to, i.e. the starting and ending vertex of an edge in this graph?

Solution

  • This is a surprisingly subtle problem. Eswaran and Tarjan (see below) were the first to claim a linear-time algorithm for it, but there was a bug, found and corrected by Raghavan (A note on Eswaran And Tarjan's algorithm for the strong connectivity augmentation problem). The linked PDF article contains a full treatment of the corrected algorithm.

    @article{doi:10.1137/0205044,
author = {Kapali P. Eswaran and R. Endre Tarjan},
title = {Augmentation Problems},
journal = {SIAM Journal on Computing},
volume = {5},
number = {4},
pages = {653-665},
year = {1976},
doi = {10.1137/0205044},
URL = { 
        http://dx.doi.org/10.1137/0205044
},
eprint = { 
        http://dx.doi.org/10.1137/0205044
}
}