Inspired by a "real-world" puzzle (actually, an unimportant aspect of a free-to-play game someone I know is playing)...
Given an arbitrary (finite) undirected graph, I want to compute a largest-possible set of disjoint edges in the graph - that is, no two edges in the set share a vertex.
I think this should be a standard graph-theory problem. Is there a good algorithm for this? For all I know, it or a close variant is NP-hard (it feels like it could go either way), but I'm curious.
I'm also curious as to whether the following greedy algorithm is a good approximation to the optimal solution:
- Pick the vertex of least degree not yet in our solution.
- Choose its neighbor of least degree, and add the edge between them to the solution.
- Remove both vertices from the graph.
- Repeat until the graph has no edges remaining.
There might be a clever example on which this does poorly, but I'd be interested in how bad an approximation it can give!
$\endgroup$ 11 Answer
$\begingroup$This is called the maximum matching problem, and it is one of the few graph problems for which there is a non-obvious polynomial time algorithm! It's called Edmonds's blossom algorithm:
Edit: Following Casteels's suggestion, here's an example showing that the greedy algorithm might only get you half of the optimal: let $N$ be a large integer, and start with $N$ disjoint paths of length $3$. Then add three extra vertices $u,v,w$, and connect $u,v,w$ to both endpoints of all $N$ paths.
The point is that the degrees of the vertices in each of the original $N$ paths are now 4—2—2—4 whereas before adjoining $u,v,w$ they were 1—2—2—1. At the first step, the OP's greedy algorithm will select one of the degree-$2$ interior vertices, plus its interior neighbour for removal. This leaves behind two degree-$3$ vertices, so the pattern continues with another path, and so on until all $N$ paths are hollowed out. The remaining graph consists of just three disconnected $2N$-stars, each of which admits only one additional edge.
Thus, the greedy algorithm produces $N+3$ edges, but there is certainly a matching of size $2N$ by using the two non-interior edges of each path (I think the maximum is $2N+1$ by augmenting one of those matchings through $u$ and $v$).
$\endgroup$ 0
