Sample problems for tutorial week 3

All of the problems for this week's tutorial are about reductions. In each case, you are given both a problem P that we assume we already know how to solve, and a problem P' that we want to solve by solving one or more instances of P. You should describe

Please note that these are real "brain stretching" activities to get you thinking about graphs and reductions. A big part of the learning here is working through the terminology and writing out and reasoning about the reduction AFTER being given the core insight, not coming up with the core insight (although we will give you some time to try to come up with the core insight too).

  1. P: Given a graph G = (V, E), we want to find the largest clique in G. That is, we want the largest subset W of V with the property that every two elements of W are joined by an edge in E.

    P': Given a graph G = (V, E), we want to find the largest independent set in G. That is, we want the largest subset W of V with the property that no two elements of W are joined by an edge in E.

  2. For this problem, you can add and subtract if needed, but you should only need a tiny amount of addition/subtraction. Don't try to ignore P and do all of P' directly!

    P: Given an integer x, compute the square of x (that is, x*x).

    P': Compute the product xy of two integers x and y.

  3. P: Given a graph G = (V, E) and an integer K, we want to find a dominating set with K vertices in G. That is, we want a subset W of V such that |W| = K, and the property that every elements of V - W is joined by an edge to an element of W.

    P': Given a graph G = (V, E) and an integer K, we want to find a vertex cover with K vertices in G. That is, we want a subset W of V such that |W| = K, and the property that every edge in E has at least one endpoint in W.