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?

  • $\begingroup$ Please check whether my edit accurately captures your problem statement. (Note that if you have a set of dags, you can consider it as a single dag with multiple connected components.) $\endgroup$ – D.W. Sep 9 '16 at 20:44
  • $\begingroup$ Have you tried to solve any special cases? How about the special case where $G$ consists of only two connected components? e.g., if $G$ contains two components each of which is a totally ordered graph, this can be solved by bipartite matching. if $G$ contains two components each of which is a directed tree, do you know of any efficient algorithm for that special case? $\endgroup$ – D.W. Sep 9 '16 at 20:45

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.