南京大学：《计算理论之美》课程教学资源（课件讲稿）Color Coding

Color Coding Bingkai Lin Nanjing University

Color Coding Bingkai Lin Nanjing University

k-Path Problem: Input:A graph G and positive integer k Question:Is there a simple path on k vertices in G? k=4 [1]Michael R.Garey and David S.Johnson,Computers and intractability:A Guide to the Theory of NP- Completeness

k-Path Problem： Input: A graph G and positive integer k Question: Is there a simple path on 𝑘 vertices in 𝐺? k=4 [1] Michael R. Garey and David S. Johnson, Computers and intractability: A Guide to the Theory of NP￾Completeness

k-Path Problem: For every subset XV(G)of size k, Input:A graph G and positive integer k check if X is a k-path in G. Question:Is there a simple path on k vertices in G? k=4 [1]Michael R.Garey and David S.Johnson,Computers and intractability:A Guide to the Theory of NP- Completeness

k-Path Problem： Input: A graph G and positive integer k Question: Is there a simple path on 𝑘 vertices in 𝐺? k=4 For every subset X⊆V(G) of size k, check if X is a k-path in G. [1] Michael R. Garey and David S. Johnson, Computers and intractability: A Guide to the Theory of NP￾Completeness

Efficient=Polynomial Time For every subset XEV(G)of size k, Your algorithm hasrunning time IV(G)+1 check if X is a k-path in G. Can you find an efficient algorithm? [1]Michael R.Garey and David S.Johnson,Computers and intractability:A Guide to the Theory of NP- Completeness

Your algorithm has running time 𝑉 𝐺 𝑘+1 . Can you find an efficient algorithm? For every subset X⊆V(G) of size k, check if X is a k-path in G. Efficient=Polynomial Time [1] Michael R. Garey and David S. Johnson, Computers and intractability: A Guide to the Theory of NP￾Completeness

Efficient=Polynomial Time For every subset XEV(G)of size k, Your algorithm has running time IV(G)+1 check if X is a k-path in G. Can you find an efficient algorithm? "I can't find an efficient algorithm,I guess I'm just too dumb." [1]Michael R.Garey and David S.Johnson,Computers and intractability:A Guide to the Theory of NP- Completeness

Your algorithm has running time 𝑉 𝐺 𝑘+1 . Can you find an efficient algorithm? Efficient=Polynomial Time For every subset X⊆V(G) of size k, check if X is a k-path in G. [1] Michael R. Garey and David S. Johnson, Computers and intractability: A Guide to the Theory of NP￾Completeness

Efficient=Polynomial Time When k=V(G)I,k-PATH Problem is Hamiltonian Path Problem,which is NP-hard. Your algorithm has running time IV(G)+1 Can you find an efficient algorithm? "I can't find an efficient algorithm.but neither can all these famous people." [1]Michael R.Garey and David S.Johnson,Computers and intractability:A Guide to the Theory of NP- Completeness

Your algorithm has running time 𝑉 𝐺 𝑘+1 . Can you find an efficient algorithm? When k=|V(G)|, k-PATH Problem is Hamiltonian Path Problem, which is NP-hard. Efficient=Polynomial Time [1] Michael R. Garey and David S. Johnson, Computers and intractability: A Guide to the Theory of NP￾Completeness

When k is small, 2kpoly(G)-Time is efficient Yes.Use Color-Coding! Your algorithm has running time IV(G)+1 Can you find an efficient algorithm? [1]Michael R.Garey and David S.Johnson,Computers and intractability:A Guide to the Theory of NP- Completeness

Your algorithm has running time 𝑉 𝐺 𝑘+1 . Can you find an efficient algorithm? Yes. Use Color-Coding! When k is small, 𝟐 𝒌poly(G)-Time is efficient [1] Michael R. Garey and David S. Johnson, Computers and intractability: A Guide to the Theory of NP￾Completeness

k-Path Problem Input:A graph G and positive integer k Question:Is there a simple path on k vertices in G? Idea: For every vertex vEV(G)and XV(G),let T[X,v]=1 if X is a path ending at v k=4 ·T[Xv=0 otherwise G has a k-path iff there exist vE V(G)and XsV(G)such T[{a},a]=1 that T[X,v]=1 and X]=k. T[{a,d.d]=1 T[{c,d,d]=1 Compute T[v,X灯： T[{e,d,d=0 ·T[w.=1 .T[X,v]=1 if there exists u s.t.uvE E(G)and T[X\{v).v]=1 T[{a,d,c,c]=1 Running time:IV(G)|O(k) T[a,d.c.f).f]=1

k-Path Problem Input: A graph G and positive integer k Question: Is there a simple path on 𝑘 vertices in 𝐺? Idea: For every vertex v ∈ 𝑉(𝐺) and X ⊆ 𝑉(𝐺), let • T[X,v]=1 if X is a path ending at v • T[X,v]=0 otherwise Compute T[v,X]: • T[{v},v]=1 • T[X,v]=1 if there exists u s.t. uv∈ 𝐸 𝐺 and T[X∖ {𝑣},v]=1 Running time: 𝑉 𝐺 𝑂(𝑘) G has a k-path iff there exist v ∈ 𝑉(𝐺) and X ⊆ 𝑉(𝐺) such that T[X,v]=1 and |X|=k. f a b d c e k=4 T[{a},a]=1 T[{a,d},d]=1 T[{c,d},d]=1 T[{e,d},d]=0 T[{a,d,c},c]=1 T[{a,d,c,f},f]=1

Co orful k-Path Problem Input:A graph G,a positive integer k and a coloring c:VG)→[ Question:Is there a simple path on k vertices in G with different color under c? Idea: For every vertex vEV(G)and C [k],let T[C,v]=1 if there exists a path X ending at v whose k=4 colors are C T[C,v]=0 otherwise G has a k-path iff there exist v E V(G)such that T[[k],v]=1. T[■，b]=1 T[■，■，c]=1 Compute T[C,v]: T[■，m},c]=0 If IC|=1,then T[C,v]=1 iff C={c(v)} T[■，题，■}，c]=1 ·flC>1,then T■，■，，■，f刀]=1 T[C,v]=1 if there exists u s.t.uvE E(G),T[C\{c(v)],u]=1 and c(v)EC; T[C,v]=0 otherwise Running time:2k.G]

Colorful k-Path Problem Input: A graph G, a positive integer k and a coloring c: V(G)→ [k] Question: Is there a simple path on 𝑘 vertices in 𝐺 with different color under c? Idea: For every vertex v ∈ 𝑉(𝐺) and C ⊆ [𝒌], let • T[C,v]=1 if there exists a path X ending at v whose colors are C • T[C,v]=0 otherwise Compute T[C,v]: • If |C|=1, then T[C,v]=1 iff C={c(v)} • If |C|>1, then • T[C,v]=1 if there exists u s.t. uv∈ 𝐸 𝐺 ,T[C∖ {𝑐(𝑣)},u]=1 and c(v)∈C; • T[C,v]=0 otherwise. Running time: 𝟐 𝒌 ⋅ |𝑮| G has a k-path iff there exist v ∈ 𝑉(𝐺) such that T[[k],v]=1. 𝑇[{■}, 𝑏] = 1 𝑇[{■,■}, 𝑐] = 1 𝑇[{■,■}, 𝑐] = 0 𝑇[{■,■,■}, 𝑐] = 1 𝑇[{■,■,■, ■}, 𝑓] = 1 f a b d c e k=4

Conclusion: Co orful k-Path Problem is easier than k-Path Problem Question: Can we translate any k-Path Problem to an equivalent Co orful k-Path Problem? → k=4 k=4

Conclusion: Colorful k-Path Problem is easier than k-Path Problem Question: Can we translate any k-Path Problem to an equivalent Colorful k-Path Problem? f a b d c e k=4 f a b d c e k=4