Unifying Ideas in Computer Science
Spring 2015
MP Johnson

Problem Set 3
Due by email by 11:59pm, Saturday, May 2nd

You're free to work with a partner, but you must each submit five different problems.

  1. Give five interesting NP-Complete problems that haven't been discussed in class. There are oodles of them out there (use Google). Maybe find problems related to some interest of yours (how to do x minimizing/maximizing y).

    1. For each problem, formally define it along the lines of this model:

      Problem: Maximum Independent Set
      INSTANCE: Graph $G=\left(V,E\right)$.
      SOLUTION: An independent set of vertices, i.e. a subset $V' \subseteq V$ such that no two vertices in $V'$ are joined by an edge in $E$.
      MEASURE: Cardinality of the independent set, i.e., $\vert V'\vert$.

    2. Also, try to state, based on research online, what is known about its approximability. (Recall that although all these problems are equally hard to solve exactly, some of them are easier to approximate than others.) E.g., does somebody have a paper giving a 2-approximation? Does somebody have a paper showing that no approximation is possible? Give the reference and state what they claim about the problem's approximability status.

    3. Finally, give an integer programming (IP) formulation of the problem, and an informal description of what the IP intuitively means. For example, in the case of Maximum Independent Set, you could give:

      $\max \sum x_v$
      s.t.
      $x_u + x_v \le 1 \quad \forall (u,v) \in E$
      $x_v \in \{0,1\}$

      (intuitively: choose as many nodes as you can, but for each edge in the graph, you can't choose both of its nodes).