Tag Archives: K-Vertex Cover

Internal Macro Data Compression

I’m finally back from my trip.  Apologies for the delay.

The problem: Internal Macro Data Compression.  This is problem SR23 in the appendix.

The description: Given an alphabet Σ, a string s in Σ*, a “pointer cost” h and a bound B, can we find a string C in the alphabet of Σ augmented with at most s “pointer characters” pi such that:

  • |C|+ (h-1)* (# of pointer characters in C) is ≤ B, and
  • We can replace pointer characters with substrings of C to regain s?

Example: This is similar to the last macro compression problem, but instead of having 2 strings C and D, C serves both purposes.  In our example from last time, we had s = “ABCDEFABCGABCDEF”, and came up with C= “pqpGpq” and D= “ABCDEF”.  The difference here is that there is no D string, we have to do it all in C.  We can do that by letting C = “ABCDEFqpGpq”.  Now if we let p=”ABC” (or, “the substring of C of length 3 starting at position 1” and q = “DEF” (or, “the substring of C of length 3 starting at position 4”, we get a string of cost 11+3h that gives us back s if we replace all pointers with the strings they represent.

Reduction: The paper by Storer that we’ve been using for the last few problems also has this reduction.  I think this is his “CPM” problem.  He uses the “K-Vertex Cover” problem, in the case where K=1.   Recall in that case we are looking for a set of edges E’ such that each edge in E shares a vertex with an edge in E’. We start with a graph, which is an instance of this problem.  The alphabet we build will have:

  • A special symbol $
  • One symbol for each vertex and edge in G

For each edge ei =  (vj, vk), define the substring Ei = $vj$vk$

Our s = the concatenation of eiEi for all edges i (So the symbol for the edge followed by the substring of the edge).  B = J + |S| – |E|.

The idea (and I’ll admit I have a hard time following this paper) is that if G has a 1-VC, then we have J edges that form a set E’ such that each edge in E is adjacent to something in E’.  This means that we can overlap those edges and make pointers out of the Ei strings to save enough characters.

Difficulty: 9.  I’m sure this can be explained better, but I really have a hard time following it.

K-Vertex Cover

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.