0
$\begingroup$

I would like to partition a directed graph into subgraphs that all contain a simple cycle (if there is a solution for the given graph).

I know there are algorithms to compute the strongly connected components of a directed graph, like Kosaraju's algorithm for example. I'm looking for something similar, but a strongly connected component does not necessarily contain a simple cycle.

Can someone point me to the algorithm I'm looking for?

$\endgroup$
1
  • $\begingroup$ So, if you have a 4-node directed graph $G$ such as a triangle (that is a cycle) with one of the vertices connected to a the fourth node, a degree-1 node by an edge, you would want to leave the graph $G$ as is? i.e, you want each sub-graph to mandatorily have a cycle, if such a partition exists. $\endgroup$ – vvg Oct 23 '20 at 18:02
0
$\begingroup$

Let us start by making some observing that if some set of vertices induces a simple cycle, then these vertices are in the same strongly connected component (SCC), so any simple cycle of a directed graph must reside completely in one SCC. Also note that two vertices which are connected by edges in both directions is a simple cycle, so the only SCCs which do not contain a simple cycle are singletons (i.e. they consist of exactly 1 vertex). The vertex contained in such a SCC is not part of any simple cycle (otherwise it would be in a different SCC by our first observation) so any graphs with singleton SCCs does not admit a partition of the kind you are seeking.

It follows that such a partition can be obtained (if it exists) by partitioning the graph into SCCs.

$\endgroup$
1
  • $\begingroup$ That makes sense, thank you! $\endgroup$ – user3182899 Oct 23 '20 at 20:39

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.