{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,17]],"date-time":"2026-07-17T03:11:05Z","timestamp":1784257865817,"version":"3.55.0"},"reference-count":11,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2015,7,9]],"date-time":"2015-07-09T00:00:00Z","timestamp":1436400000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/I011935\/1"],"award-info":[{"award-number":["EP\/I011935\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2015,7,9]]},"abstract":"\n We consider parameterized subgraph counting problems of the following form: given a graph\n G<\/jats:italic>\n , how many\n k<\/jats:italic>\n -tuples of its vertices induce a subgraph with a given property? A number of such problems are known to be #W[1]-complete; here, we substantially generalize some of these existing results by proving hardness for two large families of such problems. We demonstrate that it is #W[1]-hard to count the number of\n k<\/jats:italic>\n -vertex subgraphs having any property where the number of distinct edge densities of labeled subgraphs that satisfy the property is\n o<\/jats:italic>\n (\n k<\/jats:italic>\n 2<\/jats:sup>\n ). In the special case in which the property in question depends only on the number of edges in the subgraph, we give a strengthening of this result, which leads to our second family of hard problems.\n <\/jats:p>","DOI":"10.1145\/2786017","type":"journal-article","created":{"date-parts":[[2015,7,10]],"date-time":"2015-07-10T14:10:15Z","timestamp":1436537415000},"page":"1-18","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["Some Hard Families of Parameterized Counting Problems"],"prefix":"10.1145","volume":"7","author":[{"given":"Mark","family":"Jerrum","sequence":"first","affiliation":[{"name":"Queen Mary University of London, London UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kitty","family":"Meeks","sequence":"additional","affiliation":[{"name":"Queen Mary University of London"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2015,7,9]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"ISAAC 2002 (LNCS), P. Bose and P. Morin (Eds.)","volume":"2518","author":"Arvind V.","unstructured":"V. Arvind and V. Raman . 2002. Approximation algorithms for some parameterized counting problems . In ISAAC 2002 (LNCS), P. Bose and P. Morin (Eds.) , Vol. 2518 . Springer-Verlag, Berlin, 453--464. V. Arvind and V. Raman. 2002. Approximation algorithms for some parameterized counting problems. In ISAAC 2002 (LNCS), P. Bose and P. Morin (Eds.), Vol. 2518. Springer-Verlag, Berlin, 453--464."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2007.21"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70575-8_48"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39206-1_30"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.22"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.08.008"},{"key":"e_1_2_1_7_1","first-page":"464","article-title":"A combinatorial problem in geometry","volume":"2","author":"Erd\u0151s P.","year":"1935","unstructured":"P. Erd\u0151s and G. Szekeres . 1935 . A combinatorial problem in geometry . Compositio Mathematics 2 (1935), 464 -- 470 . P. Erd\u0151s and G. Szekeres. 1935. A combinatorial problem in geometry. Compositio Mathematics 2 (1935), 464--470.","journal-title":"Compositio Mathematics"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.09.065"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703427203"},{"key":"e_1_2_1_10_1","unstructured":"J. Flum and M. Grohe. 2006. Parameterized Complexity Theory. Springer. J. Flum and M. Grohe. 2006. Parameterized Complexity Theory. Springer."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2014.11.015"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2786017","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2786017","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:43:15Z","timestamp":1750225395000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2786017"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,7,9]]},"references-count":11,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,7,9]]}},"alternative-id":["10.1145\/2786017"],"URL":"https:\/\/doi.org\/10.1145\/2786017","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,7,9]]},"assertion":[{"value":"2014-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-07-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}