# Chapter 11

Jump to navigation
Jump to search

## Contents

# 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:
**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\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) }**

- 11.2. Draw the graph that results from the reduction of 3-SAT to vertex cover for the expression
**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\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) }**

- 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**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle k}**, find a satisfying assignment in which at most**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle k}**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**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{v1, v2}, {v_1, v_2}, {v_1, v_2}}}**is satisfiable, but has only one solution**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (v_1 =F, v_2 = T)}**. In contrast,**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{v_1, v_2}, {v_1, v_2}}}**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?

### Basic Reductions

- 11.10. An instance of the
*set cover*problem consists of a set**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle X}**of**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle n}**elements, a family**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle F}**of subsets of**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle X}**, and an integer**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle k}**. The question is, does there exist**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle F}**whose union is**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle X}**? For example, if**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle X = \{1,2,3,4\}}**and**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle F = \{ \{1,2\}, \{2,3\}, \{4\}, \{2,4\} \}}**, there does not exist a solution for**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle k=2}**, but there does for**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle k=3}**(for example,**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \{1,2\}, \{2,3\}, \{4\}}**). 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**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle P_1, \ldots, P_m}**, each of which contains a subset of this year's baseball cards, is it possible to collect all the year's cards by buying**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \leq k}**packets? For example, if the players are**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \{Aaron, Mays, Ruth, Steven \} }**and the packets are**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \{ \{Aaron,Mays\}, \{Mays,Ruth\}, \{Steven\}, \{Mays,Steven\} \}, }**

- there does not exist a solution for
**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle k=2}**, but there does for**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle k=3}**, such as**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \{Aaron,Mays\}, \{Mays,Ruth\}, \{Steven\} }**

- 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**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle G}**and an integer**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle G}**contain a spanning tree such that all vertices in the tree have degree*at most*

\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**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle G}**and an integer*at least*

- 11.13.In the minimum element set cover problem, we seek a set cover
**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle S \subseteq C}**of a universal set**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle U = {1, . . . , n}}**such that sum of the sizes of the subsets in**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle S}**is at most- (a) Show that
**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle C = {{1, 2, 3}, {1, 3, 4}, {2, 3, 4}, {3, 4, 5}}}**has a cover of size 6, but none of size 5 because of a repeated element. - (b) Prove that this problem is NP-hard. (Hint: set cover remains hard if all subsets are of the same size.)

- (a) Show that

- 11.14. The
*half-Hamiltonian cycle problem*is, given a graph**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle n}**vertices, determine whether**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle [n/2]}**, where the floor function rounds its input down to the nearest integer. Prove that this problem is NP-hard.

- 11.15. The 3-phase power balance problem asks for a way to partition a set of n positive integers into three sets
**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle A}**,**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle B}**, or**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle C}**such that**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \sum_{i} a_i = \sum_{i} b_i = \sum_{i} c_i}**. Prove that this problem is NP-hard using a reduction from integer partition or subset sum (see Section 10.5 (page 329)).

- 11.16. Show that the following problem is NP-complete:
*Problem:*Dense subgraph*Input:*A graph**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle y}**.*Output:*Does**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle y}**edges?

- 11.17. Show that the following problem is NP-complete:
*Problem:*Clique, no-clique*Input:*An undirected graph**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle G=(V,E)}**and an integer*Output:*Does

- 11.18. n
*Eulerian cycle*is a tour that visits every edge in a graph exactly once. An*Eulerian subgraph*is a subset of the edges and vertices of a graph that has an Eulerian cycle. Prove that the problem of finding the number of edges in the largest Eulerian subgraph of a graph is NP-hard. (Hint: the Hamiltonian circuit problem is NP-hard even if each vertex in the graph is incident upon exactly three edges.)

- 11.19. Show that the following problem is NP-hard:
*Problem:*Maximum Common Subgraph*Input:*Two graphs**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle G_1 = (V_1, E_1)}**and**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle G_2 = (V_2, E_2)}**, and a budget**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle b}**.- Output: Two sets of nodes
**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle S_1 \subseteq V_1}**and**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle S_2 \subseteq V_2}**whose deletion leaves at least**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle b}**nodes in each graph, and makes the two graphs identical.

- 11.20. A
*strongly independent*set is a subset of vertices**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle S}**in a graph**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle S}**, there is no path of length two in

- 11.21. A
*kite*is a graph on an even number of vertices, say**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 2n}**, in which**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle n}**of the vertices form a clique and the remaining*max kite*problem asks for a subgraph that is a kite and contains**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 2g}**nodes. Prove that*max kite*is NP-hard.

### Creative Reductions

- 11.22. Prove that the following problem is NP-complete:
*Problem:*Hitting Set*Input:*A collection**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle C}**of subsets of a set*Output:*Does**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle S'}**such that**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle |S'| \leq k}**and each subset in**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle C}**contains at least one element from**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle S'}**?

- 11.23. Prove that the following problem is NP-complete:
*Problem:*Knapsack*Input:*A set**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle i}**th item has value**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle v_i}**and weight**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle w_i}**. Two positive integers: weight limit**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle W}**and value requirement**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle V}**.*Output:*Does there exist a subset**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle S' \in S}**such that**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \sum_{i \in S'} w_i \leq W}**and**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \sum_{i \in S'} v_i \geq V}**?

- (Hint: start from integer partition.)

- 11.24. Prove that the following problem is NP-complete:
*Problem:*Hamiltonian Path*Input:*A graph**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle s}**and**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle t}**.*Output:*Does**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle s}**, ends at**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle t}**, and visits all vertices without visiting any vertex more than once? (Hint: start from Hamiltonian cycle.)

- 11.25. Prove that the following problem is NP-complete:
*Problem:*Longest Path*Input:*A graph*Output:*Does

- 11.26. Prove that the following problem is NP-complete:
*Problem:*Dominating Set*Input:*A graph and positive integer .*Output:*Is there a subset such that where for each vertex either or there exists an edge , where .

- 11.27. Prove that the vertex cover problem (does there exist a subset of vertices in a graph such that every edge in is incident upon at least one vertex in ?) remains NP-complete even when all the vertices in the graph are restricted to have even degrees.

- 11.28. Prove that the following problem is NP-complete:
*Problem:*Set Packing*Input:*A collection of subsets of a set , positive integer .*Output:*Does contain at least disjoint subsets (i.e., such that none of these subsets have any elements in common?)

- 11.29. Prove that the following problem is NP-complete:
*Problem:*Feedback Vertex Set*Input:*A directed graph and positive integer .*Output:*Is there a subset such that , such that deleting the vertices of from leaves a DAG?

- 11.30. Give a reduction from Sudoku to the vertex coloring problem in graphs. Specifically, describe how to take any partially filled Sudoku board and construct a graph that can be colored with nine colors iff the Sudoku board is solvable.

### Algorithms for Special Cases

- 11.31. A Hamiltonian path is a path that visits each vertex exactly once. The problem of testing whether a graph contains a Hamiltonian path is NP-complete. There does not have to be an edge in from the ending vertex to the starting vertex of , unlike in the Hamiltonian cycle problem. Give an -time algorithm to test whether a directed acyclic graph (a DAG) contains a Hamiltonian path. (Hint: think about topological sorting and DFS.)

- 11.32. Consider the
*k*-clique problem, which is the general clique problem restricted to graphs in which every vertex has degree at most . Prove that*k*-clique has an efficient algorithm for any given , meaning that is a constant.

- 11.33. The -SAT problem is, given a Boolean formula in 2-conjunctive normal form (CNF), to decide whether the formula is satisfiable. -SAT is like -SAT, except that each clause can have only two literals. For example, the following formula is in -CNF:
- Give a polynomial-time algorithm to solve -SAT.

- 11.34, Show that the following problems are in NP:

- Does graph have a simple path (i.e., with no vertex repeated) of length ? \#Is integer composite (i.e., not prime)?
- Does graph have a vertex cover of size ?

- 11.35. Until 2002, it was an open question whether the decision problem
*Is integer a composite number, in other words, not prime?*can be computed in time polynomial in the size of its input. Why doesn't the following algorithm suffice to prove it is in P, since it runs in time?

PrimalityTesting() composite := for i := 2 to do if then composite :=

Back to Chapter List