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$
  • 3
    $\begingroup$ Looks like the partition into strong components to me. $\endgroup$ – Brendan McKay Aug 25 '14 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$ – Swapnil Bhatia Aug 25 '14 at 15:34
  • $\begingroup$ Can you give an example of an irreducible AP of maximum cardinality having more than one cell? $\endgroup$ – Brendan McKay Aug 26 '14 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$ – Brendan McKay Aug 27 '14 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$ – Swapnil Bhatia Sep 6 '14 at 4:04

Your Answer

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

Browse other questions tagged or ask your own question.