Maximal-size set of disjoint edges

Question

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:

1. Pick the vertex of least degree not yet in our solution.
2. Choose its neighbor of least degree, and add the edge between them to the solution.
3. Remove both vertices from the graph.
4. 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!

Answer 1

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: http://en.wikipedia.org/wiki/Edmonds%27s_matching_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$).