The Parameterized Complexity of Counting Problems

We develop a parameterized complexity theory for counting problems. As the basis of this theory, we introduce a hierarchy of parameterized counting complexity classes #W[t], for t/spl ges/1, that corresponds to Downey and Fellows' (1999) W-hierarchy and show that a few central W-completeness results for decision problems translate to #W-completeness results for the corresponding counting problems. Counting complexity gets interesting with problems whose decision version is tractable, but whose counting version is hard. Our main result states that counting cycles and paths of length k in both directed and undirected graphs, parameterized by k, are #W[1]-complete. This makes it highly unlikely that any of these problems is fixed-parameter tractable, even though their decision versions are. More explicitly, our result shows that most likely there is no f(k)/spl middot/n/sup c/-algorithm for counting cycles or paths of length k in a graph of size n for any computable function f: /spl Nopf//spl rarr//spl Nopf/ and constant c, even though there is a 2/sup O(k)//spl middot/n/sup 2. 376/ algorithm for finding a cycle or path of length k (2).

Authors

• Jörg Flum
• Martin Grohe

Keywords

• Complexity theory
• Bipartite graph
• Computer science
• Databases
• Approximation algorithms
• Computational complexity
• Polynomials
• Algorithm design and analysis
• Artificial intelligence
• Computational biology
• Complex Parameters
• Counting Problem
• Path Length
• Undirected
• Cycle Length
• Decision Problem
• Graph Size
• Vocabulary
• Class Of Problems
• Minimum Coverage
• Immediate Consequence
• Algorithm For Problem
• Proof Of Result
• Problem Parameters
• Example Of Problem
• Version Of Problem
• Inclusion Exclusion
• Free Variables
• First-order Logic
• Vertex Cover
• Dominating Set
• Form Of Formula
• Time Graph
• Propositional Logic
• Universal Quantifier
• Planar Graphs
• Clique Of Size
• Tree Search
• Isomorphism