NP-Hardness
Prev: Applications of Flows and Cuts
Exercises
1.
(a) Describe and analyze an algorithm to solve Partition in time , where is the size of the input set and is the sum of the absolute values of its elements. (b) Why doesn’t this algorithm imply that ?
2.
Consider the following problem, called BoxDepth: Given a set of axis-aligned rectangles in the plane, how big is the largest subset of these rectangles that contain a common point? (a) Describe a polynomial-time reduction from BoxDepth to MaxClique. (b) Describe and analyze a polynomial-time algorithm for BoxDepth. [Hint: time should be easy, but time is possible.] (c) Why don’t these two results imply that ?
3.
A boolean formula is in disjunctive normal form (or DNF) if it consists of a disjunction (Or) or several terms, each of which is the conjunction (And) of one or more literals. For example, the formula (x ∧ y ∧ z) ∨ (y ∧ z) ∨ (x ∧ y ∧ z) is in disjunctive normal form. DNF-Sat asks, given a boolean formula in disjunctive normal form, whether that formula is satisfiable. (a) Describe a polynomial-time algorithm to solve DNF-Sat. (b) What is the error in the following argument that ? Suppose we are given a boolean formula in conjunctive normal form with at most three literals per clause, and we want to know if it is satisfiable. We can use the distributive law to construct an equivalent formula in disjunctive normal form. For example, (x ∨ y ∨ z) ∧ (x ∨ y) ⇐⇒ (x ∧ y) ∨ (y ∧ x) ∨ (z ∧ x) ∨ (z ∧ y) Now we can use the algorithm from part (a) to determine, in polynomial time, whether the resulting DNF formula is satisfiable. We have just solved 3SAT in polynomial time. Since 3SAT is NP-hard, we must conclude that !
4.
The problem AllOrNothing3Sat asks, given a 3CNF boolean formula, whether there is an assignment to the variables such that each clause either has three True literals or has three False literals. (a) Describe a polynomial-time algorithm to solve AllOrNothing3Sat. (b) But 3Sat is NP-hard! Why doesn’t the existence of this algorithm prove that ?
5.
(a) Suppose you are given a magic black box that can determine in polynomial time, given an arbitrary weighted graph G, the length of the shortest Hamiltonian cycle in G. Describe and analyze a polynomialtime algorithm that computes, given an arbitrary weighted graph G, the shortest Hamiltonian cycle in G, using this magic black box as a subroutine. (b) Suppose you are given a magic black box that can determine in polynomial time, given an arbitrary graph G, the number of vertices in the largest complete subgraph of G. Describe and analyze a polynomialtime algorithm that computes, given an arbitrary graph G, a complete subgraph of G of maximum size, using this magic black box as a subroutine. (c) Suppose you are given a magic black box that can determine in polynomial time, given an arbitrary graph G, whether G is 3-colorable. Describe and analyze a polynomial-time algorithm that either computes a proper 3-coloring of a given graph or correctly reports that no such coloring exists, using the magic black box as a subroutine. [Hint: The input to the magic black box is a graph. Only a graph. Vertices and edges. Nothing else.] (d) Suppose you are given a magic black box that can determine in polynomial time, given an arbitrary boolean formula Φ, whether Φ is satisfiable. Describe and analyze a polynomial-time algorithm that either computes a satisfying assignment for a given boolean formula or correctly reports that no such assignment exists, using the magic black box as a subroutine. (e) Suppose you are given a magic black box that can determine in polynomial time, given an arbitrary set of positive integers, whether can be partitioned into two sets and such that . Describe and analyze a polynomial-time algorithm that either computes an equal partition of a given set of positive integers or correctly reports that no such partition exists, using the magic black box as a subroutine. (f) Suppose you are given a magic black box that can determine in polynomial time, given an arbitrary generalized regular expression R (as defined just before the Exercises), whether R matches any string. Describe and analyze a polynomial-time algorithm that either finds a single string that matches a given generalized regular expression or correctly reports that no such string exists, using the magic black box as a subroutine.
6.
There’s something special about the number 3. (a) Describe and analyze a polynomial-time algorithm for 2Partition. Given a set S of 2n positive integers, your algorithm will determine in polynomial time whether the elements of S can be split into n disjoint pairs whose sums are all equal. (b) Describe and analyze a polynomial-time algorithm for 2Color. Given an undirected graph G, your algorithm will determine in polynomial time whether G has a proper coloring that uses only two colors. (c) Describe and analyze a polynomial-time algorithm for 2Sat. Given a boolean formula Φ in conjunctive normal form, with exactly two literals per clause, your algorithm will determine in polynomial time whether Φ has a satisfying assignment. [Hint: This problem is strongly connected to topics described in an earlier chapter.]
7.
There’s nothing special about the number 3. (a) The problem 12Partition is defined as follows: Given a set S of 12n positive integers, determine whether the elements of S can be split into n subsets, each with 12 elements, whose sums are all equal. Prove that 12Partition is NP-hard. [Hint: Reduce from 3Partition. It may be easier to consider multisets first.] (b) The problem 12Color is defined as follows: Given an undirected graph G, determine whether we can color each vertex with one of twelve colors, so that every edge touches two different colors. Prove that 12Color is NP-hard. [Hint: Reduce from 3Color.] (c) The problem 12SAT is defined as follows: Given a boolean formula Φ in conjunctive normal form, with exactly twelve literals per clause, determine whether Φ has a satisfying assignment. Prove that 12Sat is NP-hard. [Hint: Reduce from 3Sat.]
8.
There are two different versions of the Hamiltonian cycle problem, one for directed graphs and one for undirected graphs. Earlier in this chapter you can find two proofs that the directed Hamiltonian cycle problem is NP-hard. (a) Describe a polynomial-time reduction from the undirected Hamiltonian cycle problem to the directed Hamiltonian cycle problem. Prove your reduction is correct. (b) Describe a polynomial-time reduction from the directed Hamiltonian cycle problem to the undirected Hamiltonian cycle problem. Prove your reduction is correct. (c) Which of these two reductions implies that the undirected Hamiltonian cycle problem is NP-hard?
9.
(a) Describe a polynomial-time reduction from UndirectedHamiltonianCycle to DirectedHamiltonianCycle. (b) Describe a polynomial-time reduction from DirectedHamiltonianCycle to UndirectedHamiltonianCycle.
10.
(a) Describe a polynomial-time reduction from the HamiltonianPath problem to HamiltonianCycle. (b) Describe a polynomial-time reduction from the HamiltonianCycle problem to HamiltonianPath. [Hint: A polynomial-time reduction can call the black-box subroutine more than once, but it doesn’t have to.]
11.
Consider the following subtle variants of CNFSat. For each problem, the input is a boolean formula Φ in conjunctive normal form, and the goal is to determine whether Φ has a satisfying assignment. (a) Suppose every clause of Φ contains at most three literals and each variable appears in at most three clauses. Prove that this variant of CNFSat is NP-hard. (b) Suppose every clause of Φ contains exactly three literals and each variable appears in at most four clauses. Prove that this variant of 3Sat is NP-hard. [Hint: Solve part (a) first.] (c) Suppose every clause of Φ can contain any number of literals, but each variable appears in at most two clauses. Describe a polynomial-time algorithm for this variant of CNFSat. (d) Suppose every clause of Φ contains exactly three literals and each variable appears in at most three clauses. Prove that Φ must be satisfiable. (So this variant of 3Sat is completely trivial!)
12.
(a) Prove that NotAllEqual3Sat is NP-hard. (b) Prove that 1-in-3Sat is NP-hard.
13.
A boolean formula in exclusive-or conjunctive normal form (XCNF) is a conjunction (And) of several clauses, each of which is the exclusive-or of several literals; that is, a clause is true if and only if it contains an odd number of true literals. The XCNF-Sat problem asks whether a given XCNF formula is satisfiable. Either describe a polynomial-time algorithm for XCNF-Sat or prove that XCNF-Sat is NP-hard. [Hint: Do not try to do both.]
14.
Consider the following variant of 3Sat, called Majority3Sat. Just like 3Sat, the input to Majority3Sat is a boolean formula Φ in conjunctive normal form, with exactly three literals per clause. Majority3Sat asks whether there is an assignment to the variables of Φ, such that every clause contains at least two True literals. Either describe an algorithm that solves Majority3Sat in polynomial time or prove that Majority3Sat is NP-hard. [Hint: Do not try to do both.]
15.
For any subset X \subseteq {0, 1, 2, 3}, consider the following problem, which I’ll call X-3Sat. The input is a boolean formula Φ in conjunctive normal form, with exactly three literals in each clause. The problem is to decide whether there is an assignment to the variables of Φ such that in each clause of Φ, the number of True literals is in the set X. For example: • {1, 2, 3}-3Sat is the standard 3Sat problem. • {0, 3}-3Sat is the same as AllOrNothing3Sat. (See Exercise 4.) • {1, 2}-3Sat is usually called NotAllEqual3Sat. (See Exercise 12(a).) • {1}-3Sat is usually called 1-in-3Sat. (See Exercise 12(b).) • {1, 3}-3Sat is usually called XCNF-3Sat. (See Exercise 13.) • {2, 3}-3Sat is usually called Majority3Sat. (See Exercise 14.) Give a complete list of all subsets such that X-3Sat is solvable in polynomial time, assuming P \ne NP. [Hint: Don’t give 16 different arguments.]
16.
Prove that the following problems are NP-hard. (a) Given an undirected graph G, does G contain a simple path that visits all but 17 vertices? (b) Given an undirected graph G, does G have a spanning tree in which every node has degree at most 23? (c) Given an undirected graph G, does G have a spanning tree with at most 42 leaves? (d) Given an undirected graph , what is the size of the largest subset of vertices S \subseteq V such that at most 374 edges in E have both endpoints in S? (e) Given an undirected graph , what is the size of the largest subset of vertices S \subseteq V such that each vertex in S has at most 473 neighbors in S? (f) Given an undirected graph G, is it possible to color the vertices of G with three different colors, so that at most 31337 edges have both endpoints the same color?
17.
Prove that the following variants of the minimum spanning tree problem are NP-hard.
(a) Given a graph G, compute the maximum-diameter spanning tree of G. (The diameter of a tree T is the length of the longest path in T.)
(b) Given a graph G with weighted edges, compute the minimum-weight depth-first spanning tree of G.
(c) Given a graph G with weighted edges and a subset S of vertices of G, compute the minimum-weight spanning tree all of whose leaves are in S.
(d) Given a graph G with weighted edges and an integer , compute the minimum-weight spanning tree with at most leaves.
(e) Given a graph G with weighted edges and an integer ∆, compute the minimum-weight spanning tree where every node has degree at most ∆.
18.
(a) Using the gadget in Figure 12.26(a), prove that deciding whether a given planar graph is 3-colorable is NP-hard. [Hint: Show that the gadget can be 3-colored, and then replace any crossings in a planar embedding with the gadget appropriately.] (b) Using part (a) and the gadget in Figure 12.26(b), prove that deciding whether a planar graph with maximum degree 4 is 3-colorable is NP-hard. [Hint: Replace any vertex with degree greater than 4 with a collection of gadgets connected so that no degree is greater than four.]
19.
Prove that PlanarCircuitSat is NP-hard. [Hint: Construct a gadget for crossing wires.]
20.
(a) Describe a polynomial-time reduction from 3Sat to 4Sat. (b) Describe a polynomial-time reduction from 4Sat to 3Sat.
21.
Describe a direct polynomial-time reduction from 4Color to 3Color. (This is a lot harder than the opposite direction.)
22.
A domino is a 1 × 2 rectangle divided into two squares, each of which is labeled with an integer.29 In a legal arrangement of dominos, the dominos are lined up end-to-end so that the numbers on adjacent ends match.
For each of the following problems, either describe a polynomial-time algorithm or prove that the problem is NP-hard: (a) Given an arbitrary bag D of dominos, is there a legal arrangement of all the dominos in D? (b) Given an arbitrary bag D of dominos, is there a legal arrangement of a dominos from D in which every integer between 1 and n appears exactly twice?
These integers are usually represented by pips, exactly like dice. On a standard domino, the number of pips on each side is between 0 and 6, although one can buy sets with up to 9 or even 12 pips on each side; we will allow arbitrary integer labels. A standard set of dominos contains exactly one domino for each possible unordered pair of labels; we do not assume that the inputs to our problems have this property. (c) Given an arbitrary bag D of dominos, what is the largest number of dominos we can take from D to make a legal arrangement?
23.
Pebbling is a solitaire game played on an undirected graph G, where each vertex has zero or more pebbles. A single pebbling move consists of removing two pebbles from a vertex v and adding one pebble to an arbitrary neighbor of v. (Obviously, the vertex v must have at least two pebbles before the move.) The PebbleDestruction problem asks, given a graph and a pebble count p(v) for each vertex v, whether is there a sequence of pebbling moves that removes all but one pebble. Prove that PebbleDestruction is NP-hard.
24.
Recall that a 5-coloring of a graph G is a function that assigns each vertex of G a “color” from the set {0, 1, 2, 3, 4}, such that for any edge uv, vertices u and v are assigned different “colors”. A 5-coloring is careful if the colors assigned to adjacent vertices are not only distinct, but differ by more than 1 (mod 5). Prove that deciding whether a given graph has a careful 5-coloring is NP-hard. [Hint: Reduce from the standard 5Color problem.]
25.
(a) A subset S of vertices in an undirected graph G is half-independent if each vertex in S is adjacent to at most one other vertex in S. Prove that finding the size of the largest half-independent set of vertices in a given undirected graph is NP-hard. (b) A subset S of vertices in an undirected graph G is sort-of-independent if if each vertex in S is adjacent to at most 374 other vertices in S. Prove that finding the size of the largest sort-of-independent set of vertices in a given undirected graph is NP-hard. (c) A subset S of vertices in an undirected graph G is almost independent if at most 374 edges in G have both endpoints in S. Prove that finding the size of the largest almost-independent set of vertices in a given undirected graph is NP-hard.
26.
Let be a graph. A dominating set in G is a subset S of the vertices such that every vertex in G is either in S or adjacent to a vertex in S. The DominatingSet problem asks, given a graph G and an integer k as input, whether G contains a dominating set of size k. Prove that this problem is NP-hard.
27.
A subset S of vertices in an undirected graph G is triangle-free if, for every triple of vertices u, v, w \in S, at least one of the three edges uv, uw, vw is absent from G. Prove that finding the size of the largest triangle-free subset of vertices in a given undirected graph is NP-hard.
28.
The RectangleTiling problem is defined as follows: Given one large rectangle and several smaller rectangles, determine whether the smaller rectangles can be placed inside the large rectangle with no gaps or overlaps. (a) Prove that RectangleTiling is NP-hard. (b) Prove that RectangleTiling is strongly NP-hard.
29.
(a) A subset B of vertices in a graph G is a Burr set if removing every vertex in B from G leaves a subgraph that does not contain a Hamiltonian path. Prove that finding the smallest Burr set in a given graph is NP-hard. (b) A subset S of vertices in a graph G is a Schuyler set if removing every vertex in S from G leaves a subgraph that does contain a Hamiltonian path. Prove that finding the smallest Schuyler set in a given graph is NP-hard.
30.
(a) A tonian path in a graph G is a path that goes through at least half of the vertices of G. Show that determining whether a graph has a tonian path is NP-hard. (b) A tonian cycle in a graph G is a cycle that goes through at least half of the vertices of G. Show that determining whether a graph has a tonian cycle is NP-hard. [Hint: Use part (a). Or not.]
31.
Let G be an undirected graph with weighted edges. A heavy Hamiltonian cycle is a cycle C that passes through each vertex of G exactly once, such that the total weight of the edges in C is more than half of the total weight of all edges in G. Prove that deciding whether a graph has a heavy Hamiltonian cycle is NP-hard.
32.
For each of the following problems, either describe a polynomial-time algorithm or prove that the problem is NP-hard. (a) A double-Eulerian tour in an undirected graph G is a closed walk that traverses every edge in G exactly twice. Given a graph G, does G have a double-Eulerian tour? (b) A double-Hamiltonian tour in an undirected graph G is a closed walk that visits every vertex in G exactly twice. Given a graph G, does G have a double-Hamiltonian tour? (c) A double-Hamiltonian circuit in an undirected graph G is a closed walk that visits every vertex in G exactly twice and traverses each edge in G at most once. Given a graph G, does G have a double-Hamiltonian circuit? (d) A triple-Eulerian tour in an undirected graph G is a closed walk that traverses every edge in G exactly three times. Given a graph G, does G have a triple-Eulerian tour? (e) A triple-Hamiltonian tour in an undirected graph G is a closed walk that visits every vertex in G exactly three times. Given a graph G, does G have a triple-Hamiltonian tour?
33.
This exercise asks you to prove that a certain reduction from VertexCover to SteinerTree is correct. Suppose we want to find the smallest vertex cover in a given undirected graph . We construct a new graph as follows: • • . Equivalently, we construct H by subdividing each edge in G with a new vertex, and then connecting all the original vertices of G to a new apex vertex z. Prove that G has a vertex cover of size k if and only if there is a subtree of H with k + |E| + 1 vertices that contains every vertex in .
34.
Consider the following solitaire game. The puzzle consists of an n × m grid of squares, where each square may be empty, occupied by a red stone, or occupied by a blue stone. The goal of the puzzle is to remove some of the given stones so that the remaining stones satisfy two conditions: (1) every row contains at least one stone, and (2) no column contains stones of both colors. For some initial configurations of stones, reaching this goal is impossible.
A solvable puzzle and one of its many solutions.
An unsolvable puzzle.
Prove that it is NP-hard to determine, given an initial configuration of red and blue stones, whether the puzzle can be solved.
35.
Each of the following games involves an n × m grid of squares, where each square is either empty or occupied by a stone. In a single move, you can remove all the stones in an arbitrary column. (a) Prove that it is NP-hard to find the smallest subset of columns that can be cleared so that at most one stone remains in each row of the grid. (b) Prove that it is NP-hard to find the largest subset of columns that can be cleared so that at least one stone remains in each row of the grid. (c) Prove that it is NP-hard to determine whether any subset of columns can be cleared so that exactly one stone remains in each row of the grid.
36.
Jeff tries to make his students happy. At the beginning of class, he passes out a questionnaire that lists a number of possible course policies in areas where he is flexible. Every student is asked to respond to each possible course policy with one of “strongly favor”, “mostly neutral”, or “strongly oppose”. Each student may respond with “strongly favor” or “strongly oppose” to at most five questions. Because Jeff’s students are very understanding, each student is happy if (but only if) he or she prevails in at least one of their strong policy preferences. Either describe a polynomial-time algorithm for setting course policy to maximize the number of happy students, or show that the problem is NP-hard.
37.
You’re in charge of choreographing a musical for your local community theater, and it’s time to figure out the final pose of the big show-stopping number at the end. (“Streetcar!”) You’ve decided that each of the n cast members in the show will be positioned in a big line when the song finishes, all with their arms extended and showing off their best spirit fingers. The director has declared that during the final flourish, each cast member must either point both their arms up or point both their arms down; it’s your job to figure out who points up and who points down. Moreover, the director has also given you a list of arrangements that will upset his delicate artistic temperament. Each forbidden arrangement is a subset of the cast members paired with arm positions; for example: “Marge may not point her arms up while Ned, Apu, and Smithers point their arms down.” Prove that finding an acceptable arrangement of arm positions is NP-hard.
38.
The next time you are at a party, one of the guests will suggest everyone play a round of Three-Way Mumbletypeg, a game of skill and dexterity that requires three teams and a knife. The official Rules of Three-Way Mumbletypeg (fixed during the Holy Roman Three-Way Mumbletypeg Council in 1625) require that (1) each team must have at least one person, (2) any two people on the same team must know each other, and (3) everyone watching the game must be on one of the three teams. Of course, it will be a really fun party; nobody will want to leave. There will be several pairs of people at the party who don’t know each other. The host of the party, having heard thrilling tales of your prowess in all things algorithmic, will hand you a list of which pairs of party-goers know each other and ask you to choose the teams, while he sharpens the knife.
Either describe and analyze a polynomial time algorithm to determine whether the party-goers can be split into three legal Three-Way Mumbletypeg teams, or prove that the problem is NP-hard.
39.
The party you are attending is going great, but now it’s time to line up for The Algorithm March (アルゴリズムこうしん)! This dance was originally developed by the Japanese comedy duo Itsumo Kokokara (いつもここから) for the children’s television show PythagoraSwitch (ピタゴラスイッチ). The Algorithm March is performed by a line of people; each person in line starts a specific sequence of movements one measure later than the person directly in front of them. Thus, the march is the dance equivalent of a musical round or canon, like “Row Row Row Your Boat” or “Frère Jacques”. Proper etiquette dictates that each marcher must know the person directly in front of them in line, lest a minor mistake lead to horrible embarrassment between strangers. Suppose you are given a complete list of which people at your party know each other. Prove that it is NP-hard to determine the largest number of party-goers that can participate in the Algorithm March. You may assume without loss of generality that there are no ninjas at your party.
40.
Prove that the following problems about nondeterministic finite-state automata and regular expressions are NP-hard: (a) Given an NFA M over the alphabet Σ = {0, 1}, is there a string in Σ∗ that M does not accept? (b) Given an acyclic NFA M over the alphabet Σ = {0, 1}, what is the length of the shortest string in Σ∗ that M does not accept? (c) Given a regular expression R over the alphabet Σ = {0, 1}, is there a string in Σ∗ that R does not match? (d) Given a star-free regular expression R over the alphabet Σ = {0, 1}, what is the length of the shortest string in Σ∗ that R does not match? (In fact, problems (a) and (c) are PSPACE-complete; even proving that these problems are in PSPACE is nontrivial.)
41.
(a) Describe a polynomial-time algorithm for the following problem: Given an NFA M over the alphabet Σ = {0, 1}, is there a string in Σ∗ that M does accept? (b) Describe a polynomial-time algorithm for the following problem: Given a regular expression R over the alphabet Σ = {0, 1}, is there a string in Σ∗ that R does match? (c) The complement of any regular language is another regular language. So why don’t these two algorithms, together with the NP-hardness results in Problem 40, prove that ?
42.
Charon needs to ferry n recently deceased people across the river Acheron into Hades. Certain pairs of these people are sworn enemies, who cannot be together on either side of the river unless Charon is also present. (If two enemies are left alone, one will steal the obol from the other’s mouth, leaving them to wander the banks of the Acheron as a ghost for all eternity. Let’s just say this is a Very Bad Thing.) The ferry can hold at most k passengers at a time, including Charon, and only Charon can pilot the ferry.30 Prove that it is NP-hard to decide whether Charon can ferry all n people across the Acheron unharmed (aside from being, you know, dead). The input for Charon’s problem consists of the integers k and n and an n-vertex graph G describing the pairs of enemies. The output is either True or False. Please do not write your solution in classical Latin.