3
$\begingroup$

I'm preparing for exam and I came across this problem:

We say that a graph is König's graph when the sizes of its minimum vertex cover and maximum matching are equal. Find a polynomial time algorithm deciding if a graph is König's graph.

I'm stuck. I know that in bipartite graphs this always holds. I also know that we can find maximum matching in every graph in polynomial time. But I don't know how to connect this with minimum vertex cover problem which in general is NP-complete.

$\endgroup$
3
$\begingroup$

Let $M$ be a maximum matching. Any vertex cover must contain at least one vertex out of each edge in the matching. Hence the size of a minimum vertex cover equals the size of the maximum matching if there's a vertex cover consisting of one vertex out of each edge of $M$.

Denote the edges of $M$ by $e_1 = (x_1,y_1),\ldots,e_m = (x_m,y_m)$, where $m = |M|$. Let $v_i$ be a Boolean variable which determines which of $x_i,y_i$ we pick. We can express the constraint that an edge not in $M$ is covered as a disjunction of two literals. Hence we can express the existence of a vertex cover of size $M$ as a 2CNF. Since 2SAT is solvable in polynomial time, we can determine whether such a vertex cover exists.

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