Re: Graph Theory: Cutting a Graph into Two in an Artificial Chemistry

I don't have time to do this "properly", but the
general question for general graphs has the feel
of NP-Complete. However, your situation will have
many many more constraints on the graph. For
example, you won't have 6000 vertices, all mutually
connected.

It feels to me like the graphs you are interested
in will have only limited sorts of minimal cycles,
and each "atom" will have small degree. In that
case there are going to be clever branch-and-bound
searches that should work.

I don't, however, know of anything "off the shelf".
.

Relevant Pages