Edge contraction in DAG
Here are some pointers to one possible solution, taken from Google's TensorFlow XLA compiler. 

Their use case is to partition a computation graph (usually a DAG) into subgraphs and place them on different devices, while satisfying data dependencies and maximizing each subgraph. For instance, in your question, assuming nodes must either be placed on CPU (red) or GPU (black), we would compute subgraph Node{1, 3} on CPU, and then compute Node{2} on GPU, and finally Node{4} on CPU.

The algorithm consists of two parts:


Union-find for keeping track of node merging


Start reading from here, the main loop for contracting edges

An "incremental cycle detection" algorithm


This functionality is implemented in the GraphCycles class
It is based on a dynamic topsort algorithm for DAG as documented here