python - ツリーまたはグラフの縮小

Question

現在、Python を使用して「ツリーの要約」の問題を解決しています。私のツリーは、重みと子を持つノードで構成されています。例

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: {[]}
        ]}
     ]})

エッジ収縮によって得られるすべての可能なグラフを見つけることに興味があります。2 つのエッジを縮小すると、古い頂点が新しい頂点に置き換えられます。重みは古い頂点の合計です。たとえば、子 2 を孫 1 と契約すると、次のようになります。

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

もちろん、これは可能なエッジ収縮の 1 つにすぎません。この小さなツリーでも、もっと多くの短縮形があります (例: (child 1, child 2), (child 1, parent), (child 2, parent))。

これらの新しいツリーのそれぞれについて、1 つのノードを縮小することによって得られるすべてのツリーを再度見つける必要があります (最終的に、問題は n ノード ツリーを m ノード ツリーに縮小することです)。

私は現在、適切なノード サイズのツリーに到達するまで、edge_contract() を再帰的に呼び出して「ブルート フォーシング」を行っています。しかし、コードは適度なサイズのツリー (~25 ～ 50 ノード) で機能する必要があり、現在の実装はそうではありません。

このタイプの木の収縮は解決済みの問題ですか。問題に取り組むための良い方法は何ですか?