A Simple Algorithm for Hamiltonicity

MaRDI QIDQ6250639zbMATH OpenFDO

Authors Hasan Abasi, Nader H. Bshouty

Publication date 10 April 2014

Abstract: We develop a new algebraic technique that solves the following problem: Given a black box that contains an arithmetic circuit $f$ over a field of characteristic $2$ of degree~$d$. Decide whether $f$, expressed as an equivalent multivariate polynomial, contains a multilinear monomial of degree $d$. This problem was solved by Williams cite{W} and Bj"orklund et. al. cite{BHKK} for a white box (the circuit is given as an input) that contains arithmetic circuit. We show a simple black box algorithm that solves the problem with the same time complexity. This gives a simple randomized algorithm for the simple $k$-path problem for directed graphs of the same time complexityfootnote{$O^{\ast }(f(k))$ is $O(poly(n)cdotf(k))$} $O^{\ast }(2^k)$ as in cite{W} and with reusing the same ideas from cite{BHKK} with the above gives another algorithm (probably not simpler) for undirected graphs of the same time complexity $O^{\ast }(1.657^k)$ as in cite{B10,BHKK}.

This page was built for publication: A Simple Algorithm for Hamiltonicity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6250639)