1
$\begingroup$

I am studying Matching Theory on Graphs and I am wondering if I understand the characterization of the problems right.

Definition: Let $G = (V, E)$ a graph. A set $M \subseteq E$ is called a matching in $G$ if and only if each vertex $v$ in $V$ is incident to at most one edge in $M$, that is, $\forall v \in V ( \forall w \in V ( \forall x \in V (( vw \in M \wedge vx \in M) \rightarrow w = x)))$ holds. Edges may be weighted. For any matching $M$ and weight function $w: E \rightarrow \mathbb Q$ we define $w(M) := \Sigma_{e \in M} w(e)$.

In the following are the definitions of the two computational problems I am currently working with. For simplicity sometimes I use bipartite graphs only.


Problem Name: $\text{MAXIMUM-CARDINALITY MATCHING}$

Input: A graph $G = (V, E)$.

Task: Find a matching $M$ such that $|M|$ is maximum.


Problem Name: $\text{MAXIMUM-WEIGHT BIPARTITE MATCHING}$

Input: A bipartite graph $G = (V, E)$ with weights $w: E \rightarrow \mathbb Q$ on the edges.

Task: Find a matching $M$ such that $w(M)$ is maximum.


Definition: A path $P$ in $G$ is called $M$-alternating if and only if the edges in $P$ are alternatingly out of and in $M$.

Definition: A path $P$ in $G$ is called $M$-augmenting if and only if $P$ is $M$-alternating and both its end vertices are not covered by $M$.

Thoerem (I think it is due to Peterson): Let $G = (V, E)$ be a graph and let $M$ be a matching in $G$. Then either $M$ is a solution to $\text{MAXIMUM-CARDINALITY}$ $\text{MATCHING}$ or there exists an $M$-augmenting path.

Theorem (Egervary): Let $G = (V, E)$ be a bipartite graph and let $w: E \rightarrow \mathbb Q$ be a weight function. Then the maximum weight of a matching in $G$ (that is, the weight of a solution to the $\text{MAXIMUM-WEIGHT}$ $\text{BIPARTITE MATCHING}$ problem) is equal to the minimum value of $y(V)$, where $y : V \rightarrow \mathbb Q$ is such that $y_u + y_v \geq w_e$ for each edge $e = uv$. If $w$ is integer, we can take $y$ integer.

My question is: Does there exist a simpler characterization of the $\text{MAXIMUM-WEIGHT}$ $\text{BIPARTITE MATCHING}$ problem similar to Peterson's Theorem? What is wrong with the following characterization?

First, let $A \; \Delta \; B$ denote the symmetric difference of two sets $A$ and $B$. Further, if $P$ is a path, then let $E(P)$ denote the set of edges in $P$.

Hypothesis: Let $G = (V, E)$ be a bipartite graph, $w: E \rightarrow \mathbb Q$ a weight function, and $M$ a matching in $G$. Then either $w(M)$ is maximum or there exists an $M$-alternating (note: not necessarily $M$-augmenting) path $P$ such that $M' := M \; \Delta \; E(P)$ is a matching in $G$ and $w(M') > w(M)$.

Is the hypothesis correct? If not, why is it wrong? What about the hypothesis with respect to non-bipartite graphs? If the hypothesis is correct, why is always Egervary's Theorem used?

$\endgroup$
2
$\begingroup$

It is nice for OP to extract the essence of the proof for Berge's Lemma, which is described as the "Theorem (I think it is due to Peterson)" to create the hypothesis.

"Is the hypothesis correct? If not, why is it wrong?" Yes, it is correct.

"What about the hypothesis with respect to non-bipartite graphs?" Yes, it is still correct with respect to non-bipartite graphs.

"If the hypothesis is correct, why is always Egervary's Theorem used?" Well, I cannot avow Egervary's Theorem is always used (when? and where?). It is true, however, that in the case of bipartite graph, Egervary's Theorem is instrumental in creating a fast and easily-implementable algorithm to find the maximum weight matching. In comparison, I cannot find a similarly good algorithm for which the hypothesis can be equally helpful. So it is no wonder that Egervary's Theorem is usually mentioned when we come to the maximum weight matching for bipartite graph.

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