MPCS 55001 — Problem Set 8

Instructions

This problem set is due on Wednesday June 3, 2020 at 20:00 Central, to be submitted on Gradescope. Each problem is worth 10 marks in total.

You may assume that the following problems are $\mathbf{NP}$-complete:

• Satisfiability: Given a propositional formula $\varphi$, is there an assignment of variables that satisfies it?
• 3-SAT: Given a propositional formula $\varphi$ in conjunctive normal form with exactly three literals per clause, is there an assignment of variables that satisfies it?
• Vertex Cover: Given a graph $G$ and integer $k \geq 0$, does $G$ contain a vertex cover of size at most $k$?
• Independent Set: Given a graph $G$ and integer $k \geq 0$, does $G$ contain an independent set of size at least $k$?
• Set Cover: Given a set $U$ of $n$ elements, a collection $\mathcal X = \{X_1, X_2, \dots, X_m\}$ of subsets of $U$, and an integer $k \geq 0$, does there exist a collection of at most $k$ sets from $\mathcal X$ such that their union is equal to $U$?
• Hamiltonian Cycle: Given a graph $G$, does $G$ contain a Hamiltonian cycle? (A Hamiltonian cycle is a cycle which visits every vertex exactly once)
• Subset Sum: Given a set of natural numbers $S = \{n_1, \dots, n_k\}$ and an integer $N \geq 0$, is there a subset of $S$ whose members add up to $N$?

Problems

1. Suppose you have an oracle $\mathcal O$ that solves Hamiltonian Cycle: If you give $\mathcal O$ a graph $G$, $\mathcal O$ will respond, in $O(1)$ time, with Yes if $G$ contains a Hamiltonian cycle and No if $G$ does not contain a Hamiltonian cycle. Explain how to use $\mathcal O$ to find the edges of the Hamiltonian cycle, if it exists, in polynomial time.

2. The Subgraph Isomorphism problem is: Given graphs $G$ and $H$, does $G$ contain a subgraph that is isomorphic to $H$? Show that Subgraph Isomorphism is $\mathbf{NP}$-complete.

3. 315 Production is a talent agency with many fun and interesting personalities. Suppose you are organizing a live concert event over two days featuring talent from your agency. You have a number of acts that you can put on and you would like to divide the acts so that the total time of their performances is even between each of the two days. The problem we would like to solve is the following:

   Given $n$ acts with performance time $t_1, \dots, t_n$, decide whether or not there is a way to divide up the acts into two sets $D_1$ and $D_2$ such that \[\sum_{t_i \in D_1} t_i = \sum_{t_j \in D_2} t_j.\]

   Does this problem have a known efficient algorithm? Either prove that there is by giving a polynomial time algorithm or prove that there isn't via a reduction.