Edge contraction in DAG

Question

I have a directed acyclic graph whose vertices are either red or black. I want to perform edge contraction between pairs of red vertices only, and avoid introducing cycles. The goal is to have the fewest number of red vertices remaining (and no cycles. Note that after edge contraction, the resulting self-loop is removed, it does not violate the no-cycles rule).

In the example below, I could merge vertices 1 and 3, or I could merge vertices 3 and 4, but I can't merge all 3 together, since this would introduce a cycle with black vertex 2.

I want to merge as many red vertices as possible, to reduce the number of nodes in the graph. How can I do this efficiently? I don't necessarily need an optimal solution (where optimal => smallest number of remaining vertices). I potentially have 100k nodes, evenly split red and black.

There are 2 optimal solutions for the simple example shown. Here is one.

Answer 1

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