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?
