Homework 12
Last updated: Wed, 12 May 2021 19:35:11 -0400
Out: Wed May 5, 00:00 EST Due: Wed May 12 Fri May 14, 23:59 EST
This homework covers material from Chapter 7 of the textbook.
Homework Problems
Undirected Hamiltonian Paths (6 points)
Maximum Satisfiability (6 points)
P, NP, and 2COMPONENTS (6 points)
Cliques and Kites (6 points)
Traveling Salespeople (6 points)
README (2 points)
Total: 32 points
Submitting
Submit this assignment at Gradescope hw12.
should only include pdf or plain text files,
and each file must be assigned to the correct problem in Gradescope.
1 Undirected Hamiltonian Paths
Theorem 7.55 in the textbook proves that
\textrm{\textit{UHAMPATH}} = \{\left\langle G,s,t\right\rangle\mid G\textrm{ is an undirected graph with a Hamiltonian path from }s\textrm{ to }t\}
is \textrm{NP}-complete.
Read and understand the proof.
Then, based on this understanding, re-state the proof in your own words by explicitly describing the five steps (numbered 1-5) we followed in class when using Theorem 7.36.
2 Maximum Satisfiability
Most of the search problems we’ve studied have an optimization variant that is often more useful in practice. For example, the \textrm{MAXSAT} problem is the problem of trying to satisfy as many clauses as possible in a Boolean formula. It is extremely useful in a variety of applications such as solving package dependencies and bug finding.
Formally,
\textrm{MAXSAT} = \{\left\langle\phi , k\right\rangle\mid\phi\textrm{ is a Boolean formula in conjunctive normal form with }k\textrm{ satisfiable clauses}\}
Show that \textrm{MAXSAT} is \textbf{NP}-complete.
Make sure your answer includes all five steps described in class.
3 P, NP, and 2COMPONENTS
Show that if \textbf{P}\neq\textbf{NP}, then the \textrm{2COMPONENTS} problem from Homework 11 cannot be \textbf{NP}-complete.
4 Cliques and Kites
Recall that a clique in an undirected graph is a subgraph where all pairs of nodes in that subgraph are connected by an edge.
A kite is a subgraph in an undirected graph where half the nodes in the subgraph form a clique, and the other half form a "tail" where all these tail nodes are connected in a row and the last one connects to one of the nodes in the clique (just like in an actual kite).
Formally,
\textrm{KITE} = \{\left\langle G,2k\right\rangle\mid G\textrm{ is an undirected graph containing a kite with } 2k \textrm{ nodes}\}
Show that \textrm{KITE} is \textbf{NP}-complete.
If you use Theorem 7.36, make sure your answer includes all 5 steps described from class.
5 Traveling Salespeople
Define the Traveling Salesperson problem to be the language:
\textrm{TSP} = \{\left\langle G\right\rangle\mid G\textrm{ is an undirected graph that contains a cycle that touches every node exactly once}\}
Show that \textrm{TSP} is \textbf{NP}-complete.
If you use Theorem 7.36, make sure your answer includes all 5 steps described from class.