EECS 376: Foundations of Computer Science
University of Michigan, Winter 2022 Discussion Notes 10 1 Search Problems and Search to Decision Reductions
Many of the problems we have discussed in lecture deal with “yes” or “no” answers. Such problems are known as decision problems or languages. However, sometimes we want to return an array of integers with a specific property, or a subset of some of the nodes in a graph, and so on. These types of problems are called functional or search problems. Recall the following definition:
Definition 1.1. A search problem is NP-Hard if an efficient algorithm to the problem implies P = NP.
Copyright By PowCoder代写 加微信 powcoder
From this definition, we state the following informal theorem without proof.
Proposition 1.2. (Informal) An NP-Hard search problem has an efficient algorithm if and only
if its decision version does.
The implications of these statements are that given an efficient algorithm for the decision version of any NP-Complete problem, it is possible to construct an efficient algorithm that solves the corresponding search version of the same problem, generally called a search-to-decision reduction. We now consider a few relevant definitions before looking at some examples.
Let val be a function which maps from the set of solutions to the set of real numbers. This will allow us to rank solutions.
Definition 1.3. An optimal solution to a maximization problem is y∗ such that ∀y in the solution space : val(y∗) ≥ val(y).
Definition 1.4. An optimal solution to a minimization problem is y∗ such that ∀y in the solution space : val(y∗) ≤ val(y).
We note that search problems are often (but not always, as we will see soon) in the form of a maximization or minimization problem – problems for which we want to maximize or minimize some function or quantity given certain constraints.
Example 1.5 (Minimization problem). Previously, we encountered Kruskal’s algorithm and the problem of finding a minimum spanning tree for an undirected graph. This can be interpreted as a minimization problem. The set of solutions is the set of spanning trees of the graph, and the value of the spanning tree is equal to its weight. Our goal is to minimize the weight of the spanning tree. Recall that a graph may have more than one minimum spanning tree – in general, a minimization problem need not have a unique optimal solution.
Example 1.6 (Maximization problem). We saw the 0-1 Knapsack problem in discussion notes 3. This search problem can be interpreted as a maximization problem. The set of solutions is the set of subsets of items whose total weight does not exceed the capacity of the knapsack. Our goal is the maximize the total value of the subset of items which we take, so the value of solution can be the total value of the subset of items. As before, an optimal solution to an instance of the 0-1 Knapsack problem is not necessarily unique.
EECS 376: Foundations of Computer Science
University of Michigan, Winter 2022 Discussion Notes 10 2 Examples of Search-to-Decision Reductions
2.1 Search-to-Decision Reduction for SAT
Recall the language SAT = {⟨φ⟩ | φ is a satisfiable Boolean formula}.
Claim 2.1. If SAT is decidable in polynomial time, then given a boolean formula φ, we can
efficiently find a satisfying assignment for each variable such that φ evaluates to true.
Proof. Assume that SAT ∈ P. Then there exists an algorithm D which decides SAT and runs in O(|φ|k) time on input φ. Suppose there are n variables in φ: x1,…,xn. To find a satisfying assignment for φ we must find a satisfying assignment for each xi (1 ≤ i ≤ n).
1. If D(φ) returns false, output ⊥ (the formula is unsatisfiable).
2. For each variable xi (1 ≤ i ≤ n) in φ, do the following:
(a) Set xi to false (xi = F). Let us denote the resulting formula (with xi set to false) as φxi=F . Run D(φxi=F ).
i. If D(φxi=F ) accepts, continue to the next iteration of the algorithm (for xi+1).
ii. If D(φxi=F ) rejects, set xi to true and continue to the next iteration of the algorithm
3. We are now left with a truth assignment for each variable xi in φ such that D accepts, which means that this assignment must be an assignment for φ which evaluates φ to true. Output the truth values of x1,…,xn.
We claim that the runtime of the search algorithm is polynomial in the input size. We know that the runtime of D is O(|φ|k). This algorithm iterates for at most n ≤ |φ| iterations (linear in the number of variables in φ, which may be less than the actual size of φ if some variables are duplicated). In each iteration, it takes O(|φ|) time to assign the new truth assignment to the literals in φ. Also, in each iteration, there is a single call to D which takes O(|φ|k) time. Therefore, the runtime of the algorithm is O(n · (|φ| + |φ|k)) = O(|φ|2 + |φ|k+1) = O(|φ|k+1) which is polynomial in |φ|.
2.2 Search-to-Decision Reduction for Long-Path
Consider the language:
⟨G, k⟩ : k is an integer; G is an undirected graph Long-Path = with a simple path of length ≥ k .
Recall that a simple path is a path that does not visit a vertex twice or more.
Claim 2.2. If Long-Path is decidable in polynomial time, then given an undirected graph G, we are able to find vertices and edges that make up the longest simple path in G, if one exists, in polynomial time.
Proof. Assume that Long-Path ∈ P. Then there exists an efficient algorithm A that decides Long-Path in polynomial time, where the input size n is the number of vertices in G.
To find the longest path in G:
EECS 376: Foundations of Computer Science
University of Michigan, Winter 2022 Discussion Notes 10
1. First we need to determine the number of edges that are part of the longest simple path in G. To do so, we can simply iterate through k = 0 to |V | − 1, and see if A(G, k). The greatest k for which A accepts is the size of the longest path. From here on k∗ will refer to that value.
2. Now we can test if each edge is part of the longest path or not. The key idea is that if there is some path of length k∗ that does not use some edge e, the graph G\e will still have a path of length k∗. So, for each edge e ∈ G, we remove e then remove any isolated vertices and run A(G\e,k∗). If it rejects we replace e and any vertices we removed.
3. At this point we are only left with the vertices and edges that form a simple path of length k∗.
Let O(|G|c) be the runtime complexity of A on ⟨G, k⟩. This algorithm takes O(|V | · |G|c) time to determine the length of the longest path if a linear search is used, O(|E|·|G|c) time to determine the path edges, and O(|V |) time again to return the path. The overall time complexity therefore is O(|E| · |G|c + |V | · |G|c), which is polynomial with respect to the size of G. One should check if we are actually only left with a simple path of length k∗ at the end, i.e. there is no edge that is not part of a path of length k∗ and the path of length k∗ we are left with is unique.
3 Approximation Algorithms
Based on the above discussion, the notion of NP-Hardness extends beyond just decision problems. It even applies to “search” problems – problems which we take a keen interest in. So what can we do if we cannot find an optimal solution to a “search” problem exactly? One method is to find a solution which approximates or is somehow close to the optimal solution. We will often call such a solution an approximate solution.
Let y∗ be an optimal solution to some minimization/maximization search problem, and define OPT = val(y∗). For the following definitions, let y be the solution produced by some approximation algorithm A.
Definition 3.1. For maximization problems:
An approximate solution y is said to be an α-approximation if
α·OPT≤val(y)≤OPT (forα<1). Definition 3.2. For minimization problems:
An approximate solution y is said to be an α-approximation if
OPT ≤val(y)≤α·OPT (forα>1).
Definition 3.3. The value α in the above definitions is known as the approximation ratio of y. 4 TSP Approximation Algorithm
In TSP, we are given a complete, edge-weighted, undirected graph G = (V, E). A complete graph is one such that every pair of vertices has an edge between them, i.e. a graph that is also a clique. An edge-weighted graph is one that is equipped with a function w : E → R+ that assigns a positive real number to each edge, called its weight. We think of each vertex as a city, and the weight of the edge (v1,v2) as the travel distance from v1 to v2. A subgraph of G is a graph H = (V′,E′)
EECS 376: Foundations of Computer Science
University of Michigan, Winter 2022 Discussion Notes 10
such that V ′ ⊆ V and E′ ⊆ E. If H is a subgraph of G, then the weight of H, denoted w(H), is the sum of the weights of its edges. If P is a simple path in G, we can think of P as a subgraph, and define its weight to be the sum of the weights of the edges along the path. The goal of TSP is to find a Hamiltonian cycle of minimum weight, which we call an optimal tour. We can interpret this as follows. A salesperson wants to visit each city exactly once and return to the city at which they started, while minimizing the total distance they travel. They can accomplish this task by traveling along an optimal tour.
A special case of TSP occurs when the vertices of G are points in the plane, and the weight of the edge (v1, v2) is the distance between v1 and v2: if v1 = (x1, y1) and v2 = (x2, y2), then
w((v1, v2)) := |v1 − v2| = (x1 − x2)2 + (y1 − y2)2.
This corresponds to the situation in which all the cities are assumed to lie on a plane, and the travel distance from one city to another is the straight line distance between them. It turns out that even in this restricted setting, TSP is NP-complete. In this restricted setting, the edge weights satisfy the triangle inequality: for all vertices v1, v2, v3 ∈ V :
w((v1, v2)) ≤ w((v1, v3)) + w((v3, v2)).
We will present a 2-approximation algorithm for TSP for the special case that the edge weights satisfy the triangle inequality (the case of points on the plane is just a specific example of this more general setting).
4.1 Minimum Spanning Tree
A tree is a connected, undirected graph that has no cycle. Let G = (V,E) be a connected, undirected, edge-weighted graph. A spanning tree of G is a subgraph of G that is a tree, and that contains all the vertices of G. A minimum spanning tree (MST) is a spanning tree of minimum weight.
Recall that Kruskal’s algorithm can produce a MST in polynomial time. We can use a MST of G to approximately solve TSP in polynomial time.
4.2 Using MST to approximately solve TSP with the triangle inequality
We are given a complete, edge-weighted, undirected graph G = (V, E) whose edge weights satisfy the triangle inequality. Our first step is to find an MST T of G.
Claim 4.1. Let H be an optimal tour, and let T be a MST of G. Then w(T) ≤ w(H)
Proof. For a proof by contradiction, suppose that we had w(T) > w(H). Then since H is a Hamiltonian cycle, we could remove an edge from H to get a spanning tree with weight less than T . This contradicts our assumption that T was a MST, so we are done.
Now, consider the tour that we get by performing a depth-first search on T. We would traverse each edge twice, so the total distance traveled in this tour is 2w(T). Of course, this tour is not our desired solution because we will visit some vertices more than once. However, since G is a complete graph, we can modify this tour by circumventing any repetitions: we perform the same tour, but every time we are about to revisit a vertex, we just go straight to the next unvisited vertex in the tour. In this way, we obtain a Hamiltonian cycle; let c be its weight. By the triangle inequality, the distance traveled by going straight from one vertex to another cannot be more than the distance
EECS 376: Foundations of Computer Science
University of Michigan, Winter 2022 Discussion Notes 10 traveled if we visit some other vertices in between. Therefore, c ≤ 2w(T ). If H is an optimal tour,
so this is a 2-approximation algorithm for TSP.
c ≤ 2w(T) ≤ 2w(H),
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com