Containment in sets I have a collection of items, each of which belongs in exactly three sets.  Each set contains exactly $m$ items.  Given numbers $x_2, x_3$, how can I choose $k$ sets such that $x_2$ of the items are contained in two sets and $x_3$ of the items are contained in three sets?  Also, when is it possible to do this?
Alternatively, I have a bipartite graph.  Each vertex on the left has degree $m$, and each vertex on the right has degree $3$.  How can I mark $k$ vertices on the left such that $x_2$ vertices are adjacent to $2$ marked vertices and $x_3$ vertices are adjacent to $3$ marked vertices?
Alternatively, how might I generate an $n$-vertex graph that contains $k$ edges, $x_3$ triangles, and $x_2$ open triads?
Thanks!
 A: Partial answer: If you allow even two different sizes $m_1$ and $m_2$ of the sets, then whether a solution exists cannot be decided in polynomial time unless P=NP.
I will prove this by Turing reduction from 3CNF-SAT.
The input is a 3CNF formula. We can assume without loss of generality that every variable appears as many times as a positive atom as it appears as a negative atom; otherwise add some clauses of the form $(A\lor \neg A \lor \neg A)$ or $(A\lor A\lor \neg A)$ until things balance. This increases the size of the the formula at most by a factor of 4.
Let $n$ be the number of clauses in the balanced 3CNF, and let $p$, $q$, and $r$ be the three first primes larger than $3n$. Thanks to Bertrand's postulate neither prime is larger than $24n$.
We're going to construct a family of $n+1$ instances of your problem such that the 3CNF is satisfiable exactly if one of the instances have a solution. These instances differ only in the value of $x_2$. They have the same set of $np+3nq+nr < 120n^2$ "items" and $6n$ "sets" of size $m_1=p+2q$ or $m_2=q+r$.
The $np+3nq+nr$ items will be assigned in "groups" of size $p$, $q$ or $r$, such that every item in each group is in the same sets. Then, when we know now many items are covered by a certain number of sets, the Chinese Remainder Theorem allows us to know how many groups of each kind they are.
There will be $3n$ "atom sets", each corresponding to an occurrence of an atom in the CNF. Intuitively, the atom set will be chosen if the atom is false.
Each clause in the CNF will be represented as a $p$-group, which is connected to the atom sets in the clause. We're going to require that the number of chosen sets covering the $p$-group is different from 3, which corresponds to the clause being true.
The we need to add something that guarantees that the different atom sets for each variable are chosen or not-chosen in a consistent way. Arrange the atom sets for each variable in a circle such that positive occurrences alternate with negative ones. For each pair of neighboring sets, add a $q$-group whose items are in the two atom sets. We're going to require that each $q$ group is covered by exactly one of the atom sets.
The $q$-group is only connected to two atom sets, so in order to give it the right degree we also connect it to a "helper" set, which we will make sure is always chosen. The helper set will also connect to an $r$-group, with three helper sets sharing each $r$-group. (This is always possible because there are $3n$ helper sets, so there will be $n$ $r$-groups). We will require that each $r$ group is covered by exactly three chosen sets. That forces all of the helper sets to be chosen, so we can require that each $q$-group is covered by exactly 2 chosen sets.
This describes all of the items. The only thing we don't know is how many of the $p$ groups will have 2 chosen sets (rather than 0 or 1), so we need to construct one instance of the problem for each $i\in\{0,1,2,\ldots, n\}$. This instance will have
$$ x_2 = 3nq + ip \qquad x_3 = nr \qquad k = 3n/2 + 3n$$
If one of these instances have a solution, it will correspond to a satisfying truth assignment for the 3CNF. Conversely, if we can satisfy the 3CNF we can also solve the corresponding problem instance.
Each of the problem instances has a size that is polynomial in the size of the 3CNF, and there are polynomially many of them. So if we had a polynomial solver for your problem (extended to allow to different $m$s), we could use that to decide 3CNF-SAT in polynomial time.
