Tag Archives: 3DM

Numerical 3-Dimensional Matching

SP15 is 3-Parttion.

The next problem is one of G&J’s “unpublished results” problems.  I tried figuring out an elegant way to doing it, but couldn’t make it happen.

The problem: Numerical 3-Dimensional Matching.  This is problem SP16 in the appendix.

The description: Given three sets W, X, and Y, each containing the same amount (m) of elements with positive “sizes” and a positive bound B.  Can we create m sets A1 through Am (containing 3 elements each), such that:

  • Each Ai has exactly one element from W, X, and Y
  • The sum of the sizes of the elements in each Ai is exactly B
  • Each element in W, X and Y is in some Ai

Example: Suppose we have the following sets:

  • W has elements with sizes {1,2,3,4}
  • X has elements with sizes {12,11,7,5}
  • Y has elements with sizes {1,1,4,5}  (the ability to allow repeat numbers is why we define the sets as elements with sizes rather than sets of integers)

If B=14, then the partition where A1 is the first element in W, X, and Y, A2 is the second element in W, X, and Y, and so on gives each Ai set a sum of 14.  Obviously, we don’t need to choose corresponding elements from W, X, and Y to form the sets (for example, rearranging the elements in X to be in increasing order doesn’t change whether the problem can be solved, just the exact composition of the Ai sets)

Reduction: I tried doing a reduction using 3-partition, but got stuck (I’ll show it below, in case you want to try to fix it).  G&J refer you to Theorem 4.4 in the book, which is the proof that 3-partition itself is NP-Complete.

We can follow that along and do similar steps to our problem:

  • Theorem 4.3 shows how to turn 3DM into 4-partition (a problem like 3-partition but each set in the solution has 4 elements instead of 3).  Since the sets that are created in the 4-partition solution come from 4 different places (page 98 calls then a “ui, a wi[·], an xj[·], and a yk[·]).  Since these partitioned sets all add to the same total (B) and come from 4 disjoint parent sets, we can see how we could do basically the same reduction and show that the “numerical 4-dimensional matching problem” is NP-Complete.
  • Theorem 4,4 shows how to turn a 4-parition problem into a 3-partition problem.  The idea is to add enough “pairing” and “filler” elements to the 3-partition instance to make any 4-partition set be split into two 3-partition sets, each consisting of 2 elements from the 4-parittion, plus the “pairing” element of one of the 2 elements chosen.  We can do something similar converting numerical 4-dimensional matching to numerical 3-dimentional matching.  (The difference is that we are given specifically which sets the elements are coming from)  So, if we’re given W, X, Y, and Z in our numerical 4DM instance, we construct W’ to be elements from W and Y, X’ to be elements from X and Z, and Y’ to be the pairing elements of pairs from W’ and X’.  We then need to add enough filler elements to our 3 sets in a similar way to the 3-partition proof (again, the difference is that we have to specifically assign them to W’, X’, or Y’.  But that can be determined by how the 3-partition proof allocates the items)

Difficulty: If you have gone over the 3-partition reduction, this is probably a 6.  Lots of tricky math but doable in a (hard) homework.    But keep in mind you’re tacking it on to the difficulty 8 of understanding the 3-partition reduction in the first place.

My reduction I couldn’t get to work: I really want there to be an easier way to do this.  I tried reducing from 3-partition directly because the problems are so similar.  Here is where I got to:

We’re given a 3-parititon instance S, and an integer B.  Our goal is to split S into sets of size 3 that all add up to B.

So, let’s use S to create 3 sets in our numerical 3DM instance:

  • W has all of the elements in S
  • X has all of the elements in S, but the sizes are each increased by 10B.
  • Y has all of the elements in S, but the sizes are each increased by 100B.

This would make B’ be 111B.

S has a 3-parititon, then for each set {si, sj, sk}, we take the three sets {wi, xj, yk}, {wj, xk, yi}, and {wk, xi, yj}  This will solve the numerical 3DM instance.

My problem comes showing this in the other direction.  If we have a numerical 3DM solution, we can only construct the 3-partition instance if the sets in the 3DM solution arrange themselves nicely like they do above.  I need to show that if the 3DM solution has {wi, xj, yk}, then the set in the 3DM solution that contains wj also contains xi (or xk) and yk (or yi).  I think you can get there by using the rules about how the bounds of the elements in the 3-partition instance work, but the work you need to do to show that it’s true makes this way of doing things no longer “easier” than the Theorem 4.4 proof I sketched above, so I gave up on it.

I still wish there was a more elegant way to transform this problem, though.

3-Matroid Intersection

This is a problem that was really hard for me to understand and explain.  It may be less so or other people, though.

The problem: 3-Matroid Intersection.  This is problem SP11 in the appendix.

The description: Given three matroids (E,F1), (E, F2), (E,F3), and a positive integer K.  Can we find a subset E’ of E with K elements that is in the intersection of F1, F2, and F3?

A matroid (E,F) is a set of elements E, and a family F of subsets of E with the following properties:

  • Some set S in the family F implies that all subsets of S are also in F.
  • If I have two sets S and S’ in F, and |S| = |S’|+1, then there is some element e that is in S but not S’, and adding e to S’ gets us a set also in F.

A common example of matroids comes from graph theory: Given a graph G=(V,E), the matroid based on this graph is (E,F), where E is the set of edges in the graph, and F is the collection of edges that have no cycles (i.e, forests)  This follows the two rules above:

  • If S is a collection of edges that do not form a cycle, then any subset of S is also a collection of edges that do not form a cycle.
  • If I have two collections of edges S and S’, and S is larger than S’ by one element, we need to find an edge in S that connects two connected components  (trees in the forest) in S’.  Since each tree on K vertices has exactly K-1 edges, S has at least one edge that is not part of any tree in S’ (adding an edge to a tree causes a cycle).  That edge must either connect two trees together, or connect a vertex in some tree to a vertex not used in S’, or connect two vertices not used in S’.  Either way, adding this edge to S’ gives us another forest.

Example:  Since the reduction we’re going to use involves building three matroids from a basic graph, let’s do that.  Here is a graph:

3matroidintersection1

We’re going to use this graph to induce 3 matroids.  The first will be the graph matroid (using the rules defined above) on the undirected version of this graph:

3matroidintersection2

So F1 is the set of all forests in the above graph.

F2 is collections of sets of edges in the directed graph where each vertex has at most one incoming edge.  So, sets like {(s,a), (a,t)} or {(a,b), (b,c), (c,t)}.  The exception is that vertex s must have zero incoming edges in any set in the family.

F3 is built similarly, except we count outgoing edges, and t (instead of s) is the vertex restricted to have 0 outgoing edges.

If K=4, then the following set of edges is in all three families: {(s,a}, (a,b), (b,c), (c,t)}.  It’s acyclic, so it’s in F1.  No vertex in that set has indegree or outdegree of more than 1 (and s has indegree 0 and t has outdegree o), so it’s in F2 and F3.

Just to clarify, because it’s confusing to me.  The sets E that are the “elements” of the matroid are edges in the graph, and the families F are collections of edges.  We just found a collection of 4 edges that will be in all three families.

The reduction: G&J don’t give a reference to this problem, but suggest using 3DM. In my searches, I found that Wikipedia and this set of lecture notes from MIT both want to use Hamiltonian path between two vertices.   (Notice that the “corrected” reduction for HP actually specifies the two vertices to connect between, so the HP reduction also proves this variant).  Here is my explanation of the reduction in the MIT lecture notes.  The class was taught by Michael Goemans, and I got the notes from his web site.

So, we start with an instance of HP- a possibly directed graph G=(V,E), and two special vertices s and t that we want to see if there is a Hamiltonian Path between.  We build the three matroids described in the examples based on using the edge set E: One based on forests in E, one based on collections of edges that have indegree at most 1 on each vertex, and one based on collections of edges that have outdegree at most 1 on each vertex.  Set K = |V|-1.

Notice that an intersection of these three matroids has to be a collection of paths that do not encounter the same vertex twice.  If we can create a collection that has K edges in it, the path will start at s (because F2 ensures that no edges going into s will be part of the intersection), encounter each vertex once (because F1 ensures that we have no cycles, and thus hit each vertex at most once), and end at t (because F3 ensures that no edges leaving t will be part of the intersection).  Thus, we have an intersection of K edges if and only if V has a Hamiltonian cycle.

Difficulty: It’s an 8 for me.  Since this is taught in a relatively small part of one lecture of a class (yes, a class at MIT, but still just a class), presumably it may be less for other people.  But I have a lot of trouble thinking in terms of matroids, and even now, I’m not really convinced that the three families of edges we create are polynomial in size.

Protected: Minimum Test Set

This content is password protected. To view it please enter your password below:

Protected: Minimum Cover

This content is password protected. To view it please enter your password below:

Protected: Metric Dimension

This content is password protected. To view it please enter your password below:

Protected: 4-Partition

This content is password protected. To view it please enter your password below:

Protected: Parttion Into Perfect Matchings

This content is password protected. To view it please enter your password below:

Protected: Partition Into Paths of Length 2

This content is password protected. To view it please enter your password below:

Partition

First, an administrative note.  I wanted to call this site “Annotated NP-Complete 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 A-A’?)

Example: Suppose A was the set {1,2,3,4,6}.  Then A’ could be {1,3,4}, forming a partition (A’ and A-A’ 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 NP-Complete problems, because the description is so easy, and it seems so simple.  It’s probably my go-to example if I want to explain this stuff to non-technical 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 61-62.  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 3-Sets

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 3-Sets (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 3-element 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 XX3C = W∪X3DM∪Y and C = all q3 triples taking one element from W, one element from X3DM, 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 X3DM is the set X that we get from the 3DM problem (one of the 3 input sets), and XX3C 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, X3DM, and Y), and build an instance of X3C (creating XX3C 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