# A certain Acyclic Partition of a digraph

Has the following object been defined in the literature? What is it called? And what literature studies it? Are there other characterizations of this? What properties are known?

Let $G$ be a directed loopless connected graph. The Acyclic Partition (AP) of $G$ is a partition of vertices $S = \{S_1, S_2, \ldots, S_k\}$ of $G$ with the following properties:

1) Each simple cycle $(v_{i_1}, \ldots, v_{i_n})$ of $G$ is contained in exactly one $S_i \in S$.

2) If $u,v \in S_i \in S$, and there is a path between $u$ and $v$, then all paths between $u$ and $v$ are completely contained in $S_i$.

If $S_i, S_j \in S$ and $(S \setminus \{S_i, S_j\}) \cup \{S_i \cup S_j\}$ is an AP, then I call $S$ reducible.

For a given graph $G$, I am interested in its irreducible AP of maximum cardinality.

Update:

I'd like to clarify between an irreducible AP and a Strong Components decomposition. In the example graph shown in the image below, a Strong Components algorithm would return three components $\{\{1,2\}, \{3\}, \{4,5\}\}$ , assuming a single vertex is defined to be connected to itself.

The Strong Component decomposition described above would be an AP. But since $\{\{1,2, 3\}, \{4,5\}\}$ is also an AP and is irreducible, it would be the preferred AP. (Irreducible APs are not necessarily unique.) This illustrates how APs are different from Strong Component decompositions.

Thank you.

• Looks like the partition into strong components to me. – Brendan McKay Aug 25 '14 at 7:10
• For a two-vertex unidirectional path, Strong Components would give two components, whereas its irreducible AP would be a single set containing both vertices. (The Strong Components Decomposition would be a reducible AP, since the union of the two sets is also an AP.) In general, it appears that a Strong Components Decomposition is a subset of an AP. But thanks for pointing out the very close connection to Strong Components that I had overlooked. – Swapnil Bhatia Aug 25 '14 at 15:34
• Can you give an example of an irreducible AP of maximum cardinality having more than one cell? – Brendan McKay Aug 26 '14 at 3:11
• In your example, $\lbrace\lbrace 1,2,3\rbrace\lbrace 4,5\rbrace\rbrace$ is not irreducible, since $\lbrace\lbrace 1,2,3,4,5\rbrace\rbrace$ is also an AP. For this reason, any irreducible AP with more than one cell must have at least three cells. – Brendan McKay Aug 27 '14 at 2:36
• Oh, yes! Thanks. I need to put some conditions on when $S_i, S_j$ in the definition of reducible, e.g. that they must be acyclic. But it does look like Strong Components are very close to what I am looking for. (The context is that I would like to define vertices that are guaranteed to indicate progress, say if the graph represented a process or a computation. – Swapnil Bhatia Sep 6 '14 at 4:04