0
$\begingroup$

A vertex cover is a set of vertices such that each edge of the graph is incident to at least one vertex of the set. A minimum vertex cover is a vertex cover with minimal cardinality.

From codeforces,

The minimum vertex cover should contain exactly one vertex for every edge in the maximum matching $M$. So let's assign a boolean variable for every edge in $M$, say, $x_i = 0$ if the $i$-th edge adds its left end to the vertex cover. One can build all the dependencies over these variables. For example, if there exist edges $(u,v) \in M$ and $(u,w) \notin M$, while $w$ is not saturated by $M$, we have to set $x_i$ equal to 0, because there is no other way to cover the edge $(u, w)$. All the other cases are handled trivially.

As a result, we obtain a full system of restrictions for the set of variables. Finding an arbitrary valid assignment is a classical 2-SAT problem. So we have basically reduced the minimum vertex cover problem to 2-SAT without thinking too much.

I don't understand the variables. I have an edge from maximum matching then I might have both the endpoints of that edge in the vertex cover. But this scheme does not allow this.

This is the graph I have ($2K_2$) two edges in the maximum matching:

2K_2

For the first edge I took left vertex in the cover $x_1=0$ (according to the blog in the link) for the second edge I took right vertex in the cover $x_2=1$.

Questions:

  1. How final 2-sat will be true?
  2. Can anyone explain what will be the relation between $x_1$ and $x_2$?
$\endgroup$
16
  • 1
    $\begingroup$ Vertex cover for bipartite graph is solvable in poly-time by reducing it to perfect matching problem. What I understand from you, is that you try to solve bipartite graph by Linear Programming of vertex cover ("never" ==>"vertices got 0", "always"==> vertices got 1", "neither" ==>"1/2 wight". This LP has only 3 solutions. But if you give a LP a bipartite graph, then in theory it must give you 0/1 solution; since bipartite is not hard problem. $\endgroup$
    – YOUSEFY
    Apr 19, 2019 at 10:28
  • 3
    $\begingroup$ (1) It looks like you already asked this question at cs.stackexchange.com/q/107322/755. Also, you already about this problem at cs.stackexchange.com/q/103534/755 and got an algorithm for it (albeit a slightly different one). Please don't re-ask your question multiple times; that's not acceptable here. If your question differs from some existing one, it is your responsibility to explain clearly how this question differs from the previous ones. $\endgroup$
    – D.W.
    Apr 22, 2019 at 4:38
  • 1
    $\begingroup$ (2) I can't tell what you are asking here. We are a question-and-answer site, so we require you to ask a specific question in the body of your post. A question usually ends with a "?". I don't see any question here. I only see declarative statements. That's not suitable here. Don't force us to guess what your question might be. $\endgroup$
    – D.W.
    Apr 22, 2019 at 4:42
  • 1
    $\begingroup$ The question is not clear. I also removed "Read this blog" as you cannot expect people to read an article to understand your question. The question should be self-contained. $\endgroup$
    – Pål GD
    Apr 22, 2019 at 13:12
  • 2
    $\begingroup$ Comments exist to help you improve your question. Please don't use them to complain about downvotes or how your question is being received by others. Everyone is allowed (and encouraged) to vote according to our conscience; that helps us maintain the quality of the site and are critical for the success of the site. You are not entitled to an answer -- everyone here is a volunteer, and they are free to help or not help as they choose. $\endgroup$
    – D.W.
    Apr 22, 2019 at 20:56

2 Answers 2

3
+50
$\begingroup$

As that link explains, you have one variable per edge in the maximum matching, call it $x_i$ for the $i$th edge. If $x_i=0$, we'll choose the left endpoint of that edge to be in the vertex cover; if $x_i=1$, we'll add the right endpoint of that edge to the vertex cover.

Now, we need to make sure that all of the vertices are covered. Iterate over each edge $(u,w)$ that's not in the matching:

  • If $u$ is touched by the matching but $w$ is not touched by the matching, then the only way to achieve a valid vertex cover from this matching is to include $u$ in the vertex cover. So, we need to find the edge $(u,v)$ in the matching, then set the corresponding variable $x_i$ to 0 (to ensure $u$ is selected, not $v$).

  • If $u$ is not touched by the matching but $w$ is touched, then do the reverse of the above.

  • If neither of $u$ nor $w$ is touched by the matching -- this can't happen in a maximum matching (because you could add the edge $(u,w)$ and get a larger matching). So, you can ignore this case.

  • If both $u$ and $w$ are touched by the matching, then we need to ensure that either $u$ or $w$ is selected. This can be enforced with a 2-CNF clause. In particular, let $x_i$ be the variable for the edge that touches $u$, and let $x_j$ be the variable for the edge that touches $w$. If $u$ is the left endpoint for $x_i$ and $w$ is the right endpoint for $x_j$, we add the 2-CNF clause $\neg x_i \lor x_j$; this ensures that either $u$ or $w$ are selected (or possibly both).

So, combine all the 2-CNF clauses you get in this way, and you get a 2-CNF formula, i.e., a 2-SAT instance. Solving the 2-SAT instance tells you how to pick a set of vertices that will be a vertex cover. Once you have an assignment that satisfies the 2-SAT instance, that corresponds to a consistent way to choose vertices; and you can verify that this set of vertices forms a vertex cover.

$\endgroup$
3
  • $\begingroup$ We can't have two edges from the same vertex in the maximum matching. $\endgroup$ Apr 23, 2019 at 8:10
  • $\begingroup$ "you have one variable per edge" No,Blog says we have one variable per edge which is in the Maximum matching. $\endgroup$ Apr 23, 2019 at 8:17
  • 1
    $\begingroup$ @ManoharsinhRana, you're right. See updated answer. $\endgroup$
    – D.W.
    Apr 23, 2019 at 16:20
3
$\begingroup$

I don't understand the variables. I have an edge from maximum matching then I might have both the endpoints of that edge in the vertex cover. But this scheme does not allow this.

In bipartite graphs, the size of a maximum matching is also the size of the minimum vertex cover. Since every vertex cover must contain at least one vertex from each edge in the matching, it follows that it has to contain exactly one vertex from each edge in the matching.

$\endgroup$
1
  • 2
    $\begingroup$ I'm sure you can figure it out. $\endgroup$ Apr 22, 2019 at 3:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.