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 x1,1 through xj,k and y1,1 through yj,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 xj,1, an edge from each xi,j to its corresponding yi,j, and a vertex from xi,j to the next xi,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 xj,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.