
Recent Posts
 Hitting String April 26, 2017
 Bounded Post Correspondence Problem April 19, 2017
 Shortest Common Superstring April 12, 2017
 Shortest Common Supersequence April 7, 2017
 Longest Common Subsequence March 29, 2017
Recent Comments
Archives
 April 2017
 March 2017
 February 2017
 January 2017
 December 2016
 November 2016
 October 2016
 September 2016
 August 2016
 July 2016
 June 2016
 May 2016
 April 2016
 March 2016
 February 2016
 January 2016
 December 2015
 November 2015
 October 2015
 September 2015
 August 2015
 July 2015
 June 2015
 May 2015
 April 2015
 March 2015
 February 2015
 January 2015
 December 2014
 November 2014
 October 2014
 September 2014
 August 2014
 July 2014
 June 2014
Categories
Meta
Category Archives: Core Problems
Protected: Exact Cover By 4Sets
Enter your password to view comments.
Posted in Core Problems
Tagged Difficulty 5, reductions, uncited reduction, X3C, X4C
Hamiltonian Path
Before I start doing my own problems where G&J don’t give proofs, here’s a really simple extension of Hamiltonian Circuit that will be useful.
The problem: Hamiltonian Path
The description: Given a graph G=(V,E), where V = N. Can I create an ordering <v_{1}, v_{2}…v_{n}>of the vertices where an edge exists between each (v_{i}, v_{i+1}) in the sequence?
(This is the Hamiltonian Circuit problem without the restriction that I return to the start)
EDIT 4/24/15. My original reduction doesn’t work. I’ve left it below. Thanks to Fernando Berzal for pointing it out to me. I’ve added his answer, which looks correct.
In all honesty, the best part about being wrong is that it means people actually read these things!
The new Reduction: From HC. Given a graph G =(V,E), an instance of HC, pick any vertex v.
We’re going to build a graph G’ =(V’, E’)
V’ = All of the vertices in V, plus a new vertex v’ (which is a “copy” of v)
E’ = All of the edges in E, plus an edge (v’, w) if there was an edge (v,w) in E.
So, G’ is G, with one vertex (v) “duplicated” as v’. v’ has edges to all of the places v has.
We want to see if there’s an HP from v to v’.
If G’ has an HP from v to v’, then the last edge in the path goes from some vertex u to v’. If we replace that edge with the edge (u,v) we get a HC in G.
If G has an HC, then we can follow that cycle starting from v. Instead of the last edge coming back to v, follow it to v’. This will give us a HP in G’
My reduction that doesn’t work: From HC. Given a graph G_{HC}, an instance of HC, we build G_{HP} to be the exact same graph with 2 vertices added v_{start} and v_{end}. We add two edges, one from v_{start} to some vertex in G_{HC}, and one from v_{end} to the same vertex in G_{HC}. The idea is that a Hamiltonian path in this graph would start at v_{start}, travel through the HC in the given graph (if it exists), and end at v_{end}.
This doesn’t work because if the two new vertices both connect to the same vertex then we hit it twice in our HP, which breaks the rules.
Difficulty: 2. This is a good “simple reduction” for students to work on. I don’t use it because it’s just a variant on the same problem, and I like to drive home how reductions tie very differentlooking problems together. But I do like how it’s simple, but does make you make some changes to the original problem.
(I think that I’m going to upgrade this difficulty to 4 now, since I can see a lot of students making the same mistake I did)
Partition
First, an administrative note. I wanted to call this site “Annotated NPComplete Problems”, because the idea is that I’m going through the Garey&Johnson book and adding notes to each problem talking about how to do the reduction and how applicable it is for student assignments. But that name is sort of taken already, and I don’t want to step on any toes or cause any confusion. So I figured that I’d change the title now, before anyone finds out about the site.
And as I’ve been writing, these notes feel more like “discussions” than “short annotations” anyway, so I think this is a better title.
This is the last of the “core six” problems in the G&J book, as defined in Chapter 3. There are several other problems presented in that chapter, with proofs, but since the point of this exercise is to get to the problems without proofs, I’m going to skip over them, and come back to them only if I need to (because they’re the basis for a future reduction, for example).
The problem: Partition (PART)
The definition: Given a set of integers A, can I fid a subset A’⊆A such that the sum of all of the elements in A’ is exactly half the sum of all of the elements in A?
(Alternately, given a set of integers A, can I split all of the elements of A into two subsets B and C, such that the sum of all of the elements in B is equal to the sum of all of the elements in C?)
(Alternately (this is the G&J definition), given any set A, where each element a∈A has a size s(z) that is a positive integer, can we find a subset A’ of A where the sum of the sizes of everything in A’ is exactly equal to the sum of the sizes of everything in AA’?)
Example: Suppose A was the set {1,2,3,4,6}. Then A’ could be {1,3,4}, forming a partition (A’ and AA’ both sum to 8). If instead, A was the set {1,2,3,4,5}, then no possible partition exists. This may seem like a silly case (any set A where the sum of the elements is odd has no partition), but even if the sum of the elements of A is even, it’s possible that no partition exists for example if A is {2,4,100}.
Note: Partition is one of my favorite NPComplete problems, because the description is so easy, and it seems so simple. It’s probably my goto example if I want to explain this stuff to nontechnical people in under a minute pretend that the elements of A are weights, and the value of each element is the weight in ounces. The partition problem asks “given this group of weights, and a scale, can you make the scale balance using all of the given weights?”. It’s pretty surprising to most people that the only known way to answer that question basically boils down to “try all possible combinations of arranging things on the scale”
The reduction: From 3DM. G&J provide the reduction on pages 6162. The basic idea is to have one element in A for each element in M, and to represent the elements in A as binary numbers that have 1’s in positions corresponding to which element from W, X, and Y we get the triple from. The number is set up so that we have a maximum possible value of the sum of all of these elements in A. They then add two “extra” elements to A so that each side of the partition (elements of M that make a matching, and everything else) will add up to the same value
Difficulty: 7. The idea of using binary numbers to keep track of “positions” in a list is tricky, but comes up in lots of places. If students have seen that idea before, this becomes a hard but doable problem. If students haven’t seen that idea before, I’d make this a 9.
Hamiltonian Circuit
This is one of my favorite problems, but one of the worst reductions to understand. I usually skip over it when I teach it, showing them the picture of the widget and saying “See? It’s Nuts!” and moving on
The problem: Hamiltonian Circuit (HC)
The definition: Given a graph G=(V,E), where V = N. Can I create an ordering <v_{1}, v_{2}…v_{n}>of the vertices where an edge exists between each (v_{i}, v_{i+1}) in the sequence, and the edge (v_{n}, v_{1}) also exists?
(In other words, does a sequence of edges exist that lets me start at some vertex, visit each other vertex exactly once, and return to the start?)
Example:
The sequence <a,d,h,k,g,c> forms a Hamiltonian Circuit
The reduction: Is from VC, and it’s nuts. G&J do it on pages 5660. Starting with an instance of VC (A graph G, and an integer K), build a new graph G’ with:
 K “selector” vertices (a_{1}a_{k})
 12 vertices and 14 edges (see page 57) for each edge in G (a “covertesting” component
 Edges to connect the selector vertices to the start and end of the covertesting component.
The Cormen algorithms book has an example of this, and it takes a graph with 4 vertices and 4 edges and builds a HC instance with 50 vertices and 72 edges.
Difficulty: 9, only because I’m sure there exist reductions that have like 25 page proofs, and I want to save my 10 for that. But really, I think just making the students trace this reduction on an example is a really hard problem.
Posted in Core Problems
Tagged core problems, Difficulty 9, Hamiltonian Circuit, reductions, Vertex Cover
Independent Set
The last of the three similar graph problems, it’s also probably the easiest reduction. When I teach NPCompleteness, I’ve had a lot of success starting with this reduction (instead of building a stable of NPComplete problems from zero like the textbooks do). You kind of have to say “Trust me, Vertex Cover is NPComplete, I’ll show you why later”, but starting with a simple reduction means that they can follow the idea and the process right from the beginning without having to be bogged down in ugly conversions involving SAT.
The problem: Independent Set (IS)
The definition Given a graph G=(V,E) and an integer J. Does G have a collection of at least J vertices where no edges connect any two vertices in J?
Example: Using the same graph:
{a,h,k} is an independent set of size 3.
The reduction: From VC. Use the exact same graph, and set J=VK. (G has an independent set of J vertices exactly when it has a vertex cover of K vertices. Vertices not in the cover can’t have edges between them).
Difficulty: 1. There’s a reason why I do this first (though sometimes I go from Clique instead). In general, though, I try to avoid making them do problems that are too easy for homeworks and tests. If the reduction is trivial, it makes the showing the conversion solves the original problem difficult. You get a lot of proofs that basically say “C’mon! They’re the same thing!”. Which is not what I’m looking for 🙂
Posted in Core Problems
Tagged core problems, Difficulty 1, Independent Set, Reduction, Vertex Cover
Clique
G&J don’t even bother to prove Clique is NPComplete, just stating that it (and Independent Set) is a “different version” of Vertex Cover. But the problem comes up often enough that it’s worth seeing in its own right.
The problem: Clique (I’ve also seen “Max Clique” or “Clique Decision Problem” (CDP))
The definition: Given a graph G=(V,E), and a positive integer J (G&J say J needs to be ≤ V, but I think you can allow large values and make your algorithm just say “no”). Does J contain a subset V’ of V, or size at least J, where every two vertices in V’ are joined by an edge in E?
Example: Using the graph we had for VC:
{a,c,d} form a clique of size 3. There are no cliques of size 4, but if we add the edge (d,g) and the edge (c,h), then the vertices {c,d,g,h} would be one.
The reduction: From Vertex Cover. Given a graph G and an integer K that is an instance of Vertex Cover, take the complement of G (the complement of a graph has the same vertices, but the set of edges is “inverted”: (u,v) is an edge in the complement if and only if it was not an edge in G), and use it as your instance of CDP. Set J= VK
Difficulty: 3. It’s not a 2 because it takes a little thought to see why the complement works.
Note: As stated perviously, I teach this course using the Cormen book, so in class I show Clique is NPHard by reducing from 3SAT. It’s a good example of a hard reduction, probably about as hard as the VC reduction G&J do.
Posted in Core Problems
Tagged Clique, core problems, Difficulty 3, reductions, Vertex Cover
Vertex Cover
Back to the “core 6” with a classic problem from graph theory. There are lots of similar graph problems, so it’s important to keep them all straight.
The Problem: Vertex Cover (VC)
The Definition: Given a graph G=(V,E) and a positive integer K (G&J say that K ≤ V, but really, if it’s bigger than that, you can have the algorithm just return “yes”). Can I find a subset V’ of V, V’ ≤ K, where every edge in E has at least one endpoint in V’?
Example: Hmm, I wonder if I can insert an image..
Ok, looks like that worked. In the graph above, {c,d,g} is a vertex cover, because all edges have at least one endpoint in the set {c,d,g}. As we’ll see later, a graph containing a clique (complete subgraph) of N nodes will need at have at least N1 of those vertices in the cover.
The reduction: From 3SAT. G&J on pages 5456 show the construction. We build a graph with vertices for all variables and their negation, with an edge between them. We have three variables for each clause, connected in a triangle. (The three variables correspond to “positions” in the clause). Then there is an edge from each vertex corresponding to a literal (or its negation) to its corresponding “clause vertex” the vertex that holds the position of that variable in the original formula. K= # of variables + 2* number of clauses.
Difficulty: 7 , assuming it’s the first time a student has seen this sort of reduction. If they have seen something similar (for example, a reduction from 3SAT to Clique), then maybe a 5. The ideas are pretty similar.
Note: I teach my algorithms class using the Cormen book. In it, they reduce 3SAT to Clique, proving Clique is NPComplete, and then reduce Clique to VC. This works in the exact same way as the reduction from VC to Clique that I’ll be doing here next.
Posted in Core Problems
Tagged 3sat, Clique, core problems, Difficulty 7, reductions, Vertex Cover
Exact Cover by 3Sets
This is not one of the “core six”, but it is used a lot in reductions, so it’s worth including since it builds right off of 3DM
Also, I think I will include examples for lots of these problems. Lots of times I have trouble parsing the problem description, so creating a concrete example is helpful.
The problem: Exact Cover by 3Sets (X3C)
The definition: Given a set X, with X = 3q (so, the size of X is a multiple of 3), and a collection C of 3element subsets of X. Can we find a subset C’ of C where every element of X occurs in exactly one member of C’? (So, C’ is an “exact cover” of X).
Example: Suppose X was {1,2,3,4,5,6}
If C was {{1,2,3},{2,3,4},{1,2,5},{2,5,6}, {1,5,6}} then we could choose C’ to be {{2,3,4},{1,5,6}} as an exact cover because each element in X appears exactly once.
If instead, C was {{1,2,3},{2,4,5},{2,5,6}}, then any C’ we choose will not be an exact cover (we need all 3 subsets to cover all elements in X at least once, but then the element 2 appears three times).
Note that if we do have an exact cover, C’ will contain exactly q elements.
The proof:G&J prove this “by restriction” which basically means that they show how X3C is a more general version of 3DM . If you view an instance of 3DM as a special case of X3C by letting X_{X3C} = W∪X_{3DM}∪Y and C = all q^{3 }triples taking one element from W, one element from X_{3DM}, and one element from Y), then the C’ you get as a solution to X3C is also a matching for 3DM.
(Note that lots of these reductions will be between problems that use the same symbols in both problems. I’ll do my best to disambiguate by using subscripts to mark where the common letter comes from. So, in this case X_{3DM} is the set X that we get from the 3DM problem (one of the 3 input sets), and X_{X3C} is the set we build for the X3C problem (the set we need to cover). Hopefully that doesn’t make things more confusing)
(Also note that like many (most?) Computer Science people, I’m a big fan of nested parentheses. I’m sure all of you can follow along with that. (Right?))
Personally, I don’t like proofs by restriction as a way to teach this stuff to students. It’s very easy to mess up the “this is a special case” argument you get incorrect arguments like “this is just a special case of SAT where we return true wherever there’s a cover and false when we don’t!”. Also it feels like you’re going backwards from a real reduction, and since getting the direction wrong is probably the #1 most common issue students have in doing reductions, anything that makes their job harder isn’t a great idea.
If I taught this in a class, I’d make them do a proper reduction out of it start with an instance of 3DM (W, X_{3DM}, and Y), and build an instance of X3C (creating X_{X3C} and C), and going from there.
Difficulty: 3. It’s only not a 2 because I, at least, have trouble understanding what the X3C and 3DM problems are asking. It’s not as straightforward to explain as many other problems
Posted in Core Problems
Tagged 3DM, core problems, Difficulty 3, reductions, restrictions, X3C
3Dimensional Matching
Last one for today. I’m not sure how exactly I’ll space these out. We’ll see.
The Problem: 3Dimensional Matching (3DM)
The Definition: Given disjoint sets W,X,Y all with the same number (q) of elements, and a set M of triples from WxXxY. Is there a subset M’ of M of size q where no two elements of M’ agree in any coordinate?
I always have trouble picturing what this means, so here’s an example:
Let W = {1,2,3,4}, X = {10,20,30,40}, Y = {100,200,300,400}. q is 4 in this case.
M is a set of triples like (1,30,400), (2,20,100), and so on, with one element from each of W,X, and Y.
We’re asking for q elements of M that have no duplicates in any coordinate. In other words, each of {1,2,3,4} appears in exactly one element of M’, each of {10,20,30,40} appears in exactly one element of M’, and so on. So, a legal M’ could be:
{(1,20,300), (2,30,400), (3,40,100), (4,10,200)}
..assuming all 4 of those triples happened to be in the M we were given.
The Reduction: From 3SAT. Pages 5052 explain how we take the clauses and build W, X, Y, and M from them. It’s pretty crazyM contains 3 kinds of triples for 3 different kinds of jobs, build according to 3 different sets of rules.
Difficulty: 8. I couldn’t imagine a student coming up with this without a lot of handholding.
3Satisfiability
The first of the “core six” problems, and the first NPComplete problem that’s actually a reduction from a known NPComplete problem.
The Problem: 3Satisfiability (3SAT)
The Definition: (p.46) Given a set of variables U, and a set C of clauses, where each clause has exactly 3 elements, can we assign true/false values to the variables in U that satisfies all of the clauses in C?
(Note that just as the Satisfiability problem was really “CNFSAT”, most people would call this problem “3CNFSAT”)
The Reduction: From SAT. Pages 4849 give a simple algorithm to convert arbitrarilysized clauses into clauses of size 3, possibly by adding some extra variables.
Difficulty: 6. It’s pretty fiddly to come up with the conversions in all cases. But this really depends on the students’ familiarity with Boolean logic.
As an aside, I find myself compelled to note that while 3CNFSAT is NPComplete, the similar problem of 2CNFSAT (where all clauses are of size 2) can be solved in polynomial time. To me, one of the coolest things in Computer Science is how such small changes to a problem (like 3CNF to 2CNF, or Fractional Knapsack to 0/1 Knapsackwhere the solution space shrinks!) can drastically affect the complexity of the problem.