Find the maximum amount of non-intersecting 2-cycles in an undirected graph

Question

I have an adjecency matrix and an adjecency list (I can use either) that both represent a graph.

Basically, how can I pair off connected vertices in the graph so that I am left with the least unpaired (and disconnected) vertices?

I have tried this brute-force strategy:

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

Which is alright for the smaller graphs, but the graphs I am working with have up to 100 vertices.

Is there a way to optimise this so that it can handle that large of a graph?

And is this synonymous to another problem that has algorithms for it? I searched for "Most non-intersecting k-cycles" and variations of that, but could not find an algorithm to do this.

Answer 1

There is polynomial time solution (it works in O(|V|^2 * |E|)). It's known as the Blossom algorithm. The idea is to do something like a matching in a bipartite graph, but also shrink the cycles of odd length into one vertex.