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.