程序代写代做代考 Microsoft PowerPoint – lecture14 [Compatibility Mode]

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 xnx2 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

4x3x

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

4x3x

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