2
$\begingroup$

Given a bipartite graph $G=(U,V,E)$, find a maximum matching.

Algorithm G:

  • Let $S\gets\emptyset$
  • Mark all edges unmatched
  • For $i\gets1$ to $|E|$
    • If $i$ is unmatched
      • $S\gets S\cup\{i\}$
    • End If
  • End For

Proposition: Algorithm G is optimal.

Proof: Feasibility is easy by induction. We prove that $|S|$ is maximum. By contradiction. Assume that there exists a set $S'$ of edges that has more edges than $S$. Since $S$ is maximal, then no edge could have been added to it without violating its feasibility. Thus, $|S|$ cannot be increased. Since $|S'|>|S|$, we reach a contradiction.

This is, of course, wrong, but I cannot find the error?

$\endgroup$
2
  • 2
    $\begingroup$ Why don't you pick an example input where this gives the wrong answer, work through what the proof says should be true, and check whether it is actually true and what is the first stage where it isn't true? That should help you find which stage in the proof was faulty. $\endgroup$
    – D.W.
    Nov 17 '19 at 7:33
  • $\begingroup$ Additionally, since the algortihm does not define a sequence of edges, there is always a run of this algorithm that output an optimal matching. For example the one that first iterate over edges in a fixed maximum matching and then the rest of the edges. Therefore, if you find it hard to construct a bad-example it is because you are concentrating on a predefined mximum matching in your graph. Try to go with other sequence/enumeration of edges on the same graph and you will find why the algorithm does not work $\endgroup$ Nov 17 '19 at 10:29
2
$\begingroup$

Consider the path graph of length 3: $x-y-z-w$.

Take $S$ to be $y-z$, and $S'$ to be $x-y,z-w$.


A set of constraints for which your kind of argument does work is known as a matroid. The greedy algorithm that you describe does work for matroids (and, more generally, for greedoids). Your set of constraints satisfies a weaker condition: it is 2-extendible, meaning that in order to add a new element (in this case, an edge), you need to throw out at most two existing elements. The greedy algorithm always gives a 2-approximation for such systems of constraints.

$\endgroup$
1
$\begingroup$

There is a difference between a maximal matching and a maximum matching. A maximal matching is a matching that is not a proper subset of any other matching. Hence, it is not possible to add another edge to a maximal matching (we can say a maximal matching can't be augmented). A maximum matching is a matching of maximal cardinality. Every maximum matching is also a maximal matching, but the converse is not necessarily true. Your statement "$|S|$ cannot be increased" is not true. There can exist other matchings having larger size, and the correct version would be that "$S$ cannot be augmented".

For example, let $G = (V,E)$ be a bipartite graph with bipartition $V=X \cup Y$, vertex sets $X = \{x_1,x_2\}, Y = \{y_1,y_2\}$ and edge set $\{x_1 y_1, x_1 y_2, x_2 y_1\}$. A greedy algorithm that first chooses $S = \{x_1 y_1\}$ cannot augment $S$ because it is maximal. However, there exists another matching $S' = \{x_1 y_2, x_2 y_1\}$ which has a larger cardinality than $S$.

Note that if both the subsets $S$ and $S'$ are maximal and $|S'| > |S|$ (or just $S \ne S'$), then $S$ is not a subset of $S'$, and each subset contains an element not in the other subset.

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