Abstract
We prove \(\sharp\) W[1]-hardness of the following parameterized counting problem: Given a simple undirected graph G and a parameter k ∈ ℕ, compute the number of matchings of size k in G.
It is known from [1] that, given an edge-weighted graph G, computing a particular weighted sum over the matchings in G is \(\sharp\) W[1]-hard. In the present paper, we exhibit a reduction that does not require weights.
This solves an open problem from [5] and adds a natural parameterized counting problem to the scarce list of \(\sharp\) W[1]-hard problems. Since the classical version of this problem is well-studied, we believe that our result facilitates future \(\sharp\) W[1]-hardness proofs for other 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.
References
Bläser, M., Curticapean, R.: Weighted counting of k-matchings is #W[1]-hard. In: Thilikos, D.M., Woeginger, G.J. (eds.) IPEC 2012. LNCS, vol. 7535, pp. 171–181. Springer, Heidelberg (2012)
Courcelle, B.: The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Information and Computation 85(1), 12–75 (1990)
Ehrenborg, R., Rota, G.-C.: Apolarity and canonical forms for homogeneous polynomials. European Journal of Combinatorics 14(3), 157–181 (1993)
Flum, J., Grohe, M.: The parameterized complexity of counting problems. SIAM Journal on Computing, 538–547 (2002)
Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer-Verlag New York, Inc., Secaucus (2006)
Hartshorne, R.: Algebraic geometry. Springer (1977)
Makowsky, J.: Algorithmic uses of the Feferman-Vaught theorem. Annals of Pure and Applied Logic 126, 159–213 (2004)
Schwartz, J.: Fast probabilistic algorithms for verification of polynomial identities. J. ACM 27(4), 701–717 (1980)
Temperley, H., Fisher, M.: Dimer problem in statistical mechanics - an exact result. Philosophical Magazine 6(68) (1961) 1478–6435
Valiant, L.: The complexity of computing the permanent. Theoretical Computer Science 8(2), 189–201 (1979)
Valiant, L.: The complexity of enumeration and reliability problems. SIAM Journal on Computing 8(3), 410–421 (1979)
Valiant, L.: Holographic algorithms. In: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2004, pp. 306–315 (2004)
Vassilevska, V., Williams, R.: Finding, minimizing, and counting weighted subgraphs. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, pp. 455–464. ACM, New York (2009)
Xia, M., Zhang, P., Zhao, W.: Computational complexity of counting problems on 3-regular planar graphs. Theor. Comp. Sc. 384(1), 111–125 (2007)
Zippel, R.: Probabilistic algorithms for sparse polynomials. In: Ng, K.W. (ed.) EUROSAM 1979 and ISSAC 1979. LNCS, vol. 72, pp. 216–226. Springer, Heidelberg (1979)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Curticapean, R. (2013). Counting Matchings of Size k Is \(\sharp\) W[1]-Hard. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds) Automata, Languages, and Programming. ICALP 2013. Lecture Notes in Computer Science, vol 7965. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-39206-1_30
Download citation
DOI: https://doi.org/10.1007/978-3-642-39206-1_30
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-39205-4
Online ISBN: 978-3-642-39206-1
eBook Packages: Computer ScienceComputer Science (R0)