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 = (US, VS, ES) of
G satisfing the following requirements:
1. For each vertex
u in
US, the number of edges attached to
u must be less than or equal to
c(u).
2. For each vertex
v in
VS, 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
VS 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.
