Monthly Archives: December 2016

Subset Product

I’m setting this to post automatically on the 27th.  Hopefully, it posts correctly.

Sp12 is Partition

Sp13 is Subset Sum

This next problem is related to those, but has a cool twist.

The problem: Subset Product.  This is problem SP14 in the appendix.

The description: Given a set A of positive integers, and a positive integer B, is there a subset A’ of A such that the product of the sizes all elements in A’ is exactly B?

(The G&J definition of the problem defines A as a set of generic elements, each with a positive integer “size”.  This is more general in that it allows for two different elements in A to have the same size.  But most of the time this and similar problems (for example: Subset Sum, Partition) are encountered, it is with the definition above)

Example: Let A = {1,2,3,4,5,6} .  If B = 60, then setting A’ to {2,4,5} solves the problem.  If B=61, then no subset of A will multiply to B.  61 is easy to see since it’s prime, but other non-prime numbers (like 35) also will not have a solution.

The reduction: G&J say to use X3C, and I’ll admit that this idea came to me while I was wrestling with the reductions for Comparative Containment and its relatives, with all of their work creating sets based on prime numbers.

We start with an instance of X3C: a set X with 3q elements, and a collection of 3-element subsets of X.

What we’re going to do is assign a prime number to each element in X- so the first 3q prime numbers will be allocated.

Each element in C will be represented by an element whose size is the product of the 3 prime numbers corresponding to the elements in C.   Notice that since each of the elements in X are represented by distinct prime numbers, the only way for two elements in C to generate the same number is if the two elements in C were exactly the same.  (In which case, the duplicate can be safely removed).

Our set A will be the collection of these C numbers, and our integer B will be the product of the first 3q primes.

So, if a cover C’ exists, multiplying all of the elements in C’ together will give us a number that is the product of the first 3q primes, because each element x in X will appear as a factor in some c in C’ exactly once, and thus each x’s prime number assignment will appear exactly once in the product of all of the numbers that represent the sets in C’.

If a subset A’ of A that multiplies to B exists, then the prime factorization of B gets us each of the first 3q prime numbers exactly once.  Each of the elements in A’ corresponds to a set in C, and the prime factorization of that element in A’ will “cover” three elements in X.  The union of all such coverings will cover X entirely.

The only hard part that remains is to decide whether we can actually find the first 3q prime numbers in polynomial time.  The prime number theorem says that the nth prime number is proportional to n log n, and brute-forcing whether a number is prime is O().  Thus, we should be able to find the first 3q prime numbers in polynomial time just by checking each number individually, starting from 2.  Obviously, more efficient methods also exist.

Difficulty: 4.  It’s easy to go off in very different directions (for example, trying to compare this problem to Sum of Subsets by realizing that taking the logarithm of a product gets you a sum). Also the prime number theorem stuff isn’t obvious, and I don’t know how you mention its existence to students without spoiling the entire reduction.

Still, once they have that possibly obscure bit of knowledge, this is a good easy reduction that many students can follow.

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:

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:

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.