Tree or Graph contraction

Question

I am currently using Python to solve a "tree summarization" problem. My tree consists of nodes which have weights and children. An example

Node(
    name: "Parent", weight: 20, children: {[
        Node(name: "Child 1" weight: 10, children: {[]},
        Node(name: "Child 2", weight: 10, children: {[
           Node(name: "Grandchild 1", weight: 5, children: {[]}
        ]}
     ]})

I am interested in finding all possible graphs obtainable by edge contractions. When I contract two edges, the old vertices are replaced by a new vertex whose weight is the sum of the old vertices. For example, contracting Child 2 with Grandchild 1 results in:

Node(
    name: "Parent", weight: 20, children: {[
        Node(name: "Child 1" weight: 10, children: {[]},
        Node(name: "(Child 2, Grandchild 1)", weight: 15, children: {[]}
     ]})

Of course this is only one possible edge contraction. Even for this small tree, there are many more contractions (e.g. (child 1, child 2), (child 1, parent), (child 2, parent)).

For each of these new trees, I need to again find all trees obtained by contracting one node (ultimately, the problem is to reduce a n-node tree to an m-node tree).

I am currently "brute forcing", recursively calling edge_contract() until I reach trees of the right node size. But the code needs to be able to work on moderately sized trees (~25-50 nodes) and the current implementation is not.

Is this type of tree contraction a solved problem. What are some good ways to tackle the problem?

Answer 1

Each time you transform a tree, you are deciding on the sets of edges that you are contracting. In the example you gave, the set would contain only one edge from "Child 2" to Grandchild 1".

If you are interested in finding all the trees that you can get by contracting the edges, that would be 2^d(where d is the total number of edges in the original tree). As you said, you want to convert a n-node tree to an m-node tree. If you already know "m" then you need to find all the sets from the total 2^d sets that have m-1 elements(as m node tree would have m-1 edges).

If you are interested in only a subset of m-node tree, then randomly select how many you want.