Homework 9 Integer programming

1. (2 points) In 0-1 Integer programming, there are a set of inequalities of the form: a 1 , 1 X 1 +
. . . a 1 , n X n ≥ b 1 ; . . . ; a m , 1 X 1 + . . . a m , n X n ≥ b m
The coefficients a 1 , 1 ⋅ ⋅ ⋅ a m , n , b 1 ⋅ ⋅ ⋅ b m are rational numbers and X 1 ⋅ ⋅ ⋅ X
n are Boolean variables. The problem has an Yes answer if there are solutions to the Boolean
variables that satisfy all inequalities. Show that the 0-1 Integer programming is NP-complete.
Hint: First show that it is in NP. Then show that Sat can be expressed as a 0-1 Integer program.
This is one of the easier ways to reduce a problem to another. To reduce A to B, show that B can
express A as a special case.
2. (2 points) Clique. Given an undirected graph G and an integer p, we want to determine if it has
a clique, i.e., a subgraph where there is an edge between each pair of nodes, of size p. Show that
the clique problem is NP-complete by a reduction from independent set.
3. (2 points) dHamPath. Show that determining if a directed graph has a directed Hamiltonian
path, i.e., a directed path from some node s to some other node t that visits every other node
exactly once is NP-complete by a reduction from dHamCycle.
4. (2 points) Given a set of n items of values V1, ...,Vn and weights W1,...,Wn, and a capacity W,
the 0-1 Knapsack problem selects a subset of the items which can fit in the knapsack to
maximize their total value. A decision version of this problem asks if there is selection of items
which fit into the knapsack and has a value at least T. Reduce the subset sum problem to the
knapsack problem to show that it is NP-hard.
5. (2 points) Assume that there are n tasks with integer processing times t1.. tn that should be
scheduled on two machines. Every task can be scheduled on either machine but not both. We
want to minimize the total time by which all tasks are completed. Ideally the tasks can be
scheduled so that the total processing time is equally divided. Show that determining if the
processing time can be equally divided is NP-complete by reducing the subset sum problem to
it.
Please submit this on Canvas using file upload.