Revision #1 Authors: Vikraman Arvind, Venkatesh Raman

Accepted on: 20th June 2002 00:00

Downloads: 2239

Keywords:

As our main result, we give a randomized fixed parameter tractable

algorithm to approximately count the number of copies of a

$k$-vertex graph with bounded treewidth in an $n$ vertex graph. As a

consequence, we get randomized algorithms with running time

$k^{O(k)}n^{O(1)}$, approximation ratio $1/k^{O(k)}$, and error

probability $2^{-n^{O(1)}}$ for the following problems:

\begin{itemize}

\item Approximately counting the number of matchings of size $k$ in an

$n$ vertex graph.

\item Approximately counting the number of paths of length $k$ in an

$n$ vertex graph.

\end{itemize}

Our algorithm is based on the Karp-Luby approximate counting technique

applied to fixed parameter tractable problems, and the color-coding

technique (based on perfect hashing) of Alon, Yuster and Zwick.

It is interesting to note in contrast that the \emph{exact} counting

versions of the above two problems are recently shown by Flum and

Grohe to be hard for the parameterized complexity class $\W[1]$. Hence

no exact counting algorithm with running time $f(k) n^{b+O(1)}$ is

likely to exist these two problems, for any computable function $f:

{\cal N} \rightarrow {\cal N}$.

We also show some $\W$-hardness results for parameterized exact

counting problems, whose decision versions are known to be fixed

parameter tractable. These problems include counting versions of

weight $k$ satisfying assignment of a bounded DNF formula, and finding

a $k$-clique or a $k$-independent set in a graph.

TR02-031 Authors: Vikraman Arvind, Venkatesh Raman

Publication: 15th June 2002 16:05

Downloads: 2164

Keywords:

We give a randomized approximation algorithm taking

$O(k^{O(k)}n^{b+O(1)})$ time to count the number of copies of a

$k$-vertex graph with treewidth at most $b$ in an $n$ vertex graph

$G$ with approximation ratio $1/k^{O(k)}$ and error probability

inverse exponential in $n$. This algorithm is based on the

Karp-Luby approximate counting technique applied to

fixed parameter tractable problems, and the color-coding

technique (based on perfect hashing) of Alon, Yuster and Zwick. As a

consequence we get a randomized fixed parameter tractable algorithm

to approximately count the number of matchings of size $k$ or paths

of length $k$ in a given graph.

We also give some results (both $W$-hardness and fixed parameter

tractability) on the exact counting versions of some of these and

other fixed parameter tractable problems. These problems include

counting versions of $k$-vertex cover, weight $k$ satisfying

assignment of a bounded DNF formula, and finding a $k$-clique or a

$k$-independent set in a graph.