These next two problems are from an “unpublished manuscript” that I can’t find. Assuming I did them correctly, I think they are also good problems for students to work on.
The problem: Multiple Copy File Allocation. This is problem SR6 in the appendix.
The description: Given a graph G=(V,E), where each vertex v ∈ V has a “usage” u(v), and a “storage cost” s(v) (both positive integers), and a positive integer K. Can we find a subset V’ of V where for each v ∈ V we define d(v) to be the length of the shortest path from v to some member of V’, that the sum of:
- The s(v) values for all vertices in V’ plus
- The d(v)*u(v) values for all vertices not in V’ is ≤ K?
Example: The idea is that each vertex in V’ pays its s(v) cost, and each vertex not in V’ pays its u(v) cost for each edge is has to go through to get to something in V’. Here’s a simple example:
Each node lists its s value first and u value second. If we take just the “1,10” node into V’, our total cost is:
- 1 from the “1,10” node (its s value)
- 2 + 3 + 4 from each of its neighbors (their u values * a distance of 1)
- 2 from the “90,1” vertex. (u cost of 1, times a distance of 2 edges from the vertex in V’)
..for a total of 12. I think that’s minimal.
Reduction: G&J say to use Vertex Cover, and mention that we can make all s values equal to each other and all u values equal to each other. The phrasing implies that we shouldn’t make the s value and u values the same altogether, which is a good hint.
So we start with out VC instance: a graph G=(V,E) and an integer K. We will use the same graph. Let s = the s(v) for each vertex = |V|. Let u = the u(v) for each vertex = (The smallest integer larger than |V|/2).
Set K’ = K*s + (|V|-K)* u. Hopefully it’s clear how this number will allow a solution to the VC problem take that cover and create a solution to the MCFA problem.
If we have a MFCA solution, first notice that any vertices that are 2 (or more) edges away from something in V’ are contributing 2*u to the total cost. Since 2*u > s, we can add a vertex to V’ at a distance 1 away from these distant vertices and keep our total cost ≤ K’. This means we can transform any MCFA solution into one that is also a solution but where V’ is a cover of V.
Also notice that even after making these changes that if we were to have K+1 (or more) vertices in V’, our total cost would be (K+1)*s + (|V|-K-1)* u. This is more than K’ (it adds an extra s of cost |V| and removes a u of cost |V|/2+1).
So, we can construct a MCFA solution where there are K or less vertices in V’ that form a cover. This gives us a solution to the VC instance.
Difficulty: 5. It takes a little playing around with the algebra to get the correct values, but the idea that we can make the s and u values the same for all vertices is helpful, and gives a clear path to how you’d reduce this problem from VC.