Continuing our “Variants on the Knapsack Problem” theme..
The problem: Partially Ordered Knapsack. This is problem MP12 in the appendix.
The description: Like usual, we’re given a set U, where each element u in U has positive integer size s(u) and value v(u), a maximum total size B, and a target total value K. We also are given a partial order on the elements of U, which we can represent as a directed acyclic graph. Can we find a subset U’ of U where the total size of all elements in U’ is at most B, the total value of all elements in U’ is at least K, and for all elements u in U’, if some other u’ is u’, then u’ is also in U’?
Example: Suppose we have the following 3 elements:
If B=6 and K=6, and there is no partial order, then taking items 1 and 2 make a valid solution. But if we add the partial order graph:
Than taking either item 1 or 2 means we have to also take item 3, which makes our size too big. So this version can’t be solved.
Reduction: G&J have this as a “no reference” reduction, but I found a paper by Johnson and Neimi that has it, and I’m glad I did because it’s pretty slick. The reduction is from Clique, So we’re given an undirected graph G=(V, E) and an integer K. We need to build a partial order DAG (where the vertices will be knapsack items), and also sizes and values for each item.
The DAG has a vertex for each vertex and edge in G (I’ll be talking about these as “vertices from V” and “vertices from E”) Edges in the DAG connect vertices from V to the vertices from E that are incident on that vertex. So there is no path of length more than 1 in the partial order (no edges come out of the vertices from E).
Both the value and size of each vertex from V are |E|+1, and the value and size of each vertex from E are 1.
B’ and K’ will both be set to K(|E|+1) + K(K-1)/2. It’s worth noting that the first half of that equation will be the total profits and sizes of K vertices from V, and the second half will be total profits and sizes of the edges connecting those vertices if they form a clique.
Suppose we have a clique in G. Then all of the vertices in the clique, plus all of the edges in the clique form a solution to the partially ordered knapsack problem, as described above.
If we have a solution to the Partially Ordered Knapsack problem, that means we have a set of vertices that respects the partial order with total value at least K’ and total size at most B’. Since the value and size of each vertex are the same, that means that the total value = the total weight = K’ = B’. The only way to get that is if we have K vertices from V, and K(K-1)/2 vertices from E. Since the partial order is built such that we can’t take a vertex from E without taking a vertex from V that is an endpoint of the vertex from E, this means that we have a set of K(K-1)/2 edges in E that all have endpoints in one of K vertices from V, which forms a clique.
Difficulty: 5. I like how the formula for B’ in the reduction is one where you can easily see what all of the pieces of it are doing, and where they all come from.