graph-problem.md

Problem

Given a directed graph with weighted nodes, find the a set of cycles that don't share any nodes, maximizing the total sum of the node weights. Ties can be broken arbitrarily.

Example 1

All nodes have weight 1

a -> b
^    |
|    v
d <- c

The list of cycles is [a->b->c->d weight 4]

Example 2

All nodes have weight 1

a -> b -> c
^    |    |
|    V    V
f <- e <- d

The list of cycles is [a->b->c->d->e->f weight 6]

Example 3

All nodes have weight 1

a -> b -> d -> e
^    |     ^   |
 \   |       \ |
   \ V        \V
     c         f

The list of cycles is [a->b->c weight 3, d->e->f weight 3]

Example 4

All nodes have weight 1 except for e which has weight 5

a -> b -> c
^    |    |
|    V    |
f <- e    |
^         |
|-------- d

The list of cycles is [a->b->e->f weight 8]

Example 5

All nodes have weight 1

a -> b -> d -> e
^    |     ^   |
 \   |       \ |
   \ V        \V
     c <- g <- f

The list of cycles is [a->b->d->e->f->g->c weight 7]