CSCI 570 – Summer 2020 – HW 6
Due August 10th
1 Graded Problems
1. State True/False.
• Assume P . Let A and B be decision problems. If A ∈ NPC and
A ≤p B, then B.
• If someone proves P = NP , then it would imply that every decision
problem can be solved in polynomial time.
2. Given an n bit positive integer, the problem is to decide if it is composite.
Here the problem size is n. Is this decision problem in NP?
3. State True/False. Assume you have an algorithm that given a 3-SAT
instance, decides in polynomial time if it has a satisfying assignment.
Then you can build a polynomial time algorithm that finds a satisfying
assignment(if it exists) to a given 3-SAT instance.
4. A variation of the satisfiability problem is the MIN 2-SAT problem. The
goal in the MIN 2-SAT problem is to find a truth assignment that mini-
mizes the number of satisfied clauses. Give the best approximation algo-
rithm that you can find for the problem.
5. Assume that you are given a polynomial time algorithm that decides if a
directed graph contains a Hamiltonian cycle. Describe a polynomial time
algorithm that given a directed graph that contains a Hamiltonian cycle,
lists a sequence of vertices (in order) that forms a Hamiltonian cycle.
6. State True/False. Let A be NP -complete, and B be NP -hard. Then,
A ≤p B.
7. State True/False. If P = NP , then every NP -hard problem can be solved
in polynomial time.
1
2 Practice Problems
1. Show that vertex cover remains NP -Complete even if the instances are
restricted to graphs with only even degree vertices.
2. Given an undirected graph with positive edge weights, the BIG-HAM –
CYCLE problem is to decide if it contains a Hamiltonian cycle C such that
the sum of weights of edges in C is at least half of the total sum of weights
of edges in the graph. Show that BIG-HAM -CYCLE is NP-complete.
You are allowed to use the fact that deciding if an undirected graph has
a Hamiltonian cycle is NP-complete.
2