0
$\begingroup$

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.

Example graph to identify differences between AP and Strong Components

$\endgroup$
5
  • 3
    $\begingroup$ Looks like the partition into strong components to me. $\endgroup$ Aug 25, 2014 at 7:10
  • $\begingroup$ 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. $\endgroup$ Aug 25, 2014 at 15:34
  • $\begingroup$ Can you give an example of an irreducible AP of maximum cardinality having more than one cell? $\endgroup$ Aug 26, 2014 at 3:11
  • $\begingroup$ 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. $\endgroup$ Aug 27, 2014 at 2:36
  • $\begingroup$ 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. $\endgroup$ Sep 6, 2014 at 4:04

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.