無向グラフの非交差2サイクルの最大値を求める

Question

私は隣接行列と隣接関係リストを持っています（いずれも使用できます）。どちらもグラフを表しています。

基本的に、グラフ内の接続された頂点をペアにして、ペアのない（そして切断された）頂点が残っているようにするにはどうすればよいですか？

私はこの強引な戦略を試してみました：

def max_pairs(adj_matrix): 
    if len(adj_matrix) % 2: 
     # If there are an odd amount of vertices, add a disconnected vertex 
     adj_matrix = [adj + [0] for adj in adj_matrix] + [0] * (len(adj_matrix) + 1) 
    return max(adj_matrix) 

def all_pairs(adj_matrix): 
    # Adapted from http://stackoverflow.com/a/5360442/5754656 
    if len(adj_matrix) < 2: 
     yield 0 
     return 
    a = adj_matrix[0] 
    for i in range(1, len(adj_matrix)): 
     # Recursively get the next pairs from the list 
     for rest in all_pairs([ 
       adj[1:i] + adj[i+1:] for adj in adj_matrix[1:i] + adj_matrix[i+1:]]): 
      yield a[i] + rest # If vertex a and i are adjacent, add 1 to the total pairs 

小さいグラフの大丈夫ですが、私が働いているグラフは、100の頂点まで持っています。

これを最適化して、大きなグラフを処理できる方法はありますか？

これはアルゴリズムのある別の問題と同義ですか？私は「ほとんど交差していないkサイクル」とそのバリエーションを検索しましたが、これを行うアルゴリズムは見つかりませんでした。

Answer 1

多項式時間解があります（O(|V|^2 * |E|)で動作します）。それはBlossom algorithmとして知られています。この考え方は、二部グラフのマッチングのようなことをすることですが、奇数長のサイクルを一つの頂点に縮小します。