Quote from: theymos on January 14, 2019, 07:12:44 AM

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, v3)
(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.

Two more questions :

M (number of V vertices) is not given right? We have the number of u vertices, their capacity, and T the constant, and our solution is finding the vectors (u,v) that satisfy the requirements with the maximum number possible of v vertices?

Typo on your end in the 2nd optimal solution? I figure you meant either v1 or v3 for one of those vectors?

----------

Quote from: DabLjat on January 14, 2019, 12:11:43 PM

And where the user chimk?

Quote from: DabLjat on January 14, 2019, 12:21:20 PM

Yes, true, and where the user Veleor?

Can you stop?