# Minimal cut of a directed graph such that disjoint elements are strongly connected

Given an arbitrary directed graph $$G$$ (which may not necessarily be connected) find a minimum set of edges $$S\subseteq E$$ such that every disjoint component of $$G(V,E\cap S')$$ is strongly connected.

A "minimum set" refers to the set with the minimum number of edges. The best algorithm I could come up with is exponential, ex. iterating over all sets of edges. Could this be done faster or probabilistically?

• Can you please clarify what "disjoint component of $G(V,S)$" is? Jun 21 at 23:40
• A subset of edges and nodes in G that are not connected to other subsets of edges and nodes in G by any edges Jun 21 at 23:43
• So are you talking about weakly connected components (i.e, convert the graph to be undirected, and then take the connected components in it)? Jun 21 at 23:48
• sorry, I was unclear, instead of "disjoint" in my original question, I should have used "disconnected" I mean to say that after cutting some number of edges, every disconnected component of the graph is strongly connected. Jun 21 at 23:54
• To be clear, no I do not mean weakly connected component. Jun 21 at 23:55

There is a fast algorithm for this problem: (assuming you meant that $$S$$ is the set of edges being removed from $$G$$)
1. Compute the strongly connected components of $$G$$, with an algorithm of your choice. For example, this DFS-based algorithm can work in $$O(|V|+|E|)$$.
2. Define $$S$$ to be the set of edges between any two strongly connected components.
This algorithm is very efficient, running in linear time with respect to $$|V|$$ and $$|E|$$.
Indeed, if there is an edge $$(v,u)$$ that is between two strongly connected components, but it is not in $$S$$, then $$(v,u)$$ will be in the new graph. Notice there is no path $$u\rightsquigarrow v$$ (otherwise $$v$$ and $$u$$ would have been in the same strongly connected component) and hence, the new graph will contain a component that is not strongly connected.