PROBLEM LINKS
DIFFICULTY
HARD
EXPLANATION
The problem description can be simplified to this. We are given a graph G where each edge has an associated color. Each color c also has a capacity cap(c). Find the largest possible subset of edges M that does not contain a cycle. Additionally, for any color c the number of edges in M with associated color c must be at most cap(c).
Let M be any acyclic subset of edges satisfying the coloring constraints (call such sets feasible). The following subroutine will either find a feasible subset M’ with |M’| = |M| + 1 or else declare that M is a maximum feasible subset of edges. Given this method, one simply finds a maximum feasible subset by starting with M being the empty set and repeatedly calling the subroutine until it declares the current feasible subset of edges to be maximum. The subroutine is reminiscent of the bipartite matching algorithm.
Form an auxiliary bipartite graph H whose nodes correspond to edges of G. One side A consists of edges in M and the other side B consists of edges of G not in M. For any e in A and e’ in B, add a directed arc from e’ to e in H if M-e+e’ satisfies the color capacities and add a directed arc from e to e’ if M-e+e’ is acyclic. Let X be the subset of B where any e in X can be added to M without creating a cycle and let Y be the subset of B where any e in Y can be added without violating the color constraints. Find a * shortest * path from X to Y (perhaps of
length 0 if X and Y are disjoint).
Say this path P = b _ 0, a _ 0, b _ 1, …, a _ {l-1}, b _ l. Remove all a _ i from M and add all b _ i to M. Paying close enough attention to the definitions, one can see that the resulting set has one more element
than M and still is acyclic and satisfies the color constraints. For example, one can show that for 0 <= i < l that adding b _ {i+1} to M creates a cycle and that a _ i lies on this cycle. If b _ {i+1} did not
create a cycle then b _ {i+1} is in X, so a shorter X-Y path can be obtained by starting at b _ {i+1}, rather than b _ 0. Furthermore, since a _ i → b _ {i+1} is an arc then a _ i must lie on the cycle in M + {b _ i}. Similar reasoning shows that for 0 <= i < l that adding adding b _ i to M violates a color capacity and that a _ i is the same color as b _ i.
The point is, if we removed all a_i and added all b _ i for 0 <= i < l then the amount used of each color is the same as is used by M. Also, if we remove all a _ i and added all b _ {i+1} for 0 <= i < l then the connected components are the same as in M. Finally, since b _ l has a color that isn’t used to capacity and b _ 0 bridges two components, then we may remove all of a _ i, 0 <= i < l and add all of b _ i, 0 <= i <= l and the resulting set is feasible.
Now, say there is no X-Y path. The goal is to argue that M is maximum. For any subset of edges F, let a(F) be size of the largest subset of F that is acyclic. Similarly, let b(F) denote the size of the largest subset of F that satisfies the color constraints. If E denotes all edges, then for any subsets M and F of E where M is acyclic and satisfies the color constraints (but F can be any subset), then |M| <= a(F) + b(E-F). This is because M = |M intersect F| + |M - F| <= a(F) + b(E-F) since M intersect F is an acyclic subset of F and M-F is a subset of E-F satisfying the color constraints. We will find some subset U of E such that |M| >= a(U) + b(E-U) which proves |M| is maximum.
If X is empty then M must be maximum since it would then be a spanning tree of each of the connected components of G so clearly no larger subset of edges can be acyclic. So, assume X is not empty and let U denote all edges (represented as nodes in H) that can reach Y in H. Now, Y is contained in U and the sets X and U are disjoint (since there is no X-U path) . We will argue that |M intersect U| >= a(U), the proof of |M-U| >= b(E-U) proceeds in a similar spirit.
Suppose that |M intersect U| < a(U). Then there is some edge z in U - (M intersect U) such that (M intersect U) + {z} is acyclic. First, since z is in U-(M intersect U), then z cannot be in M. Furthermore, it must be that M + {z} is not acyclic since z is in U and M + {z} being acyclic would imply z is also in X, but U and X are disjoint. Now, since (M intersect U) + {z} is acyclic but M + {z} does not, then there is some edge y in M-U such that M-{y}+{z} is acyclic. This, in turn, implies there is an arc from y to z by construction of H. Since y is not in U and z is in U, this contradicts the fact that U contains all nodes that have a path to X.
There is a nice set of notes from an optimization course recently
taught that discusses this algorithm in a more general setting.
http://www.cs.illinois.edu/class/sp10/cs598csc/Lectures/Lecture17.pdf
This problem is listed as an example on the second page.