1
$\begingroup$

How to solve this problem?

A vertex cover of a graph 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.

Consider a set of all minimum vertex covers of a given bipartite graph. Your task is to divide all vertices of the graph into three sets. A vertex is in set N (“Never”) if there is no minimum vertex cover containing this vertex. A vertex is in set A (“Always”) if it is a part of every minimum vertex cover of the given graph. If a vertex belongs neither to N nor to A, it goes to the set E (“Exists”).

$\endgroup$
  • 3
    $\begingroup$ What have you tried? Where did you get stuck? $\endgroup$ – Yuval Filmus Jan 29 at 4:52
  • $\begingroup$ I thought that highest degree vertex is must.If two vertecies have same degree than both are eligilble for vertex cover. $\endgroup$ – Manoharsinh Rana Jan 29 at 6:58
  • $\begingroup$ My answer refers to the question "how to find a minimum vertex cover in a bipartite graph". If your question is different, please update the body of your question to include the actual question. Links don't count – your question has to be self-contained. $\endgroup$ – Yuval Filmus Jan 29 at 7:03
  • $\begingroup$ Good questions are self-contained. This means you should not expect someone to access a link in order to comprehend your question. (And what happens if the relevant site or page goes offline in the future?) Please include any information pertinent to the question in itself. Thank you. $\endgroup$ – dkaeae Jan 29 at 8:17
  • $\begingroup$ I will take care of that from next time. $\endgroup$ – Manoharsinh Rana Jan 29 at 10:06
2
$\begingroup$

The following idea comes from a Chinese blog.

Find a maximum matching $M$ ($2m$ vertices and $m$ edges) firstly. For convenience, for a vertex $v$, we denote by $M(v)$ the vertex that is matched with $v$ in $M$, and denote by $N(v)$ the set of neighbors of $v$.

We have the following observations:

  1. All vertices not in $M$ must belong to $\mathrm{Never}$.

    Proof. Suppose a minimum vertex cover contains a vertex $v$ not in $M$, to cover the $m$ edges in $M$, the vertex cover must also contains another $m$ vertices, so the size of the vertex cover is at least $m+1$, which contradicts to Kőnig's theorem.

  2. If a vertex $v$ in $M$ belongs to $\mathrm{Always}$, then $M(v)$ must belong to $\mathrm{Never}$.

    Proof. Suppose a minimum vertex cover contains both $v$ and $M(v)$, to cover the rest $m-1$ edges in $M$, the vertex cover must also contains another $m-1$ vertices, so the size of the vertex cover is at least $m+1$, which contradicts to Kőnig's theorem.

  3. If a vertex $v$ belongs to $\mathrm{Never}$, then $N(v)$ must be a subset of $\mathrm{Always}$.

These observations lead us to the following algorithm:

A = A[0] = empty set
N = N[0] = all the vertices not in M
i = 0
while True:
    i = i + 1
    A[i] = empty set
    for each vertex v in N[i - 1]:
        temp = N(v) \ A
        A[i] = union(A[i], temp)
        A = union(A, temp)

    if A[i] is empty:
        break

    for each vertex v in A[i]:
        add M(v) into N[i]
        add M(v) into N

After the execution of this algorithm, all vertices in A belong to $\mathrm{Always}$ and all vertices in N belong to $\mathrm{Never}$. For those rest vertices, we partition them into two sides by intersecting respectively with $L$ and $R$, where $L$ and $R$ are respectively the two sides of the bipartite graph. We can see either side along with the vertices in A forms a minimum vertex cover, so these vertices belong to $\mathrm{Exist}$.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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