An r -simple k -path is a {path} in the graph of length k thatpasses through each vertex at most r times. The \simpath{r}{k}problem, given a graph G as input, asks whether there exists anr -simple k -path in G. We first show that this problem isNP-Complete. We then show that there is a graph G that containsan r -simple k -path and no simple path of length greater than4logklogr . So this, in a sense, motivates this problemespecially when one's goal is to find a short path that visits manyvertices in the graph while bounding the number of visits at eachvertex.

We then give a randomized algorithm that runs intime\poly(n)2O(klogrr) that solves the \simpath{r}{k}on a graph with n vertices with one-sided error. We also showthat a randomized algorithm with running time \poly(n)2(c2)kr with c1 gives a randomizedalgorithm with running time \poly(n)2cn for theHamiltonian path problem in a directed graph - an outstanding open problem.So in a sense our algorithm is optimal up to an O(logr) factor