{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T04:23:45Z","timestamp":1775622225954,"version":"3.50.1"},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2016,10,24]],"date-time":"2016-10-24T00:00:00Z","timestamp":1477267200000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2017,10]]},"DOI":"10.1007\/s00493-016-3338-5","type":"journal-article","created":{"date-parts":[[2016,10,24]],"date-time":"2016-10-24T08:11:04Z","timestamp":1477296664000},"page":"965-990","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["The parameterised complexity of counting even and odd induced subgraphs"],"prefix":"10.1007","volume":"37","author":[{"given":"Mark","family":"Jerrum","sequence":"first","affiliation":[]},{"given":"Kitty","family":"Meeks","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,10,24]]},"reference":[{"key":"3338_CR1","first-page":"453","volume":"2518","author":"V. Arvind","year":"2002","unstructured":"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.","journal-title":"ISAAC 2002"},{"key":"3338_CR2","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1016\/0024-3795(91)90051-W","volume":"158","author":"B. V. R. Bhat","year":"1991","unstructured":"B. V. R. Bhat: On greatest common divisor matrices and their applications, Linear Algebra and its Applications\n158 (1991), 77-97.","journal-title":"Linear Algebra and its Applications"},{"key":"3338_CR3","first-page":"250","volume-title":"On parameterized path and chordless path problems","author":"Y. Chen","year":"2007","unstructured":"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."},{"key":"3338_CR4","first-page":"587","volume":"5125","author":"Y. Chen","year":"2008","unstructured":"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\u00fas M. Halld\u00f3rsson, Anna Ing\u00f3lfsd\u00f3ttir, and Igor Walukiewicz, eds.), Lecture Notes in Computer Science, vol. 5125, Springer Berlin Heidelberg, 2008, 587-596.","journal-title":"Understanding the complexity of induced subgraph isomorphisms"},{"key":"3338_CR5","first-page":"352","volume-title":"Counting matchings of size k is #W[1]-hard","author":"R. Curticapean","year":"2013","unstructured":"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."},{"key":"3338_CR6","unstructured":"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."},{"key":"3338_CR7","volume-title":"The computational complexity of (XOR, AND)-counting problems","author":"A. Ehrenfeucht","year":"1990","unstructured":"A. Ehrenfeucht and M. Karpinski: The computational complexity of (XOR, AND)-counting problems, Technical report TR-90-033, ICSI, Berkeley, 1990."},{"key":"3338_CR8","first-page":"464","volume":"2","author":"P. Erdos","year":"1935","unstructured":"P. Erdos and G. Szekeres: A combinatorial problem in geometry, Compositio Math. 2 (1935), 464-470.","journal-title":"Compositio Math"},{"key":"3338_CR9","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/j.tcs.2008.09.065","volume":"410","author":"M. Fellows","year":"2009","unstructured":"M. Fellows, D. Hermelin, F. Rosamond and S. Vialette: On the parameterized complexity of multiple-interval graph problems, Theoretical Computer Science\n410 (2009), 53-61.","journal-title":"Theoretical Computer Science"},{"key":"3338_CR10","doi-asserted-by":"crossref","first-page":"892","DOI":"10.1137\/S0097539703427203","volume":"33","author":"J. Flum","year":"2004","unstructured":"J. Flum and M. Grohe: The parameterized complexity of counting problems, SIAM Journal on Computing\n33 (2004), 892-922.","journal-title":"SIAM Journal on Computing"},{"key":"3338_CR11","volume-title":"Parameterized complexity theory","author":"J. Flum","year":"2006","unstructured":"J. Flum and M. Grohe: Parameterized complexity theory, Springer, 2006."},{"key":"3338_CR12","doi-asserted-by":"crossref","first-page":"3336","DOI":"10.1137\/090757496","volume":"39","author":"L. Goldberg","year":"2010","unstructured":"L. Goldberg, M. Grohe, M. Jerrum and M. Thurley: A complexity dichotomy for partition functions with mixed signs, SIAM Journal on Computing\n39 (2010), 3336-3402.","journal-title":"SIAM Journal on Computing"},{"key":"3338_CR13","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1016\/0024-3795(95)00349-5","volume":"249","author":"P. Haukkanen","year":"1996","unstructured":"P. Haukkanen: On meet matrices on posets, Linear Algebra and its Applications\n249 (1996), 111-123.","journal-title":"Linear Algebra and its Applications"},{"key":"3338_CR14","doi-asserted-by":"crossref","first-page":"702","DOI":"10.1016\/j.jcss.2014.11.015","volume":"81","author":"M. Jerrum","year":"2015","unstructured":"M. Jerrum and K. Meeks: The parameterised complexity of counting connected subgraphs and graph motifs, Journal of Computer and System Sciences\n81 (2015), 702-716.","journal-title":"Journal of Computer and System Sciences"},{"key":"3338_CR15","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2786017","volume":"7","author":"M. Jerrum","year":"2015","unstructured":"M. Jerrum and K. Meeks: Some hard families of parameterised counting problems, ACM Trans. Comput. Theory\n7 (2015), 1-26.","journal-title":"ACM Trans. Comput. Theory"},{"key":"3338_CR16","unstructured":"R. Lidl and H. Niederreiter: Finite fields, Encyclopedia of Mathematics and its Applications, vol. 20, Addison-Wesley, 1983."},{"key":"3338_CR17","doi-asserted-by":"crossref","first-page":"170","DOI":"10.1016\/j.dam.2015.06.019","volume":"198","author":"K. Meeks","year":"2016","unstructured":"K. Meeks: The challenges of unbounded treewidth in parameterised subgraph count-ing problems, Discrete Applied Mathematics\n198 (2016), 170-194.","journal-title":"Discrete Applied Mathematics"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00493-016-3338-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-016-3338-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-016-3338-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,12,14]],"date-time":"2017-12-14T18:58:49Z","timestamp":1513277929000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00493-016-3338-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,10,24]]},"references-count":17,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2017,10]]}},"alternative-id":["3338"],"URL":"https:\/\/doi.org\/10.1007\/s00493-016-3338-5","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,10,24]]}}}