dag_path_length (557B)
1 # Dag path length 2 3 Given a [DAG] G, a source s and sink t, and a length l, decide whether there is an st-path of length l in G 4 5 Generalization of [unary_subset_sum] (corresponds to a specific shape of [DAGs] with a sequence of [bottlenecks] and two parallel paths from one bottleneck to the next 6 7 [Conditional_hardness] in [potechin2020lengths] for [NFA_unary_lengths] 8 - reduction from [triangle_detection] 9 10 Can be solved via [Boolean_matrix_multiplication] 11 12 [dag_path_length_mine] 13 14 Up: [path_length], [directed_acyclic_graph] 15 16 See also: [bringmann2024nfa]