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]=1k-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