TR14-004 Authors: Hasan Abasi, Nader Bshouty, Ariel Gabizon, Elad Haramaty

Publication: 11th January 2014 22:04

Downloads: 1714

Keywords:

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

$$\poly(n)\cdot 2^{O( k\cdot \log r/r)}$$ that solves the \simpath{r}{k}

on a graph with $n$ vertices with one-sided error. We also show

that a randomized algorithm with running time $\poly(n)\cdot

2^{(c/2)k/ r}$ with $c<1$ gives a randomized

algorithm with running time $\poly(n)\cdot 2^{cn}$ 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.