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!