1
$\begingroup$

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!

$\endgroup$
1
  • 3
    $\begingroup$ PS, at the very least, you algorithm will find a maximal matching (a matching that cannot be extended). It is not too hard to show that any maximal matching has at least half as many edges as a maximum matching. So your algorithm will get at least half way to optimal. I'm not sure about an example showing that it can't get much higher than that. $\endgroup$
    – Casteels
    Aug 28 '14 at 10:30
5
$\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: 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$).

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.