Analysis of Algorithms
V. Adamchik CSCI 570 Spring 2020 Lecture 13 University of Southern California
NP-Completeness
Reading: chapter 9
P and NP complexity classes
P = set of problems that can be solved in polynomial
time by a deterministic TM.
NP = set of problems that can be solved in polynomial time by a nondeterministic TM.
NP = set of problems for which solution can be verified in polynomial time by a deterministic TM.
Polynomial Reduction: Y ≤p X
To reduce a decision problem Y to a decision problem X (we
write Y ≤p X) we want a function f that maps Y to X such that:
1) f is a polynomial time computable
2) ∀y ∈ Y (y is instance of Y) is YES if and only if f(y) ∈ X is YES.
If we cannot solve Y, we cannot solve X.
We use this to prove NP completeness: knowing that Y is hard, we prove that X is at least as hard as Y.
Polynomial Reduction: Y ≤p X
NP-Hard and NP-Complete
X is NP-Hard, if ∀Y NP and Y ≤p X.
X is NP-Complete, if X is NP-Hard and X NP.
NP-hard
NP-complete
NP
P
Assuming P ≠ NP.
NP-Completeness Proof Method
To show that X is NP-Complete:
1) Show that X is in NP
2) Pick a problem Y, known to be an NP-Complete 3) Prove Y ≤p X (reduce Y to X)
Transf.
Algorithm for X
Algorithm for Y YX
yes no
Boolean Satisfiability Problem (SAT)
A propositional logic formula is built from variables, operators AND (conjunction, ∧), OR (disjunction, ∨), NOT (negation, ¬), and parentheses:
(X1∨¬X3)∧(X1 ∨¬X2∨X4∨X5)∧…
A formula is said to be satisfiable if it can be made TRUE by assigning appropriate logical values (TRUE, FALSE) to its variables.
Theorem. SAT is NP-complete.
Hamiltonian Cycle Problem
A Hamiltonian cycle (HC) in a graph is a cycle that visits each vertex exactly once.
Problem Statement:
Given a directed or undirected graph G = (V,E). Find if the graph contains a Hamiltonian cycle.
We can prove it that HC problem is NP-complete by reduction from SAT, but we won’t.
Traveling Salesman Problem
Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city and returns to the origin city?
Problem Statement:
Given a weighted graph G=(V,E) with positive edge costs, is there a Hamiltonian cycle that has total cost k?
We can prove that it is a NP-compete problem.
Karp introduced the now standard methodology for proving problems to be NP-Complete.
He received a Turing Award for his work (1985).
Discussion Problem 1
Given SAT in Conjunctive Normal Form (CNF) (X1∨¬X3)∧(X1 ∨¬X2∨X4∨X5)∧…
with any number of clauses and any number of literals in each clause. Prove that SAT is polynomial time reducible to 3SAT.
Discussion Problem 2
Assuming that finding a Hamiltonian Cycle (HC) in a graph is NP-complete, prove that finding a Hamiltonian Path is also NP-complete. HP is a path that visits each vertex exactly once and isn’t required to return to its starting point.
Graph Coloring
Given a graph, can you color the nodes with ≤ k colors such that the endpoints of every edge are colored differently?
Theorem. (k>2)
k-Coloring is NP-complete.
Graph Coloring: k = 2
How can we test if a graph has a 2-coloring?
3-SAT ≤p 3-colorable
We construct a graph G that will be 3-colorable iff the 3- SAT instance is satisfiable.
Graph G consists of the following gadgets.
A truth gadget:
TF
A gadget for each variable:
a ¬a
3-SAT ≤p 3-colorable
Combining those gadgets together (for three literals)
3-SAT ≤p 3-colorable
A special gadget for each clause
This gadget connects a truth gadget with variable gadgets.
a
b
c
T
3-SAT ≤p 3-colorable
Suppose all a, b and c are all False (red).
T
3-SAT ≤p 3-colorable
We have showed that if all the variables in a clause are false, the gadget cannot be 3-colored.
Example: a ∨ ¬b ∨ c
Example with four clauses
a=c=T b=d=F
3-SAT ≤p 3-colorable Claim: 3-SAT instance is satisfiable if and only if
G is 3-colorable.
Proof: ⇒)
3-SAT ≤p 3-colorable Claim: 3-SAT instance is satisfiable if and only if
G is 3-colorable.
Proof: ⇐)
Sudoku: n2×n2
NP-? NP-hard?
Sudoku Graph
Sudoku
Constructing a Sudoku graph we have proved:
Don’t be afraid of NP-hard problems.
Many reasonable instances (of practical interest) of problems in class NP can be solved!
The largest solved TSP an 85,900-vertex route calculated in 2006. The graph corresponds to the design of a customized computer chip created at Bell Laboratories, and the solution exhibits the shortest path for a laser to follow as it sculpts the chip.
Discussion Problem 3
The Steiner Tree problem is as follows. Given an undirected weighted graph G=(V,E) with positive edge costs, a subset of vertices R ⊆ V, and a number C. Is there a tree in G that spans all vertices in R (and possibly some other in V) with a total edge cost of at most C? Prove that this problem is NP-complete by reduction from Vertex Cover.
Example. B 12 C R = {A,F,D} and C = 34. 16
20 A497D
13
F
18
4
E
G
B A
F
C
D
E
BC
D
A
F
E
BC
D
A
F
E
Approximation Algorithms
Suppose we are given an NP-hard problem to solve.
Can we develop a polynomial-time algorithm that produces a “good enough” solution?
An algorithm that returns near-optimal solutions is called an approximation algorithm.
Graph Coloring
Given a graph G=(V,E), find the minimum number of colors required to color vertices, so no two adjacent vertices have the same color.
This is NP-hard problem.
Let us develop a solution that is close enough to the optimal solution.
Greedy Approximation
Given G=(V,E) with n vertices.
Use the integers {1,2,3, …, n} to represent colors.
Order vertices by degree in descending order.
Color the first vertex (highest degree) with color 1.
Go down the vertex list and color every vertex not adjacent to it with color 1.
Remove all colored vertices from the list. Repeat for uncolored vertices with color 2.
Example
F JK
D
BC Order: H, K, D, G, I, J, A, B, E, F, C
G H
A
I
E
Formal Definition
Let P be a minimization problem, and I be an instance of P. Let ALG(I) be a solution returned by an algorithm, and let OPT(I) be the optimal solution.
Then ALG(I) is said to be a 𝛼-approximation algorithm for some 𝛼 > 1, if for ALG(I) ≤ 𝛼 ∙ OPT(I).
Maximization Problem
Let P be a maximization problem, and I be an instance of P. Let ALG(I) be a solution returned by an algorithm, and let OPT(I) be the optimal solution.
Then ALG(I) is said to be a 𝛼 -approximation
algorithm for some 0 < 𝛼 < 1, if for ALG(I) ≥ 𝛼 ∙ OPT(I).
Vertex cover
Given G=(V,E), find the smallest S⊂V s.t. every edge is incident on a vertex in S.
Let us design a greedy algorithm for vertex cover.
Example
Vertex cover
Lemma. Let M be a matching in G, and S be a vertex cover, then
|S| ≥ |M|
2-Approximation Vertex Cover
Approx-VC(G):
M - maximal matching on G
S - take both endpoints of edges in M Return S
Theorem. Let OPT(G) be the size of the optimal vertex cover and S = ApproxVC(G). Then |S| ≤ 2∙ OPT(G).
Proof.
Can we do better than 2-Approximation?