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, 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?
----------
And where the user chimk?
Yes, true, and where the user Veleor?
Can you stop?
