I'm trying to find an algorithm (sub exponential) to answer the following question (informal): given a (finite) set of distinct books of different (positive integer) sizes and a (finite) set of bags of different (positive integer) sizes, such that each book is allowed to enter only some of the bags, can all the books be arranged into the bags? (the actual solution is not important, rather its existence).
Or a little more formal: Let $G$ be a bipartite graph with vertex parts $P_1$ (books) and $P_2$ (bags) (all edges are between $P_1$ and $P_2$). Let $w$ be a positive integer weight function on the edges (books size) such that if $e_1$ and $e_2$ are incident with the same vertex in $P_1$ then $w(e_1)=w(e_2)$, and let $c$ be a positive integer function on the vertices of $P_2$ (bag capacity).
Define the function $f_G(v)$ for every vertex $v$ in $G$ to be the sum of weights of the edges incident with it; $\displaystyle f_G(v) = \sum_{e=(v',v)}w(e)$.
I'm looking for an algorithm to answer the question: does $G$ have a subgraph $H$ in which the degree of every vertex in $P_1$ is $1$ and for every vertex $v$ in $P_2$ we have $f_H(v)\leq c(v)$?
Thank you!
Adding an answer following @Irvan's comment above:
The bin packing problem ("Given $n$ items of sizes $d_1,...d_n$ and $m$ bins with capacity $c_1,...,c_m$ store all the items using the smallest number of bins.") could be reduced to this problem in polynomial time.
If we had the algorithms in the question, we could map the items to books and bins to bags, allowing each book to enter every bag. And the question of smallest number of bins is answered by running the algorithm a maximum of $m$ times (sorting the bins in decreasing order and adding a bin at every run).
Thus, the problem in question is NP-hard.