I have a dag $G=(V,E)$ and a coloring $c:V \to C$ that assigns a color to each vertex. I want to partition the vertices into groups, in a way that minimizes the number of groups, such that the following conditions are satisfied:
(a) All vertices in the same group must have the same color.
(b) If there is a path $v \leadsto w$ between two different vertices $v,w$, then $v,w$ cannot be placed in the same group.
Is there an efficient algorithm for this problem?
Here is another way to think about this problem. I have two or more disjoint acyclic directed subgraphs and I want to merge the disjoint subgraphs by joining the nodes into groups, i.e. not creating an edge but by grouping set $V_i$ from subgraph $G_n$ with set $V_j$ from subgraph $G_m$. Edges may only go from one node to another if they are not in the same set. Nodes within the same set do not form edges, they are just grouped together as a graph component. The goal is to minimize the number of sets of nodes (single nodes will count as a set), subject to the following conditions:
$i)$ Since we are dealing with directed graphs, it is important that the topological order of the node sets is maintained, even after merging.
$ii)$ Only vertices with the same color are allowed to be in the same group.
$iii)$ We may only group two nodes $v,w$ if there's no path from $v \rightarrow w$ or $w \rightarrow v$ .
Here is a simple example to illustrate the problem:
Can this be solved efficiently?
