Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR02-031 | 20th June 2002 00:00

Approximation Algorithms for some Parameterized Counting Problems. Revision of: TR02-031

RSS-Feed




Revision #1
Authors: Vikraman Arvind, Venkatesh Raman
Accepted on: 20th June 2002 00:00
Downloads: 1672
Keywords: 


Abstract:

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.


Paper:

TR02-031 | 30th April 2002 00:00

Approximate Counting small subgraphs of bounded treewidth and related problems





TR02-031
Authors: Vikraman Arvind, Venkatesh Raman
Publication: 15th June 2002 16:05
Downloads: 1514
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint