0
$\begingroup$

Definition: A set $CโŠ†V$ and a collection of subsets $๐ต_1,โ€ฆ,๐ต_๐‘˜โŠ†V$ is an odd vertex cover if for every edge ๐‘’ either $๐‘’โˆฉ๐ถโ‰ โˆ…$ or $๐‘’ โŠ† B_i$ for some ๐‘–.

The cost of the odd vertex cover is defined to be: $|C| + \sum_{i=1}^{k} \lfloor{\frac{|B_i|}{2}}\rfloor$

Without loss of generality, we may assume that all the sets $B_i$ are of odd size, hence the name, and that C and $B_1,โ€ฆ,B_k$ are disjoint.

Theorem: In any graph, the size of the maximum matching is equal to the cost of the minimum odd vertex cover.

How can I prove it? I tried to use Edmond's algorithm for finding maximum match. Then to take one side of these edges as $C$ and the blossoms as $B_i$'s. I don't have a formal proof for that though.

$\endgroup$
2
  • $\begingroup$ Are you familiar with the Gallai-Edmonds decomposition? $\endgroup$
    – Dániel G.
    Jan 31 at 19:10
  • $\begingroup$ No, this question was asked in a course I'm taking and the lecturer suggested the method I tried above $\endgroup$
    – Lianga
    Feb 1 at 15:53

0

Reset to default

You must log in to answer this question.