1

I want to reduce the vertex cover problem to a specific decision problem. This decision problem is the following:

I have a nxn matrix A, a vector b in R^n, and a positive integer k. Does there exists a vector x in R^n with at most k non-zero entries such that A*x is greater than or equal to b?

I was thinking that A could be viewed as an adjacency matrix, but I'm not sure how to reduce the vertex cover problem to this problem.

Can anyone give me a hint or two on what I should do next?

EDIT**I originally thought about using dominating set problem, but after thinking through the problem a little more, I thought I should use vertex cover instead. (so question originally referred to dominating set)

cs_user2017
  • 127
  • 1
  • 2
  • 12
  • I think there would be a better chance for an easy reduction, if it where ILP. Which problem do you try to prove being NP-hart? If it is dominating set, then the reduction should be another way around. If it is LP, there are better NP-hart candidates as dominating set – ead Mar 19 '17 at 10:10
  • I was thinking about the problem a little more, and I thought that I could reduce vertex cover to this problem instead. – cs_user2017 Mar 20 '17 at 07:46

0 Answers0