# Either find a perfect matching, or return a witness that none exist [duplicate]

I am looking for a polynomial-time algorithm that takes as input a bipartite graph $$(X\cup Y, E)$$, and returns one of two options:

1. If a perfect matching exists, it returns the matching;

2. Otherwise, it returns a witness based on Hall's theorem, i.e., a set $$S\subseteq X$$ such that the number of neighbors of $$S$$ is smaller than $$|S|$$.

I found in wikipedia various algorithms for finding a maximum matching in an unweighted bipartite graph. Such algorithms can be used to determine if a perfect matching exists. But does any of these algorithms also return an evidence in case of failure?

EDIT: I have read the links in the answer of Yuval Filmus below, but it took me some time to fill in the missing details. For future reference, here is a detailed solution. Below, let $$n := |X| = |Y|$$.

Step 1. Define a flow network with $$2n+2$$ nodes in the following structure:

$$s \rightrightarrows X \rightrightarrows Y \rightrightarrows t$$

where:

• $$s$$ is a new source node connected to all vertices in $$X$$ with capacity 1;
• every original edge of $$E$$ is directed from $$X$$ to $$Y$$ with capacity $$\infty$$;
• each vertex in $$Y$$ is connected with capacity 1 to a new sink node $$t$$.

Step 2. Use the Ford-Fulkerson algorithm to find a maximum flow in that graph. Suppose the maximum flow size is $$m$$ (which must be at most $$n$$).

Step 3. If $$m = n$$ then we are done - the flow induces a matching of size $$n$$ which is perfect.

Step 4. Otherwise, $$m < n$$. The FF algorithm also returns an $$s$$-$$t$$ minimum cut of size $$m$$ - a partition $$(C,C')$$ of the vertices in the graph, such that $$s\in C$$, $$t\in C'$$, and the sum of capacities of edges directed from $$C$$ to $$C'$$ is $$m$$.

This cut cannot cross any edge of $$E$$, since these edges have infinite capacity. Hence, the cut size is determined by edges from $$s$$ to $$X\cap C'$$ and from $$Y\cap C$$ to $$t$$. So $$m = |X\cap C'| + |Y\cap C| = (n-|X\cap C|)+|Y\cap C|$$. Hence: $$|X\cap C| = |Y\cap C| + (n-m) > |Y\cap C|$$. Since the cut cannot cross edges of $$E$$, all neighbors of $$|X\cap C|$$ must be in $$|Y\cap C|$$, so $$|X\cap C|$$ is the desired Hall-violator.

• You specifically want Hall's theorem type evidence? The fact that the maximum matching has cardinality strictly less than $|V|/2$ is pretty strong evidence that there's no perfect matching (e.g., it can be verified in polynomial time). – David Richerby Jan 15 '19 at 16:27

You can find a maximum matching in a bipartite graph using network flow. The min cut max flow theorem translates to Hall's condition, so a min cut would give you the "evidence". See for example this document or this question on Mathematics.

• By "min cut" you mean "source-sink min-cut" - a set $(C,C')$ such that $s\in C, t\in C'$, and the sum of capacities directed from $C$ to $C'$ is minimized? – Erel Segal-Halevi Jan 16 '19 at 8:50
• I mean min cut in the sense of the min cut max flow theorem, which is probably the same as what you wrote. – Yuval Filmus Jan 16 '19 at 8:51

I would use a degenerated version of the Hungarian algorithm (O(n^3)).

In the basic version on a U, V bipartite graph, you loop on the elements of x of U to give them the best assignement y from V. if y is already assigned, you make a growing subset X of U that may change their affectation without regret until:

• either X has at least |X| neighboors in V => then you move your assignements to add properly x.
• either X cannot grow anymore without regret and you accept to modify the weights (as the regret cannot be prevented).

For your problem, there is no weight. So if you are in the second case, just break off and you have your X subset. Else you will reach the last x of U and have a perfect assignement.

• Sounds interesting. But what do you mean by "regret"? – Erel Segal-Halevi Jan 16 '19 at 6:20
• For your problem there is no need to consider weights, regret and the assignement optimization. But let say one needs to maximize the weights of the edges selected. Every x of U expects the best y of V (max. edge x-y). Generally, even in a perfect assignement, some x will have a less interesting y assigned. The regret of this assignement is the weight difference with respect to the best edge. – Optidad Jan 16 '19 at 8:57