fack's blog

weight assignment on vertices in weighted graph
By fack, history, 4 years ago, In English

Suppose I have a weighted graph with equal positive weight (let it be K) on each edge. Now I want to count the number of ways to assign weights to vertices SUCH THAT if there is an edge between X and Y then max(W[X], W[Y])=K where W[X] means assigned weight to vertex X.

can someone solve it in better than O(2^n).

Anyone could help me with LCM constrainsts. Please DM

Thanks

  • Vote: I like it
  • -18
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Note that for K = 2 this problem is equivalent to finding the number of vertex covers, which is #P-hard.

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

Even the special case of this problem $$$K=2$$$ (equivalent to counting vertex covers) is #P-complete, because counting solutions to 2-SAT is also #P-complete, and a vertex cover can easily be represented with a 2-SAT formula.

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

Heh, ongoing codechef again. And this is even not exactly correct reduction. Why dont they learn?..

→ Reply