Relations between automata and the simple k-path problem

Ran Ben-Basat, Ariel Gabizon

Let $G$ be a directed graph on $n$ vertices. Given an integer $k<=n$, the SIMPLE $k$-PATH problem asks whether there exists a simple $k$-path in $G$. In case $G$ is weighted, the M…