1
$\begingroup$

We have this algorithm which is supposed to find max matchings.


𝛭 = ∅;          //the matching is initialized to zero

for (𝑒 = {𝑥, 𝑦} ∈ 𝐸) {   //for each edge in the graph
 
    if ( x and y vertices are free)  //check if M U e is a matching

    𝛭 = 𝑀 ∪ 𝑒;
}

  1. Give an example where this algorithm does not calculate a max matching
  2. Prove that the algorithm is 2-approximation(The algorithm always calculates a matching M which has size |M| >= |M*|/2, where M* a max matching of the initial graph)
$\endgroup$
1
  • $\begingroup$ Please ask only one question per post. We're not particularly looking for posts that are just the statement of an exercise-style task and a request for us to solve it for you. What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$
    – D.W.
    May 17 at 4:07

1 Answer 1

0
$\begingroup$

For the lower bound take a path of three edges $P_3$. If the algorithm considers the middle edge first, it gets a matching of size one, meanwhile the matching consisting of the first and last edges has size two.

For the second part, note that the algorithm provided in the question yields an (inclusionwise) maximal matching, in the sence, that you cannot add more edges to the matching in such a way that it stays a matching. So it suffices to prove that any maximal matching in a graph is at least half as big as the maximum matching in this graph.

To prove this, we use notion of vertex cover. A vertex cover is a set of vertices that is incident to all edges in the graph. Note that if a graph $G$ has a matching of size $k$, then the smallest vertex cover of the graph must have size at lest $k$, since these edges do not share endpoints and we need to choose one endpoint of each such edge in the matching. So the vertex cover number of a graph $\nu(G)$ (the smallest size of a vertex cover) is at least the matching number $\mu(G)$ of this graph (the size of a maximum matching).

On the other hand, note that for a maximal matching $M$, the set $S$ containing both endpoints of each edge in $M$ is a vertex cover, since otherwise, there must exist an edge with both endpoints not in $S$, but such an edge can be added to $M$ to get a larger matching which contradicts the assumption that $M$ is maximal. Hence $2|M| \geq |S| \geq |\nu(G)|\geq |\mu(G)|$.

$\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.