For problems F1 to problem F3 you are to provide three things:
==================================================
a. Formulate the decision problem as a language membership problem (i.e.,describe the language L corresponding to the decision problem). You may assume that there is a standard way to encode graphs and their vertices and edges as strings.
b. Sketch a proof that this language is in NP.
c. State what else would need to be proven in order to show the language NP-complete (but do not prove).
==================================================
An example (HAMILTONIAN PATH) for parts a and b is provided as reference.
The HAMILTONIAN PATH problem is the problem of recognizing, given a graph G=(V,E) as input, whether or not there is a tour of the
nodes of the graph that visits each node exactly once. I.e., is there an ordering of the vertices of G, where n=|V|,
such that (v_i,v_(i+1))in E for all i, 1<=i
a. The language corresponding to this decision problem is:
HAMILTONIAN_PATH={| G has a hamiltonian path}. Here, is the string encoding of the graph G.
b. Here is a non-deterministic polynomial algorithm description for the HAMILTONIAN PATH problem, where n is the number of nodes in the graph:
Guess a sequence s of n nodes. (runtime n log n) Check if the sequence s has any node twice. (runtime < n^2) Check if each pair of consecutive nodes in (runtime n * graph arc lookup) sequence s is connected in the graph.
Fail if either check failed, otherwise YES, there is a Hamiltonian path.
Note: The runtime of the n guesses is n log n because each guess of a node involves guessing log n bits (it takes log n bits to
code which node is being guessed).
The existence of this algorithm shows that HAMILTONIAN PATH is in NP.
F1. (3-COLORING) "3-COLORING" is the problem of, given three colors and a binary relation R on a set V of "nodes", can we assign colors to nodes so that no pair of nodes connected by R has the same color.
F2. (k-INDEPENDENT) Given a graph G, an independent set is a subset X of the vertices of G such that no pair of vertices in X is connected by an edge in G. The k-INDEPENDENT-SET decision problem is defined as follows:
Given: an undirected graph G and an integer k Question: Does G contain an independent set of size at least k?
F3. (VERTEX-COVER) Given a graph G=(V, E), and integer k <= |V|, is there a subset of at most k vertices such that every edge in E has at least one vertex in the subset?
F4. Suppose we have problems P1 and P2. Suppose there is a polynomial-time reduction from P1 to P2.
a. What can we say about the existence of an efficient algorithm for deciding P1 if there is an efficient algorithm deciding P2?
b. Can we say the same thing about an efficient algorithm for deciding P2 if there is an efficient algorithm deciding P1?
(Here an efficient algorithm is one that runs in polynomial-time in the size of its input).
F5. Suppose you are considering the difficulty of deciding some language that comes up in a problem you are working on. Suppose
you decide to try to show that the new language is NP-complete.
Explain why Cook's theorem would be useful.