walk_length (759B)
1 # Walk length 2 3 Given [graph_directed], G, [source] s, [sink] t, length l, decide if there is a [walk] from s to t with length exactly l 4 5 - if l is constant then the problem is clearly tractable 6 - if l is given as input in unary, the problem is tractable by creating l copies of G 7 - O(l |G|) 8 - [fine_grained_complexity] bounds, cf [nfa_unary_lengths] 9 - if l is given in binary, the problem is [ptime] by [fast_exponentiation] to get the possible lengths of [walk]s in log l 10 - O(log l |G|) 11 - if the edges of G can be annotated with lengths also written in binary 12 - [np_hard] by reduction from [subset_sum] 13 - in [np] by [basagni1997difficulty] using [eulerian_path] 14 15 See also: [path_length], [nfa_unary_lengths] 16 17 Up: [computational_problem] on [graph]