Abstract
We consider the problem of counting, in a given graph, the number of induced k-vertex subgraphs which have an even number of edges, and also the complementary problem of counting the k-vertex induced subgraphs having an odd number of edges. We demonstrate that both problems are #W[1]-hard when parameterised by k, in fact proving a somewhat stronger result about counting subgraphs with a property that only holds for some subset of k-vertex subgraphs which have an even (respectively odd) number of edges. On the other hand, we show that each of the problems admits an FPTRAS. These approximation schemes are based on a surprising structural result, which exploits ideas from Ramsey theory.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
V. Arvind and V. Raman: Approximation algorithms for some parameterized counting problems, in: ISAAC 2002 (P. Bose and P. Morin, eds.), LNCS, vol. 2518, Springer-Verlag Berlin Heidelberg, 2002, 453-464.
B. V. R. Bhat: On greatest common divisor matrices and their applications, Linear Algebra and its Applications 158 (1991), 77-97.
Y. Chen and J. Flum: On parameterized path and chordless path problems, Compu-tational Complexity, 2007. Twenty-Second Annual IEEE Conference on, 2007, 250-263.
Y. Chen, M. Thurley and M. Weyer: Understanding the complexity of induced subgraph isomorphisms, Automata, Languages and Programming (Luca Aceto, Ivan Damgard, Leslie Ann Goldberg, Magnús M. Halldórsson, Anna Ingólfsdóttir, and Igor Walukiewicz, eds.), Lecture Notes in Computer Science, vol. 5125, Springer Berlin Heidelberg, 2008, 587-596.
R. Curticapean: Counting matchings of size k is #W[1]-hard, Automata, Languages, and Programming (Fedor V. Fomin, Rusins Freivalds, Marta Kwiatkowska, and David Peleg, eds.), Lecture Notes in Computer Science, vol. 7965, Springer Berlin Heidelberg, 2013, 352-363.
R. Curticapean and D. Marx: Complexity of counting subgraphs: Only the bound-edness of the vertex-cover number counts, 55th Annual IEEE Symposium on Foun-dations of Computer Science.
A. Ehrenfeucht and M. Karpinski: The computational complexity of (XOR, AND)-counting problems, Technical report TR-90-033, ICSI, Berkeley, 1990.
P. Erdos and G. Szekeres: A combinatorial problem in geometry, Compositio Math. 2 (1935), 464-470.
M. Fellows, D. Hermelin, F. Rosamond and S. Vialette: On the parameterized complexity of multiple-interval graph problems, Theoretical Computer Science 410 (2009), 53-61.
J. Flum and M. Grohe: The parameterized complexity of counting problems, SIAM Journal on Computing 33 (2004), 892-922.
J. Flum and M. Grohe: Parameterized complexity theory, Springer, 2006.
L. Goldberg, M. Grohe, M. Jerrum and M. Thurley: A complexity dichotomy for partition functions with mixed signs, SIAM Journal on Computing 39 (2010), 3336-3402.
P. Haukkanen: On meet matrices on posets, Linear Algebra and its Applications 249 (1996), 111-123.
M. Jerrum and K. Meeks: The parameterised complexity of counting connected subgraphs and graph motifs, Journal of Computer and System Sciences 81 (2015), 702-716.
M. Jerrum and K. Meeks: Some hard families of parameterised counting problems, ACM Trans. Comput. Theory 7 (2015), 1-26.
R. Lidl and H. Niederreiter: Finite fields, Encyclopedia of Mathematics and its Applications, vol. 20, Addison-Wesley, 1983.
K. Meeks: The challenges of unbounded treewidth in parameterised subgraph count-ing problems, Discrete Applied Mathematics 198 (2016), 170-194.
Author information
Authors and Affiliations
Corresponding author
Additional information
Research supported by EPSRC grant EP/I011935/1 (“Computational Counting”)
This work was undertaken when Kitty Meeks was affiliated with the School of Mathematical Sciences, Queen Mary University of London
Rights and permissions
About this article
Cite this article
Jerrum, M., Meeks, K. The parameterised complexity of counting even and odd induced subgraphs. Combinatorica 37, 965–990 (2017). https://doi.org/10.1007/s00493-016-3338-5
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00493-016-3338-5