4
$\begingroup$

Consider the following algorithm for the maximum matching problem:

  1. Sort all nodes by their $\deg(v)$
  2. Take the node with minimal $\deg(v)$
  3. Take a random edge $(u,v)$ $\in$ $E$
  4. Add $(u,v)$ to $M$
  5. Delete all edges of $u$ and $v$ in $E$

I have to show that the algorithm isn't correct for undirected graphs with maximum degree 3. (It does find the maximum matching if the maximum degree is 2.)

To prove that the algorithm does not find a maximal matching for a graph $G$, I have to give a counterexample.

My problem is that I am drawing and drawing graphs, but the algorithm is always able to find the optimal matching. Could somebody help me to find a graph where the algorithm cannot find the optimal matching?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ As usual, a good strategy for dealing with this is random testing. In other words: implement the candidate algorithm; implement a "golden-reference" algorithm that is known to always give the correct solution; and try generating 1 million random small graphs and comparing what output the two algorithms give on each one. If you find any graph where they give a different answer, then you have answered your own question. $\endgroup$
    – D.W. ♦
    Dec 5 '16 at 17:56
  • $\begingroup$ ... sorry but the algorithm clearly fails... it removes a single edge, hence you can just take a graph with a few more edges than necessary and use that as a counter-example. You probably forgot to say to repeat all 5 steps until some condition (which one?) holds... $\endgroup$
    – Bakuriu
    Dec 5 '16 at 19:52
7
$\begingroup$

Consider a graph consisting of two triangles connected by an edge (a total of seven edges). Using this graph, Besser and Poloczek show that no greedy-like algorithm for maximum matching can be optimal even on graphs with maximum degree 3.

Improve this answer
$\endgroup$

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.