1

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.

Artyer
  • 31,034
  • 3
  • 47
  • 75
  • Should they be vertex or edge disjoint? You want to find the way to pair them up in such a way that the number of pairs is as large as possible and each vertex belongs to at most one pair, don't you? – kraskevich Dec 26 '16 at 19:27
  • @kraskevich Yes. Pair them up where all the vertices are in, at most, one pair, and each pair is connected by an edge. – Artyer Dec 26 '16 at 19:29

1 Answers1

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.

kraskevich
  • 18,368
  • 4
  • 33
  • 45