### fack's blog

By fack, history, 5 weeks ago, ,

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

• -18

 » 5 weeks ago, # |   0 Auto comment: topic has been updated by fack (previous revision, new revision, compare).
•  » » 5 weeks ago, # ^ |   0 The best I could come up is O(2^n)
 » 5 weeks ago, # |   0 Note that for K = 2 this problem is equivalent to finding the number of vertex covers, which is #P-hard.
 » 5 weeks ago, # |   0 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.
 » 5 weeks ago, # |   +22 Heh, ongoing codechef again. And this is even not exactly correct reduction. Why dont they learn?..
•  » » 5 weeks ago, # ^ |   0 I guess my reduction is correct as I am able to get ac for N=20 cases
•  » » 5 weeks ago, # ^ |   0 Anyone willing to help in LCM constraints Please DM
•  » » » 5 weeks ago, # ^ |   0 Just Hints will work.
 » 5 weeks ago, # |   0 Auto comment: topic has been updated by fack (previous revision, new revision, compare).
 » 5 weeks ago, # |   0 Auto comment: topic has been updated by fack (previous revision, new revision, compare).
 » 5 weeks ago, # |   0 are koi to batado bhai intern start hone wali h batado.. 5 star ban jayege... O(2^n) me to ho gya.
•  » » 5 weeks ago, # ^ |   0 but 30 and 38 wale testcases ke liye nahi hora DM stardo approch
•  » » » 5 weeks ago, # ^ |   0 yaar ye recent action me upper kyo nahi aara? anyone?