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).
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 an integer x, compute the square of x (that is, x*x).
P': Compute the product xy of two integers x and y.
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.