1
$\begingroup$

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?

$\endgroup$
7
  • $\begingroup$ Can you please clarify what "disjoint component of $G(V,S)$" is? $\endgroup$
    – nir shahar
    Jun 21 at 23:40
  • $\begingroup$ A subset of edges and nodes in G that are not connected to other subsets of edges and nodes in G by any edges $\endgroup$ Jun 21 at 23:43
  • $\begingroup$ So are you talking about weakly connected components (i.e, convert the graph to be undirected, and then take the connected components in it)? $\endgroup$
    – nir shahar
    Jun 21 at 23:48
  • $\begingroup$ 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. $\endgroup$ Jun 21 at 23:54
  • $\begingroup$ To be clear, no I do not mean weakly connected component. $\endgroup$ Jun 21 at 23:55
1
$\begingroup$

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|$.

Additionally, it computes a correct set (which is easy to see why) and this set is the minimal set.

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.