This week we do a variant of Vertex Cover that I don’t think I’ve seen before, but we’ll use for the next problem.

After this week, I’m going to be traveling for three weeks. So the next post will be the week of August 14.

**The problem: **K-Vertex Cover. This problem is not in the appendix.

**The description: **Given a graph G=(V,E), and integers K and J. Does G contain a set of J or less paths, where each path contains K or less edges, and each edge in E is incident on at least one of these paths?

**Example: **Here is a graph:

A K-Vertex Cover where K = 0 is just a regular Vertex Cover:

With K=1, this is “Find a subset E’ of E where each edge in E shares an endpoint with something in E'”:

With K=2, we are finding paths of 2 (or less) edges where each edge in E is adjacent to something in a path (I colored each path a different color to make them easier to tell apart):

Notice that K is set as a parameter of the problem.

**Reduction: **The report by Storer that had the previous reduction (and which will have the next one) introduces this problem. The reduction is from Vertex Cover. I guess we could just take the initial VC instance, set K=0, and be done, but I like this construction because it shows how to make 1-VC, 2-VC, and so on NP-Complete. (In other words, if K is fixed outside of the problem, you need this reduction). Interestingly, a |V|-vertex cover is trivial (it’s asking if the graph has J or less connected components).

Given our VC instance G=(V,E), with bound J (instead of K, just because K here means something different and the J for our problem will be the same J for the VC instance), build a new graph G’=(V’, E’):

V’ starts with V, and adds two new vertices for each K and each J (so 2*K*J new vertices) labeled x_{1,1} through x_{j,k} and y_{1,1} through y_{j,k}. Notice that since J and K should be ≤ |V| (or the answer is trivial), this only adds a polynomial number of vertices.

E’ starts with E, adds an edge from each vertex in V to all x vertices labeled x_{j,1}, an edge from each x_{i,j} to its corresponding y_{i,j}, and a vertex from x_{i,j} to the next x_{i,k+1}

The idea is that since each x vertex needs to connect to a y vertex, we will need to include a path that goes through each x vertex in our k-cover. Since there are J paths of length K, and each vertex in v connected to all x_{j,1}, what happens is that each of the J vertices chosen in the VC of G “chooses” a different path of x vertices. So we can cover all of the vertices in G’ with J paths if and only if we can cover all of the vertices in G with J vertices.

**Difficulty: **5. This is a pretty cool reduction. I like the idea of adding K *J copies of the vertices, because while you can do that for a graph problem (since K and J need to be < |V| realistically), you can’t do that for other kinds of problems. For example, trying to create an element for each value from 1 to K in the Sum of Subsets problem won’t give you a polynomial reduction.

How did you get that report from Storer? I can’t find it online or at my university’s library…

I asked our library people to make an interlibrary loan request. I guess they asked the people at Princeton. They’ve really done a great job for me tracking down all these obscure papers..

Oh I’ve done that for books but never thought of it for papers. Thank you!