Tag Archives: Difficulty 6

Rooted Tree Storage Assignment

This whole section is filled with problem descriptions that confuse me.  Here’s another one:

The problem: Rooted Tree Storage Assignment.  This is problem SR5 in the appendix.

G&J’s definition: Given a set X, and a collection C= {X1..Xn} of n subsets of X, and an integer K.  Can we find a collection C’ = {X1‘..Xn‘} of n subsets of X, where:

  • Each Xi‘ contains all of the elements of it’s corresponding Xi, plus possibly some extra elements.
  • There are at most K new elements added across all Xi
  • We can treat the elements of X as vertices and add directed edges to form a directed tree where the elements of each Xi form a directed path.

Example: Suppose X = {1,2,3,4,5}, and X1 = {1,2,3,4} X2 = {1,3,4}  X3={1,3,5}, X4 = {2,5}

Then we can set each Xi‘ to be = Xi, except X3‘ where we’ll add the element 2.  This gives us the arrangement:



The way to think of the X1 is as “required elements along a path from the root”, and the Xi‘ is as “the actual elements along the path from the root”.

But the paper from Gavril that has the reduction gives what I think is the better definition:

Gavril’s Definition: (He calls this problem “Augmented directed tree arrangement”) Given a bipartite graph B, whose vertices can be split into two sets X and Y, and an integer K, can we add K or less edges to B to form a new bipartite graph such that:

  • The elements in X can be arranged as a directed tree
  • For each subset (I think- it’s not entirely clear whether this is a subset or just a single vertex) S of Y, the vertices in X that are adjacent to S can be arranged to form a directed path in the directed tree of X.

I like this better because you can see that the vertices that need to be in order in the tree  are “pointed to” by edges from Y.  The extra edges that you get in Xi‘ are created by adding more edges between X and Y.

Example: The example above would be represented by the following bipartite graph:


Notice how the vertices from X are arranged to almost form a directed path with no gaps, but we need to add an edge from X2 to Y3 to fix the arrangement.

Reduction: The Gavril paper uses Rooted Tree Arrangement.  So we’re given a graph G=(V,E) and an integer K.  Our bipartite graph will have X=V, and Y=E, and each vertex in Y will connect to the 2 vertices in X that correspond to the endpoints of the edge in G. K’ = K-|E|.

If you’re worried- like I was- that this might possibly make K’ negative, keep in mind that the K for the Rooted Tree Arrangement Problem was the sum of the paths between pairs of vertices in G that are connected by an edge.  So for K to be meaningful it has to be ≥ E.

If we have a solution for the Rooted Tree Arrangement problem, then we have a path between all pairs of vertices connected by an edge in E.  So, for each vertex in Y, look at the path in the solution. If the path goes through additional vertices besides the endpoints of the edge, add an edge to our bipartite graph from the vertex in Y to the vertex passed through in X.  In doing so, we will add at most K-|E| edges to the bipartite graph, and can use the arrangement that is a solution to the Storage Assignment problem.

If we have a solution to the Storage Assignment problem, the edges that were added to the bipartite graph mark the vertices traveled along a path that solves the Rooted Tree Arrangement problem, and so tells us how to build a satisfying arrangement.

Difficulty: 6.  This isn’t the hardest reduction to understand, but it does require you to know the Rooted Tree Arrangement problem really well, and to understand just what the job of the bipartite graph is.

Kth Largest m-Tuple

I think I’m going to move the posts to Wednesday this semester since I teach two 2-hour classes on Tuesday/Thursday.

SP19 is Minimum Sum of Squares

SP20 is Kth Largest Subset and is very similar to our next problem.

The problem: Kth Largest m-Tuple.  This is problem SP21 in the appendix.

The description: Given sets X1 through Xm that all contain positive integers, and integers K and B, are there at least K m-tuples (x1, .., xm) from X1 x X2 x … x Xm for which the sum of the elements in each tuple is at least B?

Example: Let X1 = {1,2,3,4}, X2 = {5,10}, X3 = {1,2}. Notice that the X’s can be different sizes, and can repeat elements.

If B = 15, then the only tuples that sum to at least 15 are {3.10,2), (4,10,1), and  (4,10,2).

Reduction: The paper by Johnson and Mizoguchi presents the reduction pretty densely, but here is what I think they are saying:  We’re going to use a Turing Reduction to solve the Partition problem, which means we’re given an instance of Partition, and assume we can call a subroutine to solve the Kth Largest m-tuple problem multiple times to solve the Partition instance.  Recall that we can use Binary Search on multiple calls of the subroutine to determine (for example) how many tuples sum to some B or more.  (We need multiple calls because the subroutine is a boolean one, just saying yes or no to a given instance).

Updated reduction:

This idea came from Said D. in the comments, and I wanted to make sure it got posted here because it’s so simple and elegant.  If we are given a partition instance S = {s1..sn} and need to know if a subset sums to B (= half the sum of all of the elements in S), then the sets we create for the Kth Largest m-tuple instance are:

{s1+1, 1}, {s2+1, 1}, …(sn+1, 1}

And we number the K-th Largest m-tuple is looking for is B+n.  Each set will contribute 1 to the tuple sum no matter which element is chosen.  It may also contribute si as well, corresponding to whether we “take” that element in the partition instance or not.

That’s way better than what I was trying to do.  Thanks, Said!

The rest of my not very good reduction:

I’ll leave the rest up here for posterity, but this is way worse than Said’s idea above, and glosses over the fact that you can’t just use any elements you want as the sets- you need to set them up in a way that makes sure you don’t repeat elements when you choose the tuples.

So, in a manner similar to that used in the Kth Largest Subset reduction, we can find the number of tuples that sum to any B we want (including half the sum of all of the elements in the partition instance).  The only tricky part is that our “subsets” are tuples of different sizes.  So we need to run this algorithm multiple times:

  • Are there are 1-tuples that solve the partition problem?  (There are O(n)  1-tuples, so a binary search requires O(log n) calls)
  • Are there any 2 tuples that solve the partition problem?  (There are O(N^2) 2-tuples, so a binary search requires O(2* log n) calls)
  • Are there any m-tuples that solve the partition problem? (There are O(N!) n-tuples, so a binary search requires O(n * log n) calls)

Thus, we can do it in a polynomial number of calls to the K-th Largest m-tuple solver.

Difficulty: This is a little harder than the Kth largest subset reduction, which I gave a 5, so I’ll make this a 6.

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.

Protected: Minimum Broadcast Time

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

Protected: Edge Embedding On A Grid

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

Protected: Undirected Flow With Lower Bounds

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

Protected: Minimum Cut Into Bounded Sets

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

Protected: Acyclic Partition

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

Protected: Multiple Choice Branching

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

Protected: Bounded Diameter Spanning Tree

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