If I find an NP Hard problem that is equivalent to my problem with an additional

Question

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 U and a family S of subsets of U, select k sets from 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?

Explanation / Answer

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.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.