Quote from: KingZee on January 14, 2019, 02:12:44 AM

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.