# Technical Report MSC-2014-01

 TR#: MSC-2014-01 Class: MSC Title: On r-simple k-path Authors: Hasan Abasi Supervisors: Nader Bshouty PDF MSC-2014-01.pdf Abstract: A Simple k-path in a graph is a path of length $k$ that visits each vertex at most once. Determining whether Simple k-Path exists in graphs is called the Simple k-Path problem. This problem is NP-complete. The Hamiltonian path problem is the $k$-Path problem for $k=n$. That is, the problem of determining whether there is a path that visits each vertex exactly once. In the first part of this thesis we develop a new algebraic technique that solves the following problem: Given a black box that contains an arithmetic circuit $f$ of degree $d$ over a field of characteristic $2$ . Decide whether $f$, expressed as an equivalent multivariate polynomial, contains a multilinear monomial of degree $d$. This problem was solved by Williams and Bj\"orklund et. al. for a white box (the circuit is given as an input). We give a simple black box algorithm that solves the problem with the same time complexity. We then use this to give a simple randomized algorithm for the Simple k-path problem for directed graphs of the same time complexity\footnote{$O^*(f(k))$ is $O(\poly(n)\cdot f(k))$} $O^*(2^k)$ as in Williams and with reusing the same ideas from Bj\"orklund with the above gives another algorithm for undirected graphs of the same time complexity $O^*(1.657^k)$ as in Bj\"orklund. In the second part of this thesis we study the following more general problem: We say that a path is r-Simple k-Path if it 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$. The Simple k-path problem is the r-Simple k-Path problem when $r=1$. We first show that for any $r$, this problem is NP-complete. Then we show that for any $r$, 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 specially when one's goal is to find a short path that visits many vertices in the graph and bounded number of visits for 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} problem for a directed 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$ and some fixed $r$ gives a randomized algorithm with running time $\poly(n)\cdot 2^{cn}$ for the Hamiltonian path in directed graph. An outstanding open problem. So in a sense our algorithm is optimal up to an $O(\log r)$ factor. Copyright The above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/2014/MSC/MSC-2014-01), rather than to the URL of the PDF files directly. The latter URLs may change without notice.