
Recent Posts
 Sequencing With Deadlines and Setup Times January 17, 2018
 Knapsack January 10, 2018
 Sequencing to Minimize Weighted Tardiness January 3, 2018
 Scheduling to Minimize Weighted Completion Time December 18, 2017
 Sequencing to Minimize Tardy Tasks, Sequencing to Minimize Tardy Task Weight December 13, 2017
Recent Comments
Archives
 January 2018
 December 2017
 November 2017
 October 2017
 September 2017
 August 2017
 July 2017
 June 2017
 May 2017
 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
 Algebra and Number Theory
 Appendix Automata and Language Theory
 Appendix Mathematical Programming
 Appendix Network Design
 Appendix Sets and Partitions
 AppendixGraph Theory
 AppendixLogic
 Appendix: Sequencing and Scheduling
 Appendix: Storage and Retrieval
 Chapter 3 Exercises
 Core Problems
 Overview
 Problems not in appendix
 Uncategorized
Meta
Tag Archives: 3DM
Protected: Numerical 3Dimensional Matching
Enter your password to view comments.
Posted in Appendix Sets and Partitions
Tagged 3Partition, 3DM, 4Partition, Difficulty 6, Difficulty 8, Numerical 3Dimensional Matching, SP15, SP16
Protected: 3Matroid Intersection
Enter your password to view comments.
Posted in Appendix Sets and Partitions
Tagged 3Matroid Intersection, 3DM, Difficulty 8, Hamiltonian Path, No G&J reference, SP11
Protected: Minimum Test Set
Enter your password to view comments.
Posted in Appendix Sets and Partitions
Tagged 3DM, Difficulty 7, Minimum Cover, Minimum Test Set, No G&J reference, uncited reduction, Vertex Cover
Protected: Minimum Cover
Enter your password to view comments.
Posted in Appendix Sets and Partitions
Tagged 3DM, Difficulty 1, Minimum Cover, Set Packing, Set Splitting, SP1, SP2, SP3, SP4, SP5, X3C
Protected: Metric Dimension
Enter your password to view comments.
Posted in AppendixGraph Theory
Tagged 3sat, 3DM, Difficulty 8, GT61, Metric Dimension
Protected: 4Partition
Enter your password to view comments.
Posted in Problems not in appendix
Tagged 3DM, 4Partition, Difficulty 8
Protected: Parttion Into Perfect Matchings
Enter your password to view comments.
Posted in AppendixGraph Theory
Tagged 3DM, Difficulty 4, Difficulty 9, GT16, NAE3SAT, uncited reduction
Protected: Partition Into Paths of Length 2
Enter your password to view comments.
Posted in Chapter 3 Exercises
Tagged 3DM, Difficulty 7, PPL2, reductions, uncited reduction
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.
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