2013/12/17 by Hasan Abasi, Nader H. Bshouty, Abasi, Hasan +5
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Advanced Graph Theory Research #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1312.4863
An r-simple k-path is a path in the graph of length k that passes through each vertex at most r times. The r-SIMPLE k-PATH 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 4log 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 poly(n)⋅ 2O( k⋅ log r/r) that solves the r-SIMPLE k-PATH on a graph with n vertices with one-sided error. We also show that a randomized algorithm with running time poly(n)⋅ 2(c/2)k/ r with c<1 gives a randomized algorithm with running time \poly(n)⋅ 2cn for the Hamiltonian path problem in a directed graph - an outstanding open problem. So in a sense our algorithm is optimal up to an O(log r) factor.