M.Sc Thesis
M.Sc Student Abasi Hassan On r-Simple k-Path Department of Computer Science Professor Nader Bshouty

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

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.