Abstract
Parameterized complexity has, so far, been largely confined to consideration of computational problems as decision or search problems. However, it is becoming evident that the parameterized point of view can lead to new insight into counting problems. The goal of this article is to introduce a formal framework in which one may consider parameterized counting problems.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
A. Andrzejak: An algorithm for the Tutte Polynomials of Graphs of Bounded Treewidth. Discrete Math. 190, pp 39–54, (1998).
V. Arvind and V. Raman: Approximate Counting Small Subgraphs of Bounded Treewidth and Related Problems. manuscript.
C. Bazgan: Schémas d’approximation et complexité paramétrée. Rapport de stage de DEA d’Informatique à Orsay, (1995).
M. Cesati: Perfect Code is W[1]-complete. Information Processing Letters 81(3), pp 163–168, (2002).
M. Cesati and L. Trevisan: On the Efficiency of Polynomial Time Approximation Schemes. Information Processing Letters 64(4), pp 165–171, (1997).
J. Chen, I.A. Kanj and W. Jia: Vertex Cover: Further Observations and Further Improvements. Journal of Algorithms 41, pp 280–301, (2001).
B. Courcelle, J.A. Makowsky and U. Rotics: On the Fixed Parameter Complexity of Graph Enumeration Problems Definable in Monadic Second Order Logic. Discrete Applied mathematics, Vol. 108, No. 1-2, pp. 23–52, (2001).
R. G. Downey and M. R. Fellows: Fixed-parameter tractability and completeness. Congressus Numeratium, Vol 87, pp 161–187, (1992).
R. G. Downey and M. R. Fellows: Parameterized Complexity. Springer-Verlag (1999).
Markus Frick Easy Instances for Model-Checking. Ph.D. Thesis, Laboratory for Foundations of Computer Science, The University of Edinburgh, (2001).
Markus Frick and Martin Grohe: Deciding First-Order Properties of Locally Tree-Decomposable Graphs. Proceedings of the 26th International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science 1644, pp 331–340, Springer-Verlag, (1999).
M. Grohe: personal communication.
D. Kozen: The Design and Analysis of Algorithms. Springer-Verlag (1991).
J.A. Makowsky: Colored Tutte Polynomials and Kauffman Brackets for Graphs of Bounded Tree Width. Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms, Washington DC, pp. 487–495, (2001).
S.D. Noble: Evaluating the Tutte Polynomial for graphs of bounded tree-width. Combin. Probab. Comput. 7, pp 307–321, (1998).
C. H. Papdimitriou: Computational Complexity. Addison Wesley (1994).
A. Razborov and M. Alekhnovich: Resolution is Not Automatizable Unless W[P] is Tractable. Proc. of the 42nd IEEE FOCS, pp 210–219, (2001).
L. Valiant: The complexity of computing the permanent. Theoret. Comput. Sci., Vol 8, pp 189–201, (1979).
D. Welsh and A. Gale: The Complexity of Counting Problems. Aspects of Complexity, editors R. Downey and D. Hirschfeldt, de Gruyter Series in Logic and Its Applications, pp 115–154, (2001).
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
McCartin, C. (2002). Parameterized Counting Problems. In: Diks, K., Rytter, W. (eds) Mathematical Foundations of Computer Science 2002. MFCS 2002. Lecture Notes in Computer Science, vol 2420. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45687-2_46
Download citation
DOI: https://doi.org/10.1007/3-540-45687-2_46
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-44040-6
Online ISBN: 978-3-540-45687-2
eBook Packages: Springer Book Archive