Microsoft PowerPoint – lecture14 [Compatibility Mode]
COMS4236: Introduction to
Computational Complexity
Spring 2018
Mihalis Yannakakis
Lecture 14, 3/1/18
Outline
• Examples of NP-complete problems and reductions
• Optimization problems vs. decision problems
• Graph Coloring and 3-Colorability problem
• Maximum Independent Set
• Maximum Clique
• Minimum Node Cover
Graph 3-Colorability is NP-complete
• Input: Undirected graph G
• Question: 3-coloring of the nodes?, i.e. assignment of
one of 3 colors to each node so that adjacent nodes
have different colors?
• In NP: Guess the 3-coloring of the nodes and check all
the edges
• NP-hard: Reduction from NAE3SAT
NAE3SAT ≤log 3-COLORABILITY
• Given instance of NAE3SAT
• Construct graph G: One node u, a node for each
variable and its negation, a gadget (a triangle) for each
clause
u
x1 x1 x2 x3 xnx2 x3
xn
Literals
Clauses
(x1,x2,x3)
NAE3SAT ≤log 3-COLORABILITY
• Three Colors: 0,1,2
• Wlog 2 is the color of u
• Then all literals get color 0 or 1 truth assignment
• If all literals of a clause have same value, then the 3 nodes
of the clause triangle have to be colored with the 2 other
colors, which is impossible
• If the literals of a clause not all equal, then we can 3-color
the clause triangle
• NAE3SAT instance is satisfiable iff graph is 3-colorable
Optimization Decision Problem
• NP (and other classes) defined as a class of languages or
decision problems – problems with Yes/No (0/1) answer.
Function and optimization problems studied in terms of a
decision problem version.
• Optimization problem : Every instance I has a set of
solutions, every solution has a value (profit or cost). The
problem is to compute the maximum or minimum possible
value and a solution that achieves it.
• Corresponding Decision problem for :
Input: instance I of , bound b on value
Question: Is the optimum value ≥b for maximization
problem (resp. optimum value ≤b for minimization problem)
Example: (Minimum) Graph Coloring
• Input: Undirected graph G=(N,E)
• Problem: Color the nodes with the minimum number of
colors so that any two adjacent nodes get different colors.
• Decision version of Graph Coloring:
• Input: Graph G, integer b
• Question: Does G have a legal coloring with at most b
colors?
• 3-Colorability is NP-complete Decision version of
Graph Coloring is also NP-complete
Maximum 3-Satisfiability (MAX 3SAT)
• Input: A set of clauses, where each clause is the
disjunction of 3 literals
• Problem: Find an assignment that satisfies the maximum
number of clauses
• Decision version of MAX 3SAT:
• Input: A set of 3-clauses, integer b
• Question: Does G have an assignment that satisfies at
least b clauses?
• 3SAT is NP-complete Decision version of MAX 3SAT
is also NP-complete
Example: Maximum Independent Set
• Input: Undirected graph G=(N,E)
• Problem: Find a maximum set of nodes that are pairwise
nonadjacent (“independent set of nodes”)
• Decision version of MIS:
• Input: Graph G, integer b
• Question: Does G have an independent set of size b ?
• Note: Important that b is part of the input. For fixed b, for
example b=10, independent set is polynomial: we can try
all (less than ) subsets of 10 nodes.
Same for MAX 3SAT: for fixed b it is P.
10n
Optimization vs. Decision Problem
• Optimization problem is at least as hard as the
corresponding Decision problem: solving opt. gives
immediately answer for decision
• In most cases, it is possible (but harder) to go also the
other way using a routine for the Decision problem
repeatedly (but only a polynomial number of times).
• Step 1. Find the optimal value
• Step 2. Find an optimal solution, one piece at a time
MIS: Optimization from Decision Problem
• Suppose we have a polynomial time routine DecMIS for
the decision problem. Then we can solve the optimization
problem in polynomial time.
1. Find the size c* of the maximum independent set: Call
DecMIS for inputs (G,b), b=1,…,n (or do binary search on
b) to find the maximum b for which DecMIS returns Yes.
2. Find a maximum independent set, one node at a time:
I*=; d=c* [ d =size of MIS in the remaining graph ]
for i = 1 to n do
{ if DecMIS(G-i, d) = Yes then G := G-i [don’t need i]
else { I*:= I* {i} ; d=d-1; G := G –i –Adj(i) }
}
return I*
Functional problems → Decision problems
• General problems with output:
• To show that a problem is computationally hard,
transform to a decision problem and show that the
decision problem is NP-hard.
• The decision problem should not be harder than the
original problem: for any input, the output should
determine easily the Yes/No decision
• Any “functional” problem (only one correct output)
can be reduced to a series of calls to a decision
problem:
Input: Instance x of , index i, letter a
Question: Is the i-th letter of the output of on input x
equal to a?
NP-completeness techniques: A ≤p B
• Restriction: A restriction (special case) of the problem B
is a known NP-complete problem A
– Example: CNF Satisfiability, MAX 3SAT: 3SAT is a special case
– Chromatic number: Graph 3-Colorability is a special case
• Local replacements and Gadgets:
Reflect the structure of the instance of problem A and its
constraints in problem B by designing suitable gadgets
and connecting them in appropriate way
– Example: Circuit SAT to 3SAT
– 3SAT to NAESAT
– 3SAT to INDEPENDENT SET
…….
(Maximum) Independent Set Problem
• Independent set in a (undirected) graph G: subset I of
nodes that are pairwise nonadjacent.
Example: edges = conflicts; Independent set = conflict-free
• (Maximum) Independent Set Problem
Input: Graph G
Output: An independent set of maximum cardinality
• Decision version: Input: graph G, number k
• Question: independent set of size ≥k? (equivalently, =k?)
• In NP: certificate= independent set I of size ≥k
• NP-hard: Reduction from 3SAT
3SAT ≤log Independent Set
• 3SAT formula with clauses C1,…,Cm, variable x1,…,xn
• Graph G, number k=m
Nodes: One node for each literal occurrence in each
clause
Edges: Connect literals in same clause and
complementary literals
• is satisfiable iff G has independent set with m nodes
1 2 3 1 2 4 2 3 4(x x x ) ( x x x ) (x x x )
1x
2x 3x
1x
2x
4x3x
2x
4x
3SAT ≤log Independent Set Proof ctd.
1. If is satisfiable then independent set with m nodes
Take a satisfying truth assignment, and let I include one
true literal node from each clause
2. If independent set I with m nodes then is satisfiable
Set a variable xi true (1) if a node for literal xi is in I, false (0)
if a node for literal xi is in I, and arbitrarily otherwise
1 2 3 1 2 4 2 3 4(x x x ) ( x x x ) (x x x )
1x
2x 3x
1x
2x
4x3x
2x
4x
Assignment: x1 = 0/1, x2 =1, x3 = 0/1, x4 = 0
(Maximum) Clique Problem
• Clique in a (undirected) graph G: subset C of nodes that
are pairwise adjacent.
• (Maximum) Clique Problem
Input: Graph G
Output: A clique of maximum cardinality
• Decision version: Input: graph G, number k
• Question: clique of size ≥k?
• In NP: certificate= clique of size ≥k
• NP-hard: Reduction from Max Independent Set
Independent Set ≤log Clique
• Graph G, number k for Independent Set problem
Graph G’ = complement of G, same number k for Clique
G’ has same nodes as G, an edge is in G’ iff it is not in G
• A set I of nodes is independent in G iff I is a clique in G’
• G has independent set of size k iff G’ has clique of size k
Node (Vertex) Cover Problem
• Node Cover in a undirected graph G: subset C of nodes
such that every edge has a node in C
• (Minimum) Node Cover Problem
Input: Graph G
Output: A node cover of minimum cardinality
• Decision version: Input: graph G, number k
• Question: node cover of size ≤k?
• In NP: certificate= node cover of size ≤ k
• NP-hard: Reduction from Max Independent Set
Independent Set ≤log Node Cover
• Graph G=(N,E), number k for Independent Set problem
Graph G’ = same graph G, k’ =n-k , where n =#nodes
• A set I of nodes is independent iff N-I is a node cover
•G has independent set of size ≥k iff G has node cover of
size ≤n-k
I no
edgesindependent
N-I
node cover