Overall, one would naturally think that with n different nodes, and for x(1) for example representing node 1, it would be like:
x(1)+x(2)+x(3)…+x(n) <= k
This would mean that for every possible solution of k-vertex-cover, the maximum amount of literals being true has to be lower or equal to k.
So much for understanding.
The problem however is, that a logic formula is needed for description of the constraint and logic doesn’t have addition or comparison.
My only idea up to now is that I could use the logic formula of Adders and Comparators to simulate an addition and a comparison in logic, but that only works out for some solutions. I need a general logic formula.
Does anyone have another idea or maybe a simpler method which could be used in general?
The reduction has to be done in polynomial time.