I might help out and spend a day thinking about it but the explanation from the graph is a bit confusing.

Can you dumb it down even further? Just a short description of what are the inputs exactly, and how do you want the output. Better if it's just an example with 5 users or something.

**G = (U, V, E)** is a bipartite graph with edges from the left side,

**U**, to the right side,

**V**. There are

*N* vertices in

**U** and

*M* vertices in

**V**. A "capacity" function

*c*: U -> Z is defined for every vertex in

**U**. A constant integer "target value"

*T* exists.

Candidate solutions are subgraphs

**S = (U**_{S}, V_{S}, E_{S}) of

**G** satisfing the following requirements:

1. For each vertex

*u* in

**U**_{S}, the number of edges attached to

*u* must be less than or equal to

*c(u)*.

2. For each vertex

*v* in

**V**_{S}, the number of edges attached to

*v* must be greater than or equal to

*T*.

Find an

**S** such that the number of vertices in

**V**_{S} is maximal.

Example:

Note that this graph is depicted as directed, but that doesn't actually matter.

Note:

- To satisfy requirement #1, you must exclude at least two of (u1, v1) or (u1, v3) or (u1, v4).

- To satisfy requirement #1, you must exclude at least one of (u2, v1) or (u2, v2).

- To satisfy requirement #1, you must exclude at least one of (u3, v1), (u3, v2) or (u3, v3)

- To satisfy requirement #2, you must exclude at least v4 (since it cannot possibly get T=2 edges), and possibly more depending on the rest of

**S**.

In a very naïve greedy algorithm, you might just fill up vertices on the right from top to bottom until you can't do anything else. That'd give a candidate solution of:

(u1, v1)

(u2, v1)

This is a valid candidate solution, but it's non-optimal because it includes only 1 vertex in

**V** whereas 2 are possible. In order to achieve an optimal solution, you need some backtracking, at least. In this case there are two equally-good optimal solutions:

(u1, v3)

(u3, v3)

(u2, v2)

(u3, v2)

or:

(u1, v1)

(u3, v1)

(u2, v2)

(u3, v2)

It becomes more complicated as the graph gets bigger.

Writing it down in this way reminds me a lot of the stable marriage problem, which gives me hope that it can be solved exactly.