Is finding a subset with exact cut with other given subsets NP-hard?

Question

I am trying to figure out whether the following problem is NP-hard:

Given  G_1,..,G_n subsets of {1..m}
       c_1,..,c_n non-negative integers in {0..m}
Find   T subset of {1..m}
S.T.   for all i=1..n, T intersects G_i in exactly c_i elements 

I tried to find reductions to NP problems such as coloring, or P problems such as matching, but on both cases could think of exponential conversion algorithm (i.e. one that takes into account all subsets of G_i of size c_i), which doesn't help me much :(

A side note: would any restrictions on the parameters make this problem much easier?
For instance, would m<< n make a computational difference (we would still be looking for an algorithm that is polynomial in m)? What if we knew that some of the constants c_i were zero?

Would appreciate any insight :)

Answer 1

This is NP-Complete problem, and is a generalization of Hitting Set Problem. Proof of NP-Completeness follows.

The problem is in NP (trivial - given a solution T, it is easy to check the intersection with each of Gi, and verify if its size is Ci).

It is also NP-Complete, assuming you are looking for minimal such T, with reduction from Exact Hitting Set Problem:

Where the decision problem of exact hitting set is:

Given a universe of elements U, subsets S1,...,Sk, and a number m - is there a subset S of U of size at most m that contains exactly one element from each Si?

Given instance of hitting-set problem (S1,S2,...Sk,d) - reduce it to this problem with Gi=Si, ci = 1, if the minimal solution of this problem is of size d, there is also a solution to exact hitting set of size d (and vise versa).