Implement DigraphStrongVertexConnectivity #857
Description
A digraph D is strongly connected if for every pair of vertices u, v in D there exists a directed path starting at u and ending in v and a directed path starting at v and ending in u. A strong separating set is any set of vertices S such that the graph D - S obtained by removing the vertices in S from D is not strongly connected. The strong vertex connectivity of D is the size of the smallest strong separating set of D. It would be nice to have a function computing the strong vertex connectivity of a digraph (a function for computing the weak vertex connectivity is being implemented in #94, if we ever get it merged).
It is not immediately clear how to compute this efficiently. The naive method of trying to remove increasingly large subsets won't scale very well past graphs with 10-20 vertices and strong vertex connectivity over 10. For the weak vertex connectivity, maximum flow computations are used to significantly speed things up. Digraphs has a maximum flow function DigraphMaximumFlow, so the question becomes how to apply it to compute strong vertex connectivity.
I couldn't find much online about strong vertex connectivity, these lecture notes by Frédéric Havet [1] are the best I could find, but they don't go much into detail on the computational aspects. For the weak vertex connectivity, we use the results from Section 4 of [2]. I think implementing the strong case would essentially involve figuring out how to adapt Algorithm 9 for computing the weak local vertex connectivity from [2] to compute the local strong vertex connectivity. This is likely quite non-trivial and would require re-deriving some results. See also Section 6.2 and especially Theorem 6.4 of [3] for more theory on the weak vertex connectivity case.
1: Frédéric Havet, Lecture notes, Chapter 5
https://www-sop.inria.fr/members/Frederic.Havet/Cours/connectivity.pdf
2: "Connectivity Algorithms" by Abdol-Hossein Esfahanian's
https://www.cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf
3: Even S. Applications of Network Flow Techniques.
In: Even G, ed. Graph Algorithms.
Cambridge University Press; 2011:117-145.
https://doi.org/10.1017/CBO9781139015165