Text Book - Algorithm Design by Jon Kleinberg and Eva Tardos

Chapter 10 - Extending the Limits of Tractability

Exercises

Q1. In Exercise 5 of Chapter 8, we claimed that the Hitting Set Problem was NP-complete. To recap the definitions, consider a set A = {a₁,..., a_n} and a collection B₁, B₂,..., B_m of subsets of A. We say that a set H ⊆ A is a hitting set for the collection B₁, B₂,..., B_m if H contains at least one element from each B_i -that is, if H ∩ B_i is not empty for each i. (So H "hits" all the sets B_i.)

Now suppose we are given an instance of this problem, and we'd like to determine whether there is a hitting set for the collection of size at most k. Furthermore suppose that each set B_i has at most c elements, for a constant c. Give an algorithm that solves this problem with a running time of the form O(f (c, k) · p(n, m)), where p(·) is a polynomial function, and f (·) is an arbitrary function that depends only on c and k, not on n or m.

Q2. The difficulty in 3-SAT comes from the fact that there are 2n possible assignments to the input variables x₁, x₂,..., x_n, and there's no apparent way to search this space in polynomial time. This intuitive picture, however, might create the misleading impression that the fastest algorithms for 3-SAT actually require time 2n. In fact, though it's somewhat counter-intuitive when you first hear it, there are algorithms for 3-SAT that run in significantly less than 2n time in the worst case; in other words, they determine whether there's a satisfying assignment in less time than it would take to enumerate all possible settings of the variables.

Here we'll develop one such algorithm, which solves instances of 3-SAT in O(p(n) · (√3)ⁿ) time for some polynomial p(n). Note that the main term in this running time is (√3)ⁿ, which is bounded by 1.74n.

(a) For a truth assignment Φ for the variables x₁, x₂,..., x_n, we use Φ(x_i) to denote the value assigned by Φ to x_i. (This can be either 0 or 1.) If Φ and Φ' are each truth assignments, we define the distance between Φ and Φ' to be the number of variables x_i for which they assign different values, and we denote this distance by d(Φ, Φ').In other words, d(Φ, Φ') =|{i : Φ(x_i) ≠ Φ'(x_i)}|.

A basic building block for our algorithm will be the ability to answer the following kind of question: Given a truth assignment Φ and a distance d, we'd like to know whether there exists a satisfying assignment Φ' such that the distance from Φ to Φ' is at most d. Consider the following algorithm, Explore(Φ, d), that attempts to answer this question.

Prove that Explore(Φ, d) returns "yes" if and only if there exists a satisfying assignment Φ' such that the distance from Φ to Φ' is at most d. Also, give an analysis of the running time of Explore (Φ, d) as a function of n and d.

(b) Clearly any two assignments Φ and Φ' have distance at most n from each other, so one way to solve the given instance of 3-SAT would be to pick an arbitrary starting assignment Φ and then run Explore(Φ, n). However, this will not give us the running time we want.

Instead, we will need to make several calls to Explore, from different starting points Φ, and search each time out to more limited distances. Describe how to do this in such a way that you can solve the instance of 3-SAT in a running time of only O(p(n) · (√3)ⁿ).

Q3. Suppose we are given a directed graph G = (V, E), with V = {v₁, v₂,..., v_n}, and we want to decide whether G has a Hamiltonian path from v₁ to v_n. (That is, is there a path in G that goes from v₁ to v_n, passing through every other vertex exactly once?)

Since the Hamiltonian Path Problem is NP-complete, we do not expect that there is a polynomial-time solution for this problem. However, this does not mean that all non polynomial-time algorithms are equally "bad." For example, here's the simplest brute-force approach: For each permutation of the vertices, see if it forms a Hamiltonian path from v₁ to v_n. This takes time roughly proportional to n!, which is about 3× 10¹⁷ when n = 20.

Show that the Hamiltonian Path Problem can in fact be solved in time O(2ⁿ · p(n)), where p(n) is a polynomial function of n. This is a much better algorithm for moderate values of n; for example, 2ⁿ is only about a million when n = 20.

Q4. We say that a graph G = (V, E) is a triangulated cycle graph if it consists of the vertices and edges of a triangulated convex n-gon in the plane-in other words, if it can be drawn in the plane as follows.

The vertices are all placed on the boundary of a convex set in the plane (we may assume on the boundary of a circle), with each pair of consecutive vertices on the circle joined by an edge. The remaining edges are then drawn as straight line segments through the interior of the circle, with no pair of edges crossing in the interior. We require the drawing to have the following property. If we let S denote the set of all points in the plane that lie on vertices or edges of the drawing, then each bounded component of the plane after deleting S is bordered by exactly three edges. (This is the sense in which the graph is a "triangulation.")

A triangulated cycle graph is pictured in Figure 10.12.

Prove that every triangulated cycle graph has a tree decomposition of width at most 2, and describe an efficient algorithm to construct such a decomposition.

Q5. The Minimum-Cost Dominating Set Problem is specified by an undirected graph G = (V, E) and costs c(v) on the nodes v ∈ V. A subset S ⊂ V is said to be a dominating set if all nodes u ∈ V-S have an edge (u, v) to a node v in S. (Note the difference between dominating sets and vertex covers: in a dominating set, it is fine to have an edge (u, v) with neither u nor v in the set S as long as both u and v have neighbors in S.)

(a) Give a polynomial-time algorithm for the Dominating Set Problem for the special case in which G is a tree.

(b) Give a polynomial-time algorithm for the Dominating Set Problem for the special case in which G has tree-width 2, and we are also given a tree decomposition of G with width 2.

Q6. The Node-Disjoint Paths Problem is given by an undirected graph G and k pairs of nodes (s_i, t_i) for i = 1,..., k. The problem is to decide whether there are node-disjoint paths P_i so that path P_i connects s_i to t_i. Give a polynomial-time algorithm for the Node-Disjoint Paths Problem for the special case in which G has tree-width 2, and we are also given a tree decomposition T of G with width 2.

Q7. The chromatic number of a graph G is the minimum k such that it has a k-coloring. As we saw in Chapter 8, it is NP-complete for k ≥ 3 to decide whether a given input graph has chromatic number ≤ k.

(a) Show that for every natural number w ≥ 1, there is a number k(w) so that the following holds. If G is a graph of tree-width at most w, then G has chromatic number at most k(w). (The point is that k(w) depends only on w, not on the number of nodes in G.)

(b) Given an undirected n-node graph G = (V, E) of tree-width at most w, show how to compute the chromatic number of G in time O(f (w) · p(n)), where p(·) is a polynomial but f (·) can be an arbitrary function.

Q8. Consider the class of 3-SAT instances in which each of the n variables occurs-counting positive and negated appearances combined-in exactly three clauses. Show that any such instance of 3-SAT is in fact satisfiable, and that a satisfying assignment can be found in polynomial time.

Q9. Give a polynomial-time algorithm for the following problem. We are given a binary tree T = (V, E) with an even number of nodes, and a nonnegative weight on each edge. We wish to find a partition of the nodes V into two sets of equal size so that the weight of the cut between the two sets is as large as possible (i.e., the total weight of edges with one end in each set is as large as possible). Note that the restriction that the graph is a tree is crucial here, but the assumption that the tree is binary is not. The problem is NP-hard in general graphs.