5
$\begingroup$

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.

Coloured DAG

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. One possible solution

$\endgroup$
  • $\begingroup$ Could you just find all red vertices that have an indegree of 1 which is red, and an outdegree of 1, which is also red, and then remove those? I imagine that anything else could possibly change the structure of the graph. This would be linear. $\endgroup$ – Matt D Mar 10 '17 at 17:38
3
$\begingroup$

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
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.