English is not my first language so sorry for beeing unable to explain the situation as exactly as I would like to.
I try to proof that if i got serial processes clustered, clusters are always allowed to take the predecessors from their processes. So for example to be sure there can't be cycles in the clusters if there were no cycles in the processes.
An example: six serial processes:
$p_1\rightarrow p_2\rightarrow p_3\rightarrow p_4\rightarrow p_5\rightarrow p_6$
clustered to two milestones:
$\qquad\,\,\,\,\,\,\, m_1\qquad \qquad \qquad\,\,\,\,\, m_2$
$(p1\rightarrow p2\rightarrow p3)\rightarrow (p4\rightarrow p5\rightarrow p6)$
now I want to proof that this always means: $m_1\rightarrow m_2$
I tried it by building sets of ordered pairs but was unable to finish it successful.
Thanks!
This may be an example of a problem that appears simple based on looking at a diagram, but which actually has a potential for NP-hard complexity in full generality, clustering in directed acyclic graphs.
Even if the original processes are arranged serially, we need to impose some restriction on how "clusters" are formed to avoid introducing cyclic dependencies. To give a simple illustration, assume three serially dependent processes or "tasks":
$$ p_1 \; \to \; p_2 \; \to \; p_3 $$
If now processes $p_1,p_3$ were to be clustered into (say) $q_0$, then the resulting graph would have $q_0$ and $p_2$ mutually dependent on one another.
To avoid this we need a clearer distinction as to what clusters are allowed. Let $G = (V,E)$ be a directed acyclic graph representing the processes (vertices) and their immediate dependencies (edges), shown previously as arrows in the diagrams.
As is well-known, the reachability relation defines a partial order on any directed acyclic graph, the transitive closure of $E$. We will hereafter denote these wider dependencies with the order relation $\lt$, so that from the diagram above we infer $p_1 \lt p_3$.
Let us define a subset of processes $P$ to be convex if whenever $p_2$ depends on $p_1$ ($p_1 \lt p_2$) and $p_3$ depends on $p_2$ ($p_2 \lt p_3$), then $p_1,p_3 \in P$ implies $p_2 \in P$. For example, a singleton subset of $V$ would be convex.
Once this distinction is drawn, we can then prove that clustering a convex subset of processes does not introduce a cycle. Note that a convex subset need not be connected, and $P$ may consist entirely of independent vertices.
Prop. Let $P$ be a convex subset in $G$, a directed acyclic graph. Let $G'$ be a graph whose vertex set is $V' = {P} \cup (V\backslash P)$, i.e. the partition of $V$ into vertices not contained in $P$ but identifying all vertices in $P$ as a single node, and whose directed edges are:
$$E' = \{(u,v)\in E\;:\; u,v \in V\backslash P \} \cup \{(u,P)\;:\; u\in V\backslash P \text{ s.t. } \exists v\in P (\; (u,v)\in E \;) \} \cup \{(P,v)\;:\; v\in V\backslash P \text{ s.t. } \exists u\in P (\; (u,v)\in E \;) \}$$
Then $G' = (V',E')$ is again a directed acylic graph.
Proof: Suppose for contradiction that $G'$ contains a cycle. Since $G$ is cycle-free, exactly one of the nodes in this cycle must be $P$:
$$ P \; \to \; p_1 \; \to \; \ldots \; \to p_k \; \to P $$
where $p_1,\ldots,p_k$ are in $V$ but not in $P$. By construction we must have $u\in P$ s.t. $(u,p_1)\in E$ and $v\in P$ s.t. $(p_k,v)\in E$. Since $p_1 \lt p_k$ from the above dependencies, we have $u \lt p_1 \lt v$. Since $P$ is convex, this would imply $p_1 \in P$, contradicting the choice of $p_1$ not in $P$. QED
By induction any finite partition of $G$ into convex subsets would correspondingly define a directed acyclic graph on the "milestones" of those equivalence classes of nodes.