An r-simple k-path is a {path} in the graph of length k that
passes through each vertex at most r times. The \simpath{r}{k}
problem, given a graph G as input, asks whether there exists an
r-simple k-path in G. We first show that this problem is
NP-Complete. We then show that there is a graph G that contains
an r-simple k-path and no simple path of length greater than
4\log k/\log r. So this, in a sense, motivates this problem
especially when one's goal is to find a short path that visits many
vertices in the graph while bounding the number of visits at each
vertex.
We then give a randomized algorithm that runs in
time