cacophonix's blog

Vertex cover in Bipartite Graph
By cacophonix, 12 years ago, In English

I have a Bipartite Graph. I want the indeces of vertices that covers all the vertices. Cant't get it. any help .....

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
12 years ago, # |
  Vote: I like it +4 Vote: I do not like it

I think I can prove this problem is NP-complete. So, we cannot find a polynomial time algorithm for it.

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What are the techniques to prove a problem's np-completness?

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +9 Vote: I do not like it

      I have a lot of negative votes. Nevertheless, your question is about marking vertices that cover the rest of vertices, while konig's theorem is about marking vertices that cover edges. Please, make clear if you want to cover vertices or edges. In the first case, the problem is NP-complete, as I said, even if you vote negatively.

      → Reply
»
12 years ago, # |
  Vote: I like it +7 Vote: I do not like it

[König's theorem] (http://en.wikipedia.org/wiki/K%C3%B6nig%27s_theorem_(graph_theory))

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    I have a lot of negative votes. Nevertheless, your question is about marking vertices that cover the rest of vertices, while konig's theorem is about marking vertices that cover edges. Please, make clear if you want to cover vertices or edges. In the first case, the problem is NP-complete, as I said, even if you vote negatively.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +14 Vote: I do not like it

      Ignore negative votes. There are just silly schoolkids that minus the first comments of every topic.

      → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i want to cover the vertices not edges.

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        So essentially you are talking about Dominating Set. This problem is NP complete if you want to find dominating set of minimum cardinality even for bipartite graphs but you have some approximation algorithm to solve this problem. One can be found here.

        → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        A very good book for NP-completeness is "Garey and Johnson, Computers and Intractability: a guide to the theory of NP-completeness, 1979.".

        Your problem about covering vertices (in an arbirary graph, not necessarily bipartite) is called "The MINIMUM DOMINATING SET problem" (http://en.wikipedia.org/wiki/Dominating_set). Nevertheless, one of the tipical reductions from SAT (satisfiability problem) already produces bipartite graphs. So, this problem is NP-hard even for bipartite graphs. The decisional version of MINIMUM DOMINATING SET, called DOMINATING SET, receives a graph G and a natural number k as input, and questions whether one can choose k vertices of G such that any other vertex is covered by the chosen ones.

        The reduction works as follows. Consider an input of the SAT problem, i.e. a logical propositional formula consisting of a conjunction of disjunctions of literals (for example ((x1 or not(x2) or x3) and (not(x1) or x2 or x3) and ...), that is, a formula of the form (c1 and c2 and c3 and ... and cm), where each ci is a disjunction of literals. Let x1,x2,...,xn be the variables involved in the formula. Note that each literal is either of the form xi, or not(x1). Recall that the question in SAT is whether the formula is satisfiable, i.e. if there is a true/false assignment to the variables such that the formula evaluates to true. We know that the SAT problem is NP-hard, and hence, we are not able to solve it in polynomial time. In order to prove that DOMINATING SET is also NP-hard, we need to polynomially transform any input of SAT (a formula F) into an input of DOMINATING SET (a graph G and a number k) by preserving the answer (F is satisfiable if and only if there is a dominating set of size k in G). This suffices to argue that we are not able to find a polynomial time algorithm for DOMINATING SET: if we could do that, then our polynomial transformation from SAT to DOMINATING SET would give us a polynomial time for SAT, a contradiction. We construct G and k from F as follows: k is just n. For each variable xi we have three vertices vxi, vnot(xi), vxi' and there are edjes between every two of those three vertices. For each disjunction ci we have a vertex vci. For each literal xj inside ci, there is an edge between vxj and vci. For each literal not(xj) in ci, there is an edge between vnot(xj) and vci. There are no more edges.

        The above reduction accomplishes "F is satisfiable iff there is a dominating set of size k in G":

        =>) Suppose there is an assignment A:variables->{true,false} that satisfies F. We construct a dominating set S of size k=n as follows. For each variable xi, if A(xi)=true, then the vertex vxi is in S. Otherwise, if A(xi)=false, then the vertex vnot(xi) is in S. There are no more vertices in S. This set is dominating because each disjunction ci is satisfied, and hence, each vci is connected to a vertex in S. Of course, all vxi,xnot(xi),vxi' are connected to a vertex in S, since either vxi or vnot(xi) is in S.

        <=) Suppose that we have a dominating set S of size k=n in G. First of all, note that each vxi' is either in S, or one of the corresponding vxi or vnot(xi) is in S, since vxi' must be dominated. This implies that for each i, at least one of vxi,vnot(xi),vxi' is in S. But it should be exactly one, since i ranges from 1 to n, and the number of elements in S is k=n. Thus, no vci is in S. Moreover, we can assume that no vxi' is in S: otherwise, by removing vxi' from S and adding any of vxi or vnot(xi), we still have a dominating set. In conclusion, for each i from 1 to n, either vxi or vnot(xi) is in S, only one of both is in S, and there are no other kind of vertices in S. At this point, we define the assignment A:variables->{true,false} as A(xi)=true if vxi is in S, and as A(xi)=false if vnot(xi) is in S. The assignment satisfies all cj because each vcj is dominated by S.

        Note that the transformation produces a bipartite graph.

        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          For each variable xi we have three vertices vxi, vnot(xi), vxi' and there are edjes between every two of those three vertices

          A graph that has K3 subgraph seems not to be bipartite.

          → Reply
          • »
            »
            »
            »
            »
            »
            12 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Ups, you are right, for bipartite graphs the reduction is not correct, I am very sorry. Perhaps we can solve the mistake with a slight change: we define k=2n (instead of k=n), for each variable xi we add 5 vertices vxi, vnot(xi), vxi', vxi'', vxi''', and edges (vxi,vxi'), (vxi',vxi''), (vxi'',vxi'''), (vxi''',vnot(xi)). For the conjunctions of literals we proceed as before: for each ci, we have a vertex vci, and for each xj in ci we have an edge (vci,vxj), and for each not(xj) in ci we have an edge (vci,vnot(xj). Now, I think the generated graph is bipartite, and the proof that the transformation preserves the answer between the both problems works more or less as before. It is not difficult to see that, among the k=2n selected vertides, two of them should be from each set {vxi, vnot(xi), vxi', vxi'', vxi'''}, but also that one of {vxi,vnot(xi)} is not chosen (otherwise, if the chosen vertices are vxi and vnot(xi), then vxi'' is not covered). Moreover, as before, any selection can be transformed into one where either vxi or vnot(xi) is chosen. Thus, similarly to before, a 2k covering corresponds to an assignment.

            → Reply
          • »
            »
            »
            »
            »
            »
            12 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Sorry again, something does not work in my last comment. For bipartite graphs we could use the following construction: we define k=2n (instead of k=n), for each variable xi we add 6 vertices vxi, vnot(xi), vxi1, vxi2, vxi3, vxi4 and edges (vxi,vxi1), (vxi1,vxi2), (vxi2,vxi3), (vxi3,vnot(xi)), (vxi,vxi4), (vxi4,vnot(xi)). For the conjunctions of literals we proceed as before: for each ci, we have a vertex vci, and for each xj in ci we have an edge (vci,vxj), and for each not(xj) in ci we have an edge (vci,vnot(xj). Now, I think the generated graph is bipartite, and the proof that the transformation preserves the answer between the both problems works more or less as before. It is not difficult to see that, among the k=2n selected vertides, two of them should be from each set {vxi, vnot(xi), vxi1, vxi2, vxi3, vxi4}, but also that one of {vxi,vnot(xi)} is not chosen (otherwise, if the chosen vertices are vxi and vnot(xi), then vxi2 is not covered). Moreover, as before, any selection can be transformed into one where either vxi or vnot(xi) is chosen. Thus, similarly to before, a 2n covering corresponds to an assignment.

            → Reply