NP-Completeness

Transformations and Satisfiability

11.1. Give the 3-SAT formula that results from applying the reduction of SAT to 3-SAT for the formula:

[math]\displaystyle{ (x\or y \or \overline z \or w \or u \or \overline v) \and (\overline x \or \overline y \or z \or \overline w \or u \or v) \and (x \or \overline y \or \overline z \or w \or u \or \overline v)\and (x \or \overline y) }[/math]

Solution

11.2. Draw the graph that results from the reduction of 3-SAT to vertex cover for the expression

[math]\displaystyle{ (x \or \overline y \or z) \and (\overline x \or y \or \overline z) \and(\overline x \or y \or z) \and (x \or \overline y \or \overline x) }[/math]

11.3. Prove that 4-SAT is NP-hard.

Solution

11.4. Stingy SAT is the following problem: given a set of clauses (each a disjunction of literals) and an integer [math]\displaystyle{ k }[/math], find a satisfying assignment in which at most [math]\displaystyle{ k }[/math] variables are true, if such an assignment exists. Prove that stingy SAT is NP-hard.

11.5. The Double SAT problem asks whether a given satisfiability problem has at least two different satisfying assignments. For example, the problem [math]\displaystyle{ {{v1, v2}, {v_1, v_2}, {v_1, v_2}} }[/math] is satisfiable, but has only one solution [math]\displaystyle{ (v_1 =F, v_2 = T) }[/math]. In contrast, [math]\displaystyle{ {{v_1, v_2}, {v_1, v_2}} }[/math] has exactly two solutions. Show that Double-SAT is NP-hard.

Solution

11.6. Suppose we are given a subroutine that can solve the traveling salesman decision problem on page 357 in (say) linear time. Give an efficient algorithm to find the actual TSP tour by making a polynomial number of calls to this subroutine.

11.7. Implement a SAT to 3-SAT reduction that translates satisfiability instances into equivalent 3-SAT instances.

Solution

11.8. Design and implement a backtracking algorithm to test whether a set of clause sets is satisfiable. What criteria can you use to prune this search?

11.9. Implement the vertex cover to satisfiability reduction, and run the resulting clauses through a satisfiability solver code. Does this seem like a practical way to compute things?

Solution

Basic Reductions

11.10. An instance of the set cover problem consists of a set [math]\displaystyle{ X }[/math] of [math]\displaystyle{ n }[/math] elements, a family [math]\displaystyle{ F }[/math] of subsets of [math]\displaystyle{ X }[/math], and an integer [math]\displaystyle{ k }[/math]. The question is, does there exist [math]\displaystyle{ k }[/math] subsets from [math]\displaystyle{ F }[/math] whose union is [math]\displaystyle{ X }[/math]? For example, if [math]\displaystyle{ X = \{1,2,3,4\} }[/math] and [math]\displaystyle{ F = \{ \{1,2\}, \{2,3\}, \{4\}, \{2,4\} \} }[/math], there does not exist a solution for [math]\displaystyle{ k=2 }[/math], but there does for [math]\displaystyle{ k=3 }[/math] (for example, [math]\displaystyle{ \{1,2\}, \{2,3\}, \{4\} }[/math]). Prove that set cover is NP-complete with a reduction from vertex cover.

11.11. The baseball card collector problem is as follows. Given packets [math]\displaystyle{ P_1, \ldots, P_m }[/math], each of which contains a subset of this year's baseball cards, is it possible to collect all the year's cards by buying [math]\displaystyle{ \leq k }[/math] packets? For example, if the players are [math]\displaystyle{ \{Aaron, Mays, Ruth, Steven \} }[/math] and the packets are

[math]\displaystyle{ \{ \{Aaron,Mays\}, \{Mays,Ruth\}, \{Steven\}, \{Mays,Steven\} \}, }[/math]

there does not exist a solution for [math]\displaystyle{ k=2 }[/math], but there does for [math]\displaystyle{ k=3 }[/math], such as

[math]\displaystyle{ \{Aaron,Mays\}, \{Mays,Ruth\}, \{Steven\} }[/math]

Prove that the baseball card collector problem is NP hard using a reduction from vertex cover.

11.12. The low-degree spanning tree problem is as follows. Given a graph [math]\displaystyle{ G }[/math] and an integer [math]\displaystyle{ k }[/math], does [math]\displaystyle{ G }[/math] contain a spanning tree such that all vertices in the tree have degree at most [math]\displaystyle{ k }[/math] (obviously, only tree edges count towards the degree)? For example, in the following graph, there is no spanning tree such that all vertices have a degree less than three.

\fixedfigsize{pictures/lowdegree.png}{1.0in}

Prove that the low-degree spanning tree problem is NP-hard with a reduction from Hamiltonian path.
Now consider the high-degree spanning tree problem, which is as follows. Given a graph [math]\displaystyle{ G }[/math] and an integer [math]\displaystyle{ k }[/math], does [math]\displaystyle{ G }[/math] contain a spanning tree whose highest degree vertex is at least [math]\displaystyle{ k }[/math]? In the previous example, there exists a spanning tree with a highest degree of 8. Give an efficient algorithm to solve the high-degree spanning tree problem, and an analysis of its time complexity.

11.14

11.16

11.18

11.20