Multiple Knapsack Problem with Set of Admissible Balls We have $m$ bins and $n$ balls. 


Each bin $i=1,2,\ldots,m$ can contain at most two balls (not any two balls but two balls from some specific set), see 3.
Each ball $j=1,2,\ldots,n$ can be put into bin $i=1,2,\ldots,m$. 
For each bin $i=1,2,\ldots,m$, there is a collection of sets $S_i=\{X_1,X_2,\ldots,X_{k_i}\}$ for given $k_i$ ($k_i\geq0$ and $k_i\leq\binom{n}{2}$). Each $X_j\in S_i$ is a 2-cardinality set and it represents the set of two balls that can be put into bin $i$. We can only choose at most one set from $S_i$.


For example, for $m=2$ and $n=3$. Say we have $k_1=0$ and $k_2=2$ and $S_1=\emptyset$. $S_2=\{\{1,2\},\{2,3\}\}$. This means that:


Ball $1$, $2$ or $3$ can be each put into bin $1$ or bin $2$. This is always true (for all instances of the problem).
In bin $1$, we cannot put any set of two balls.
In bin $2$, we can put balls $1$ and $2$ or balls $2$ and $3$. 


We want to assign the maximum number of balls into the bins. Is this easy or hard? 

Since, we have the assumption that $|X_j|=2$, I was thinking that maybe we can solve it in polynomial-time. I am trying to prove that it is easy by reducing it to maximum flow.

A problem similar to this one but more general was posted here Assigning Balls to Bins with Constraints on Which Ball to Go to Which Bin?.
This is NP-hard by reduction from 3-dimensional matching (3DM): turn each triple $\{a, b, c\}$ into a valid pair $\{a, b\}$ of balls for bin $c$, and add a large number of balls that don't belong to any valid pairs (so that if they go in a bin, they must be the sole occupant). The optimal solution will then hold $k+m$ balls ($k$ bins with 2 balls each and $m-k$ bins with 1 ball each), where $k$ is the largest size of any 3DM for the original input.