2
$\begingroup$

If I find an NP Hard problem that is equivalent to my problem with an additional constraint or bound, can I still prove that my problem is NP Hard?

Generally, this is probably not the case. For example, the NP Hard TSP is just a further constrained version of the shortest path problem.

Specifically, I have the problem:

Given a universe $\mathcal{U}$ and a family $\mathcal{S}$ of subsets of $\mathcal{U}$, select $k$ sets from $\mathcal{S}$ such that the sum of the number of repeated times that each element is covered is maximized. Number of repeats are defined as one less than the number of instances.

If the number of repeated times for each element has an upper bound at 1, this is equivalent the densest k-subgraph problem (edges are elements and nodes are sets),

Given a graph $G$ and an integer $k$, find a subgraph of $G$ on $k$ nodes with maximum number of edges.

Since the densest k-subgraph problem is strongly NP Hard, can I prove that my problem is also NP Hard?

$\endgroup$
2
$\begingroup$

Hint: An instance of densest $k$-subgraph can be viewed as an instance of your problem, in which sets are vertices and elements are edges.

More generally, to prove that a problem P is NP-hard given that a (seemingly) related problem Q is NP-hard, you need to come up with a polytime reduction from Q to P. If Q is strongly related to P, such a reduction could be easy to find.

$\endgroup$
  • $\begingroup$ I see. For some reason I thought it was the other way around, that there should be a polytime reduction from P to Q. Thanks $\endgroup$ – bravetang8 Jan 18 '15 at 22:41
  • $\begingroup$ @bravetang8 I think in this post, you can solve your concern, I should actually comment but I do not have 50 reputation. This is the link and I hope it solves your concern. cs.stackexchange.com/questions/37149/… $\endgroup$ – RandomStudent Jan 19 '15 at 0:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.