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 using P. You should describe
- How an instance of P’ will be transformed into an instance of P.
- The worst-case running time of the transformation.
- How a solution to P will be transformed into a solution to P’.
- The worst case running time of this second transformation.
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).
- For this problem, you can add, subtract and divide by 2 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 x2 of x. P’: Compute the product xy of two integers x and y.
- 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.
- 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 at least one 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.