Due 23/10.  Homework 7

1.  Here is a different definition of reducibility.

    Definition: We will say that problem P reduces to problem Q if we
    can devise a polynomial time algorithm to solve a problem P given
    a subroutine for Q that runs in polynomial time.

    The key difference is that Q can be called several times, not just
    once as in our definition.

    (a) How many times can the subroutine for Q be called (and yet the
    algorithm for P remains polynomial time)?

    (b) Suppose my algorithm for P is:

	x = input instance // could be anything, e.g. list

	for i = 1 to n     // n = length of x at the beginning
	    x = Q(x)
	end

	return x

	Will this always run in polynomial time?

2.  Suppose you are given a polynomial time algorithm for deciding
    whether an independent set of given size exists for a given graph.
    Show that you can design a polynomial time algorithm to construct
    the independent set by calling the decision algorithms
    appropriately, and an appropriate number of times.  This will be a
    reduction, in the sense of the definition above, of the
    construction problem to the decision problem.

    (Hint: Suppose the instance for the construction problem is G,k.
    Suppose I just want to determine whether the vertex numbered 1 is
    a part of the independent set.  Can I run the decision algorithm
    on a suitably constructed G',k' and determine this?)

3.  Show that the Knapsack problem reduces to subset sum.

4.  In the 0-1 integer programming problem the input is an m x n
    integer matrix A, and b is an n vector of integers.  The question
    is whether exists a m-vector x consisting of only 0s and 1s such
    that Ax <= b.  Show that 3 CNF-Sat reduces to 0-1 integer linear
    programming.

    (Hint: can the logical conditions on the variables in the CNF
    formulae be represented using additions?  Note that coefficients
    of A can be negative, so subtraction can also be represented.

    Do mention how large the numbers of the matrix A that you
    construct will become.  If the numbers become too large, your
    instance map may not run in polynomial time.  So this is
    important.)

5.  A clique is a graph in which every vertex is connected to every
    other vertex.  The decision problem CLIQUE takes as input a graph
    G and asks whether there is a clique of size k in that graph.

    Show that the independent set problem reduces to CLIQUE.

6.  The subgraph isomorphism (SI) problem takes as input graphs G1 and
    G2 and asks whether G2 is a subgraph of G1.  Show that the 3-sat
    reduces to SI.  Do not explicitly give a reduction, but use
    transitivity and reduce something more convenient to SI.