Technical Report MSC-2014-01

TR#:MSC-2014-01
Class:MSC
Title: On r-simple k-path
Authors: Hasan Abasi
Supervisors: Nader Bshouty
PDFMSC-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.

CopyrightThe 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.

To the list of the MSC technical reports of 2014
To the main CS technical reports page

Computer science department, Technion
admin