代写代考 Analysis of Algorithms, I

Analysis of Algorithms, I
CSOR W4231

Computer Science Department

Columbia University
Reductions; independent set and vertex cover; decision problems

1 Reductions
A means to design efficient algorithms
Arguing about the relative hardness of problems
2 Two hard graph problems
3 Complexity classes The class P
The class NP
The class of NP-complete problems

Beyond problems that admit efficient algorithms
􏰉 Efficient algorithms: worst-case polynomial running time
􏰉 So far we solved a variety of problems efficiently
􏰉 Today we will look at problems for which we do not know of any efficient algorithms
􏰉 To argue about the relative hardness (difficulty) of such problems, we will use the notion of reductions

BPM: does a Bipartite graph have a Perfect Matching?
Input: a bipartite graph G = (X ∪ Y, E)
Output: yes, if and only if G has a matching of size |X| = |Y |
x1 y1 x1 y1
x2 y2 x2 y2
x3 y3 x3 y3
x4 y4 x4 y4
x5 y5 x5 y5 XYXY

Some terminology
􏰉 An instance of BPM is a specific input graph G.
􏰉 We may think of an input instance G as a binary string x encoding the graph G, with length |x| bits.
􏰉 we assume reasonable encodings: e.g., a binary number b requires a logarithmic number of bits to be encoded
􏰉 reasonable encodings are related polynomially
􏰉 An algorithm that solves BPM admits
􏰉 Input: a binary string x encoding a bipartite graph
􏰉 Output: yes, if and only if x has a perfect matching

We’ve already designed the algorithm that solves BPM
1. Given the bipartite graph G (input to BPM), we constructed a flow network G′ (input to max flow).
That is, we transformed the input instance x of BPM into an input instance y of .
x1 y1 x1 y1
x2 y2 x2 y2
x3 y3 s x3 y3 t
x4 y4 x4 y4
x5 y5 x5 y5 XYXY

We’ve already designed the algorithm that solves BPM
2. We proved that the original bipartite graph G has a max matching of size k if and only if the derived flow network G′ has a max flow of value k.
3. We computed max flow in G′;
we answer yes to BPM on input x
if and only if
we answer yes to Is max flow = n? on input y.

A diagram of the algorithm for BPM
Algorithm for BPM
bipartite G
input x to BPM
Transform G into a flow network
Value of = n?
input y to no MaxFlow
Let x be a binary encoding of G. Transforming G into G′ requires only polynomial time in |x|.

Let X, Y be two computational problems. Definition 1.
A reduction is a transformation that for every input x of X produces an equivalent input y = R(x) of Y .
􏰉 By equivalent we mean that the answer to y = R(x) considered as an input for Y is a correct yes/no answer to x, considered as an input for X.
􏰉 We will require that the reduction is completed in a polynomial in |x| number of computational steps.

Diagram of a reduction
X, Y are computational problems. x, y are inputs to X, Y respectively.
Algorithm for X
Reduction R
Algorithm for Y

Reductions as a means to design efficient algorithms
􏰉 Suppose we had a black box for solving Y .
􏰉 If arbitrary instances of X can be solved using
􏰉 a polynomial number of standard computational steps; plus
􏰉 a polynomial number of calls to the black box for Y ,
we say that X reduces polynomially to Y ; in symbols X ≤P Y.
Suppose X ≤P Y . If Y is solvable in polynomial time, then X is solvable in polynomial time.

Few observations about reductions
To solve BPM we made exactly one call to the black box for . This will be typical of all our reductions today.
Reductions between problems provide a powerful technique for designing efficient algorithms.

Reductions as a means to argue about hard problems
􏰉 SupposethatX≤P Y.
􏰉 Then Y is at least as hard (difficult) as X: given an
algorithm to solve Y , we can solve X. Fact 3 (the contrapositive of Fact 2 ).
Suppose X ≤P Y . If X cannot be solved in polynomial time, then Y cannot be solved in polynomial time.
􏰉 Fact 3 provides a way to conclude that a problem Y does not have an efficient algorithm.
􏰉 For the problems we will be discussing today, we have no proof that they do not have efficient algorithms.
⇒ So we will be using Fact 3 to establish relative levels of difficulty among these problems.

Independent Set
Definition 4 (Independent Set).
An independent set in G = (V,E) is a subset S ⊆ V of nodes such that there is no edge between any pair of nodes in the set. That is, for all u,v ∈ S, (u,v) ̸∈ E.

Vertex Cover
Definition 5 (Vertex Cover).
AvertexcoverinG=(V,E)isasubsetS⊆V ofnodessuch that every edge e ∈ E has at least one endpoint in S.

Vertex Cover
Definition 5 (Vertex Cover).
AvertexcoverinG=(V,E)isasubsetS⊆V ofnodessuch that every edge e ∈ E has at least one endpoint in S.
It is easy to find a large vertex cover.
What about a small one?

Optimization versions for IS and VC
Definition 6 (Maximum Independent Set problem). Given G, find an independent set of maximum size.
Definition 7 (Minimum Vertex Cover problem). Given G, find a vertex cover of minimum size.
Brute force approach requires exponential time: there are 2n candidate subsets since every vertex may or may not belong to such a subset.

Decision versions of optimization problems
An optimization problem may be transformed into a roughly equivalent problem with a yes/no answer, called the decision version of the optimization problem, by
1. supplying a target value for the quantity to be optimized; 2. asking whether this value can be attained.
We will denote the decision version of a problem X by X(D).

Examples of decision versions of optimization problems
􏰉 (D): Given a flow network G and an integer k (the target flow), does G have a flow of value at least k?
􏰉 Matching(D): Given a bipartite graph G and an integer k, does G have a matching of size at least k?
􏰉 IS(D): Given a graph G and an integer k, does G have an independent set of size at least k?
􏰉 VC(D): Given a graph G and an integer k, does G have a vertex cover of size at most k?
So in a maximization problem the target value is a lower bound, while in a minimization problem it is an upper bound.

Rough equivalence of decision & optimization problems
1. Suppose we have an algorithm that solves Maximum Independent Set. Algorithm for IS(D)?
2. Now suppose we have an algorithm that solves the decision version IS(D), that is, on input (G = (V, E), k), it answers yes if G has an independent set of size at least k, and no otherwise. Algorithm for Maximum Independent Set?

Rough equivalence of decision & optimization problems
1. Suppose we have an algorithm that solves Maximum Independent Set.
􏰉 To solve IS(D) on input (G, k), compute the size m of the max independent set; answer yes if k ≤ m, no otherwise.
2. Now suppose we have an algorithm that solves IS(D), that is, on input (G = (V,E),k), it answers yes if G has an independent set of size at least k, and no otherwise.
􏰉 To find the size m of the maximum independent set, use binary search and at most log n calls to IS(D).
􏰉 Note that this algorithm indeed runs in time polynomial in the size of the description of the input (G, k).
This rough equivalence between optimization problems and decision problems holds for all the problems we will discuss.

Reduction from Independent Set to Vertex Cover
Let G = (V,E) be a graph. Then S is an independent set of G if and only if V − S is a vertex cover of G.
IS(D) ≤P VC(D) and VC(D) ≤P IS(D).

Reduction from Independent Set to Vertex Cover
Let G = (V,E) be a graph. Then S is an independent set of G if and only if V − S is a vertex cover of G.
IS(D) ≤P VC(D) and VC(D) ≤P IS(D). Proof.
􏰉 Givenaninstancex=(G,k)ofIS(D),transformittoan instance y = (G, n − k) of VC(D). This completes the reduction.
􏰉 Equivalence of x and y follows from Fact 8: IS(D) answers yes on x if and only if VC(D) answers yes on y.
􏰉 Hence IS(D) ≤P VC(D).
The second part of the claim is entirely similar.

Proof of Fact 8
􏰉 Forward direction: we will show that V − S is a vertex cover of G.
If S is an independent set of G, then for all u,v ∈ S, (u, v) ̸∈ E. So consider any edge (u, v) ∈ E.
􏰉 Eitherbothu,v∈V −S,hence(u,v)iscoveredbyV −S. 􏰉 Or,u∈Sandv∈V−S(w.l.o.g.);soV−Scovers(u,v).
􏰉 Reverse direction: we will show that V − S is an independent set of G.
If S is a vertex cover of G, then for every edge (u,v) ∈ E, at least one of u,v is in S. So consider any two nodes
x, y ∈ V − S: no edge (x, y) can exist since S would not cover this edge. Hence V − S is an independent set.

The class P
Notation: x ∈ X(D) ⇐⇒ x is a yes instance of X(D).
Example: (triangle, 1) is a yes instance of IS(D) but (triangle, 2) is a
no instance of IS(D).
􏰉 An algorithm A solves (or decides) X(D) if, for all input
x, A(x) = yes if and only if x ∈ X(D).
􏰉 A has a polynomial running time, if there is a polynomial p(·) such that for all input strings x of length |x|, the worst-case running time of A on input x is O(p(|x|)).
Definition 9.
We define P to be the set of decision problems that can be solved by polynomial-time algorithms.

Problems like IS(D) and VC(D)
􏰉 No polynomial time algorithm has been found despite significant effort
􏰉 So we don’t believe they are in P
Is there anything positive we can say about such problems?
If we were given a solution for such a problem, we can certify if the instance is a yes instance quickly.

Problems like IS(D) and VC(D)
􏰉 No polynomial time algorithm has been found despite significant effort
􏰉 So we don’t believe they are in P
Is there anything positive we can say about such problems?
For example, given
1. an instance x = (G, k) for IS(D); and 2. a candidate solution S
we can verify quickly that IS(D) indeed answers yes on x by checking
1. |S| = k; and
2. there is no edge between any pair of nodes in S.

Problems like IS(D) and VC(D)
􏰉 No polynomial time algorithm has been found despite significant effort
􏰉 So we don’t believe they are in P
Is there anything positive we can say about such problems?
􏰉 If we were given a solution S for such a problem X(D), we could check if it is correct quickly.
⇒ Such an S is a succinct certificate that x ∈ X(D).
Note that VC(D) also possesses a similar succinct (short) certificate (why?).

The class NP
Definition 10.
An efficient certifier (or verification algorithm) B for a problem X(D) is a polynomial-time algorithm that
1. takes two input arguments, the instance x and the short certificate t (both encoded as binary strings)
2. there is a polynomial p(·) so that for every string x, we have x∈X(D) if and only if there is a string t such that |t|≤ p(|x|) and B(x, t)= yes.
Note that existence of the certifier B does not provide us with any efficient way to solve X(D)! (why?)
Definition 11.
We define NP to be the set of decision problems that have an efficient certifier.

Let X(D) be a problem in P.
􏰉 There is an efficient algorithm A(x) that solves X(D), that is,
A(x)= yes if and only if x∈X(D).
􏰉 To show that X(D)∈ NP, we need exhibit an efficient certifier B that takes two inputs x and t and answers yes if and only if x∈X(D).
􏰉 The algorithm B that on inputs x, t, simply discards t and simulates A(x) is such an efficient certifier.

􏰉 Arguably the biggest question in theoretical CS
􏰉 We do not think so: finding a solution should be harder than checking one, especially for hard problems…

Why would NP contain more problems than P?
􏰉 Intuitively, the hardest problems in N P are the least likely to belong to P.
􏰉 How do we identify the hardest problems?

Why would NP contain more problems than P?
􏰉 Intuitively, the hardest problems in N P are the least likely to belong to P.
􏰉 How do we identify the hardest problems? The notion of reduction is useful again.
Definition 13 (NP-complete problems:).
A problem X(D) is NP-complete if 1. X(D)∈NP,and
2. forallY∈NP,Y≤PX(D).

Why would NP contain more problems than P?
􏰉 Intuitively, the hardest problems in N P are the least likely to belong to P.
􏰉 How do we identify the hardest problems? The notion of reduction will be useful again.
Definition 13 (NP-complete problems).
A problem X(D) is NP-complete if 1. X(D)∈ N P and
2. forallY∈NP,Y≤PX(D).
Suppose X is NP-complete. Then X is solvable in polynomial time (i.e., X ∈P) if and only if P =NP.

Why we should care whether a problem is NP-complete
􏰉 If a problem is NP-complete it is among the least likely to be in P: it is in P if and only if P = NP.

Why we should care whether a problem is NP-complete
􏰉 If a problem is NP-complete it is among the least likely to be in P: it is in P if and only if P = NP.
􏰉 Therefore, from an algorithmic perspective, we need to stop looking for efficient algorithms for the problem.
Instead we have a number of options
1. approximation algorithms, that is, algorithms that return a solution within a provable guarantee from the optimal
2. exponential algorithms practical for small instances
3. work on interesting special cases
4. study the average performance of the algorithm
5. examine heuristics (algorithms that work well in practice, yet provide no theoretical guarantees regarding how close the solution they find is to the optimal one)

How do we show that a problem is NP-complete?
Suppose we had an NP-complete problem X.
To show that another problem Y is NP-complete, we only need
1. Y ∈ N P and 2. X ≤P Y

How do we show that a problem is NP-complete?
Suppose we had an NP-complete problem X.
To show that another problem Y is NP-complete, we only need
1. Y ∈ N P and 2. X ≤P Y
Fact 15 (Transitivity of reductions).
IfX≤P YandY≤P Z,thenX≤P Z.
Weknowthatforallπ∈NP,π≤P X.ByFact15,π≤P Y. Hence Y is NP-complete.

How do we show that a problem is NP-complete?
Suppose we had an NP-complete problem X.
To show that another problem Y is NP-complete, we only need
1. Y ∈ N P and 2. X ≤P Y
So, if we had a first NP-complete problem X, discovering a new problem Y in this class would require an easier kind of reduction: just reduce X to Y (instead of reducing every problem in NP to Y!).

How do we show that a problem is NP-complete?
Suppose we had an NP-complete problem X.
To show that another problem Y is NP-complete, we only need
1. Y ∈ N P and 2. X ≤P Y
The first NP-complete problem Theorem 15 (Cook-Levin). Circuit SAT is NP-complete.

程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts