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 NPCompleteness
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 NPCompleteness
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 NPCompleteness
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 NPCompleteness