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.