Jump to navigation Jump to search
Transformations and Satisfiability
- 11.1. Give the 3-SAT formula that results from applying the reduction of SAT to 3-SAT for the formula:
- 11.2. Draw the graph that results from the reduction of 3-SAT to vertex cover for the expression
- 11.3. Prove that 4-SAT is NP-hard.
- 11.4. Stingy SAT is the following problem: given a set of clauses (each a disjunction of literals) and an integer , find a satisfying assignment in which at most 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 is satisfiable, but has only one solution . In contrast, has exactly two solutions. Show that Double-SAT is NP-hard.
- 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.
- 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?
- 11.10. An instance of the set cover problem consists of a set of elements, a family of subsets of , and an integer . The question is, does there exist subsets from whose union is ? For example, if and , there does not exist a solution for , but there does for (for example, ). 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 , each of which contains a subset of this year's baseball cards, is it possible to collect all the year's cards by buying packets? For example, if the players are and the packets are
- there does not exist a solution for , but there does for , such as
- 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 and an integer , does contain a spanning tree such that all vertices in the tree have degree at most (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.
- 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 and an integer , does contain a spanning tree whose highest degree vertex is at least ? 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.
Algorithms for Special Cases
Back to Chapter List