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