Homework 9
Last updated: Sun, 28 Nov 2021 12:02:14 -0500
Out: Thu Nov 18, 00:00 EST Due: Sun Nov 28 Tues Nov 30, 23:59 EST
This assignment explores NP and NP-completness.
Homework Problems
Is HAMPATH in NP? (4 + 4 = 8 points)
I Thought CLIQUE was NP-Complete? (5 + 5 = 10 points)
Maximum CLIQUE (10 points)
Double Satisfaction (10 points)
README (2 point)
Total: 40 points
Submitting
Submit your solution to this assignment in Gradescope hw9. Please assign each page to the correct problem.
A submission must include a README containing the required information, in addition to the solution to the problems.
1 Is HAMPATH in NP?
Recall the \textrm{HAMPATH} language from class:
\textrm{HAMPATH} = \left\{\left\langle G,s,t\right\rangle\mid G\textrm{ is a directed graph with a Hamilton path from }s\textrm{ to }t\right\}
where a Hamiltonian path is one that must go through every node in the graph.
Show that \textrm{HAMPATH} is in \textbf{NP} using two different methods.
2 I Thought CLIQUE was NP-Complete?
Recall the \textrm{CLIQUE} language:
\textrm{CLIQUE} = \left\{\left\langle G,k\right\rangle\mid G\textrm{ is an undirected graph that has a clique of size } k\right\}
where a clique is a complete subgraph (i.e., every pair of vertices is connected by an edge).
In class, we learned that \textrm{CLIQUE} is not known to have a polynomial time solution and is in fact \textbf{NP}\textrm{-complete}.
However, for any fixed k, the language does have a polynomial time solution.
Prove that the \textrm{3NODES} language is in \textbf{P}, where:
\textrm{3NODES} = \left\{\left\langle G\right\rangle\mid G\textrm{ is an undirected graph containing a complete subgraph with three nodes}\right\}
Prove that if \textbf{P}\neq\textbf{NP}, then \textrm{3NODES} cannot be \textbf{NP}\textrm{-complete}.
3 Maximum CLIQUE
We saw in the I Thought CLIQUE was NP-Complete? problem that finding a fixed size clique is in \textbf{P}.
But the reason why the general clique problem can’t be solved in polynomial time using a similar solution is because k could be in terms of n.
In this problem, we see another example of this.
Prove that the following language is \textbf{NP}\textrm{-complete}:
\textrm{MAXCLIQUE} = \left\{\left\langle G\right\rangle\mid G\textrm{ is an undirected graph that has a clique of size } n/2\right\}
where n is the number of vertices in the graph.
Make sure your solution includes all the required parts of an \textbf{NP}\textrm{-completeness} proof, as described in class.
4 Double Satisfaction
Prove that the following language is \textbf{NP}\textrm{-complete}:
\textrm{TWOSATS} = \left\{\left\langle \phi\right\rangle\mid \phi\textrm{ is a Boolean formula with at least 2 different ways to make it evaluate to TRUE}\right\}
Make sure your solution includes all the required parts, as described in class.