3
$\begingroup$

I came across this problem in Tim Roughgarden's course on Coursera:

In this problem you are given as input a graph $T=(V,E)$ that is a tree (that is, $T$ is undirected, connected, and acyclic). A perfect matching of $T$ is a subset $F \subseteq E$ of edges such that every vertex $v \in V$ is the endpoint of exactly one edge of $F$. Equivalently, $F$ matches each vertex of $T$ with exactly one other vertex of $T$. For example, a path graph has a perfect matching if and only if it has an even number of vertices.

Consider the following two algorithms that attempt to decide whether or not a given tree has a perfect matching. The degree of a vertex in a graph is the number of edges incident to it. (The two algorithms differ only in the choice of $v$ in line 5.)

Algorithm A:

While T has at least one vertex:
  If T has no edges: 
    halt and output "T has no perfect matching."
  Else:
    Let v be a vertex of T with maximum degree.
    Choose an arbitrary edge e incident to v.
    Delete e and its two endpoints from T.
[end of while loop]
Halt and output "T has a perfect matching."

Algorithm B:

While T has at least one vertex:
  If T has no edges: 
    halt and output "T has no perfect matching."
  Else:
    Let v be a vertex of T with minimum non-zero degree.
    Choose an arbitrary edge e incident to v.
    Delete e and its two endpoints from T.
[end of while loop]
Halt and output "T has a perfect matching."

Now, the answer key says:

Algorithm $A$ can fail, for example, on a three-hop path. Correctness of algorithm $B$ can be proved by induction on the number of vertices in $T$. Note that the tree property is used to argue that there must be a vertex with degree $1$; if there is a perfect matching, it must include the edge incident to this vertex.

However, I think I found a counter-example which shows that Algorithm B may not be correct. Am I missing something? Consider the following graph (say $T$):

enter image description here

If we follow B:

Step 1: Let $v=3$ (all vertices have the same degree) and $e=(2,3)$. Remove $e$ along with vertices $3$ and $2$.

enter image description here

Step 2: Let $v=1$ and $e=(0,1)$. Remove $e$ along with vertices $0$ and $1$.

Step 3: No vertices are left. Hence we get the output: "T has a perfect matching."

But clearly, our original graph was not a perfect matching as all the nodes were of degree $3$.

Note: I assumed that ties are meant to be broken arbitrarily by the algorithm.

$\endgroup$
  • $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Sep 27 '18 at 23:31
4
$\begingroup$

"Consider the following two algorithms that attempt to decide whether or not a given tree has a perfect matching". Your graph is NOT a tree as it has a cycle $0, 1, 2, 0$.

Furthermore, your graph does have a perfect matching. In fact, the edges $(2,3)$ and $(0,1)$ obtained by your step 1, 2 and 3 is a perfect matching. And hence, it is not true that "our original graph was not a perfect matching as all the nodes were of degree 3". Plenty of graphs whose nodes are all of degree 3 have a perfect matching.

$\endgroup$
1
$\begingroup$

The algorithms are understated: When a vertex is deleted, all edges incident to that vertex are also deleted, otherwise we're left with dangling edges.

Consider the path tree $ A - B - C - D $. Algo A chooses vertex $ B $, and say, edge $ (B, C) $. After deleting vertices $ B $ and $ C $, and all the edges, we're left with vertices $ A $ and $ D $ with no edges. Algo A halts, and incorrectly declares that $ T $ doesn't have perfect matching (it does, $ \{ (A, B ), (C, D) \} $).

Lets prove the correctness of algo B by induction. For $ \lvert V \rvert = 1 $, it correctly identifies that $ T $ doesn't have perfect matching. For $ \lvert V \rvert = 2 $, it correctly identifies that $ T $ has perfect matching. Clearly, for $ T $ to have perfect matching, $ \lvert V \rvert $ must be even. Assume algo B works for $ \lvert V \rvert = k $. Let us add a new vertex $ v $ and a new edge $ (v, w) $ to $ T $, where $ w $ is some existing vertex in $ T $. Clearly, for $ T $ to have perfect matching, it must include edge $ (v, w) $ (since that's the only way to match vertex $ v $). By construction, algo B picks $ v $ and removes edge $ (v, w) $ in some iteration, leaving $ \lvert V \rvert = k - 1 $, which by inductive hypothesis, is correctly solved by algo B.

Therefore, algo B is correct.

The solutions to the other questions from the course are available on my blog.

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