Paper Info
Title
Kernelizations for parameterized counting problems
Abstract
Kernelizations are an important tool in designing fixed parameter algorithms for parameterized decision problems. We introduce an analogous notion for counting problems, to wit, counting kernelizations which turn out to be equivalent to the fixed parameter tractability of counting problems. Furthermore, we study the application of well-known kernelization techniques to counting problems. Among these are the Buss Kernelization and the Crown Rule Reduction for the vertex cover problem. Furthermore, we show how to adapt kernelizations for the hitting set problem on hypergraphs with hyperedges of bounded cardinality and the unique hitting set problem to their counting analogs.
Year
DOI
Venue
2007
10.1007/978-3-540-72504-6_64
TAMC
Keywords
Field
DocType
vertex cover,decision problem
Kernelization,Discrete mathematics,Combinatorics,Decision problem,Parameterized complexity,Computer science,Constraint graph,Cardinality,Counting problem,Vertex cover,Bounded function
Conference
Volume
ISSN
Citations 
4484
0302-9743
2
PageRank 
References 
Authors
0.38
15
1
Name
Order
Citations
PageRank
Marc Thurley1996.02