AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
Powered by AMiner. Clicking this button will take you away from SciOpen.
Home Tsinghua Science and Technology Article
PDF (259.8 KB)
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript AI Chat Paper
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Open Access

Counting Problems in Parameterized Complexity

Department of Computer Science and Engineering, Shanghai Jiao Tong University, No. 800 Dongchuan Road, Shanghai 200240, China.
Show Author Information

Abstract

Parameterized complexity is a multivariate theory for the analysis of computational problems. It leads to practically efficient algorithms for many 𝐍𝐏-hard problems and also provides a much finer complexity classification for other intractable problems. Although the theory is mostly on decision problems, parameterized complexity naturally extends to counting problems as well. The purpose of this article is to survey a few aspects of parameterized counting complexity, with a particular emphasis on some general frameworks in which parameterized complexity proves to be indispensable.

Keywords

parameterized complexitycounting problemsdichotomy theorems

References

[1]
L. G. Valiant, The complexity of enumeration and reliability problems, SIAM Journal on Computing, vol. 8, no. 3, pp. 410-421, 1979.
Crossref Google Scholar
[2]
X. Chen, Guest column: Complexity dichotomies of counting problems, ACM SIGACT News, vol. 42, no. 4, pp. 54-76, 2011.
Crossref Google Scholar
[3]
M. Dyer and C. Greenhill, The complexity of counting graph homomorphisms, in Random Structures & Algorithms, vol. 17. John Wiley & Sons, Inc., 2000, pp. 260-289.
Crossref
[4]
R. E. Ladner, On the structure of polynomial time reducibility, Journal of the ACM, vol. 22, no. 1, pp. 155-171, 1975.
Crossref Google Scholar
[5]
L. G. Valiant, The complexity of computing the permanent, Theoretical Computer Science, vol. 8, pp. 189-201, 1979.
Crossref Google Scholar
[6]
S. Toda, PP is as hard as the polynomial-time hierarchy, SIAM Journal on Computing, vol. 20, no. 5, pp. 865-877, 1991.
Crossref Google Scholar
[7]
R. G. Downey and M. R. Fellows, Parameterized Complexity, vol. 3. Springer Heidelberg, 1999.
Crossref
[8]
R. Niedermeier, Invitation to Fixed-Parameter Algorithms. Oxford University Press, 2002.
[9]
J. Flum and M. Grohe, Parameterized Complexity Theory, vol. 3. Springer, 2006.
[10]
R. G. Downey and M. R. Fellows, Fundamentals of Parameterized Complexity. Springer, 2013.
Crossref
[11]
R. Downey, The birth and early years of parameterized complexity, in The Multivariate Algorithmic Revolution and Beyond. Springer, 2012, pp. 17-38.
Crossref
[12]
J. Flum and M. Grohe, The parameterized complexity of counting problems, SIAM Journal on Computing, vol. 33, no. 4, pp. 892-922, 2004.
Crossref Google Scholar
[13]
C. McCartin, Parameterized counting problems, Annals of Pure and Applied Logic, vol. 138, nos. 1-3, pp. 147-182, 2006.
Crossref Google Scholar
[14]
J. Edmonds, Paths, trees, and flowers, The Canadian Journal of Mathematics, vol. 17, pp. 449-467, 1965.
Crossref Google Scholar
[15]
R. Curticapean, Counting matchings of size k is #W[1]-hard, in Proceedings of the 40th International Colloquium on Automata, Languages and Programming (ICALP’13, Track A), 2013, pp. 352-363.
Crossref
[16]
A. A. Bulatov, The complexity of the counting constraint satisfaction problem, Journal of the ACM, vol. 60, no. 5, p. 34, 2013.
Crossref Google Scholar
[17]
M. E. Dyer and D. M. Richerby, On the complexity of #CSP, in Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC’10), ACM, 2010, pp. 725-734.
Crossref
[18]
M. Dyer and D. Richerby, The #CSP dichotomy is decidable, in Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science (STACS’11), vol. 9, pp. 261-272, 2011.
[19]
Y. Chen, M. Thurley, and M. Weyer, Understanding the complexity of induced subgraph isomorphisms, in Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP’08, Track A), 2008, pp. 587-596.
Crossref
[20]
H. L. Bodlaender, Fixed-parameter tractability of treewidth and pathwidth, in The Multivariate Algorithmic Revolution and Beyond. Springer, 2012, pp. 196-227.
Crossref
[21]
B. Courcelle, Graph rewriting: An algebraic and logic approach, in Handbook of Theoretical Computer Science. 1990, pp. 194-242.
Crossref
[22]
S. Arnborg, J. Lagergren, and D. Seese, Easy problems for tree-decomposable graphs, Journal of Algorithms, vol. 12, no. 2, pp. 308-340, 1991.
Crossref Google Scholar
[23]
S. Kreutzer and S. Tazari, Lower bounds for the complexity of monadic second-order logic, in Proceedings of the 25th Annual IEEE Symposium on Logic in Computer Science (LICS’10), 2010, pp. 189-198.
Crossref
[24]
J.-Y. Cai, P. Lu, and M. Xia, Computational complexity of holant problems, SIAM Journal on Computing, vol. 40, no. 4, pp. 1101-1132, 2011.
Crossref Google Scholar
[25]
J.-Y. Cai, P. Lu, and M. Xia, Holant problems and counting CSP, in Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC’09), 2009, pp. 715-724.
Crossref
[26]
L. G. Valiant, Holographic algorithms, SIAM Journal on Computing, vol. 37, no. 5, pp. 1565-1594, 2008.
Crossref Google Scholar
[27]
Y. Yin and C. Zhang, Approximate counting via correlation decay on planar graphs, in Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’13), SIAM, 2013, pp. 47-66.
Crossref
[28]
V. Arvind and V. Raman, Approximation algorithms for some parameterized counting problems, in Proceedings of the 13th International Symposium on Algorithms and Computation, Springer-Verlag, 2002, pp. 453-464.
Crossref
[29]
N. Alon, R. Yuster, and U. Zwick, Color-coding, Journal of the ACM, vol. 42, no. 4, pp. 844-856, 1995.
Crossref Google Scholar
[30]
J. Plehn and B. Voigt, Finding minimally weighted subgraphs, in Proceedings of the 16th International Workshop on Graph-Theoretic Concepts in Computer Science (WG’90), 1990, pp. 18-29.
Crossref
[31]
B. Lin and Y. Chen, The parameterized complexity of k-edge induced subgraphs, in Proceedings of the 39th International Colloquium on Automata, Languages and Programming (ICALP’12, Track A), 2012, pp. 641-652.
Crossref
[32]
M. Bläser and R. Curticapean, Weighted counting of k-matchings is #W[1]-hard, in Proceedings of the 7th International Symposium on Parameterized and Exact Computation (IPEC’12), 2012, pp. 171-181.
Crossref
[33]
R. Curticapean and D. Marx, Private communication, 2014.
[34]
D. Marx, Can you beat treewidth? Theory of Computing, vol. 6, pp. 85-112, 2010.
Crossref Google Scholar
[35]
M. Frick, Generalized model-checking over locally tree-decomposable classes, Theory of Computing Systems, vol. 37, no. 1, pp. 157-191, 2004.
Crossref Google Scholar
[36]
M. Frick and M. Grohe, Deciding first-order properties of locally tree-decomposable structures, Journal of the ACM, vol. 48, no. 6, pp. 1184-1206, 2001.
Crossref Google Scholar
[37]
P. Lu, Complexity dichotomies of counting problems, in Electronic Colloquium on Computational Complexity (ECCC), vol. 18, p. 93, 2011.
Google Scholar
[38]
V. Chandrasekaran, N. Srebro, and P. Harsha, Complexity of inference in graphical models, in Proceedings of the 24th Conference in Uncertainty in Artificial Intelligence (UAI’08), pp. 70-78, 2008.
[39]
C. Chekuri and J. Chuzhoy, Polynomial bounds for the grid-minor theorem, arXiv preprint arXiv:1305.6577, 2013.
Crossref
[40]
T. Feder and M. Y. Vardi, The computational structure of monotone monadic SNP and constraint satisfaction: A study through datalog and group theory, SIAM Journal on Computing, vol. 28, no. 1, pp. 57-104, 1998.
Crossref Google Scholar
[41]
M. Grohe, The complexity of homomorphism and constraint satisfaction problems seen from the other side, Journal of the ACM, vol. 54, no. 1, 2007.
Crossref Google Scholar
[42]
V. Dalmau and P. Jonsson, The complexity of counting homomorphisms seen from the other side, Theoretical Computer Science, vol. 329, nos. 1-3, pp. 315-323, 2004.
Crossref Google Scholar
[43]
M. Jerrum, A. Sinclair, and E. Vigoda, A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries, Journal of the ACM, vol. 51, no. 4, pp. 671-697, 2004.
Crossref Google Scholar
[44]
M. Jerrum and K. Meeks, The parameterised complexity of counting connected subgraphs and graph motifs, 2013, arXiv: 1308. 1575.
[45]
M. Bayati, D. Gamarnik, D. Katz, C. Nair, and P. Tetali, Simple deterministic approximation algorithms for counting matchings, in Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC’07), 2007, pp. 122-127.
Crossref
[46]
D. Weitz, Counting independent sets up to the tree threshold, in Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC’06), 2006, pp. 140-149.
Crossref
[47]
M. Thurley, Kernelizations for parameterized counting problems, in Proceedings of the 4th International Conference on Theory and Applications of Models of Computation (TAMC’07), Springer, 2007, pp. 703-714.
Crossref
[48]
J. A. Montoya and M. Müller, Parameterized random complexity, Theory of Computing Systems, vol. 52, no. 2, pp. 221-270, 2013.
Crossref Google Scholar
Tsinghua Science and Technology
Volume 19 Issue 4,
August 2014
Pages 410-420
DOI: 10.1109/TST.2014.6867521
Cite this article:
Zhang C, Chen Y. Counting Problems in Parameterized Complexity. Tsinghua Science and Technology, 2014, 19(4): 410-420. https://doi.org/10.1109/TST.2014.6867521

441

Views

7

Downloads

2

Crossref

N/A

Web of Science

2

Scopus

0

CSCD

Altmetrics
Received: 09 June 2014
Accepted: 13 June 2014
Published: 30 July 2014
© The author(s) 2014
Return