{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T20:15:44Z","timestamp":1768767344020,"version":"3.49.0"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2021,12,7]],"date-time":"2021-12-07T00:00:00Z","timestamp":1638835200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,12,7]],"date-time":"2021-12-07T00:00:00Z","timestamp":1638835200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["786580"],"award-info":[{"award-number":["786580"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,2]]},"abstract":"Abstract<\/jats:title>We study the problem $$\\#\\textsc {IndSub}(\\varPhi )$$<\/jats:tex-math>\n \n #<\/mml:mo>\n I<\/mml:mi>\n \n N<\/mml:mi>\n D<\/mml:mi>\n S<\/mml:mi>\n U<\/mml:mi>\n B<\/mml:mi>\n <\/mml:mstyle>\n (<\/mml:mo>\n \u03a6<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> of counting all induced subgraphs of size k<\/jats:italic> in a graph G<\/jats:italic> that satisfy the property $$\\varPhi $$<\/jats:tex-math>\n \u03a6<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. It is shown that, given any<\/jats:italic> graph property $$\\varPhi $$<\/jats:tex-math>\n \u03a6<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> that distinguishes independent sets from bicliques, $$\\#\\textsc {IndSub}(\\varPhi )$$<\/jats:tex-math>\n \n #<\/mml:mo>\n I<\/mml:mi>\n \n N<\/mml:mi>\n D<\/mml:mi>\n S<\/mml:mi>\n U<\/mml:mi>\n B<\/mml:mi>\n <\/mml:mstyle>\n (<\/mml:mo>\n \u03a6<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is hard for the class $$\\#\\mathsf {W[1]}$$<\/jats:tex-math>\n \n #<\/mml:mo>\n \n W<\/mml:mi>\n [<\/mml:mo>\n 1<\/mml:mn>\n ]<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, i.e., the parameterized counting equivalent of $${{\\mathsf {N}}}{{\\mathsf {P}}}$$<\/jats:tex-math>\n \n N<\/mml:mi>\n P<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Under additional suitable density conditions on $$\\varPhi $$<\/jats:tex-math>\n \u03a6<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, satisfied e.g. by non-trivial monotone properties on bipartite graphs, we strengthen $$\\#\\mathsf {W[1]}$$<\/jats:tex-math>\n \n #<\/mml:mo>\n \n W<\/mml:mi>\n [<\/mml:mo>\n 1<\/mml:mn>\n ]<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-hardness by establishing that $$\\#\\textsc {IndSub}(\\varPhi )$$<\/jats:tex-math>\n \n #<\/mml:mo>\n I<\/mml:mi>\n \n N<\/mml:mi>\n D<\/mml:mi>\n S<\/mml:mi>\n U<\/mml:mi>\n B<\/mml:mi>\n <\/mml:mstyle>\n (<\/mml:mo>\n \u03a6<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> cannot be solved in time $$f(k)\\cdot n^{o(k)}$$<\/jats:tex-math>\n \n f<\/mml:mi>\n \n (<\/mml:mo>\n k<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \u00b7<\/mml:mo>\n \n n<\/mml:mi>\n \n o<\/mml:mi>\n (<\/mml:mo>\n k<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> for any computable function f<\/jats:italic>, unless the Exponential Time Hypothesis fails. Finally, we observe that our results remain true even if the input graph G<\/jats:italic> is restricted to be bipartite and counting is done modulo a fixed prime.<\/jats:p>","DOI":"10.1007\/s00453-021-00894-9","type":"journal-article","created":{"date-parts":[[2021,12,7]],"date-time":"2021-12-07T13:02:54Z","timestamp":1638882174000},"page":"379-404","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Counting Induced Subgraphs: An Algebraic Approach to #W[1]-Hardness"],"prefix":"10.1007","volume":"84","author":[{"given":"Julian","family":"D\u00f6rfler","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3159-9418","authenticated-orcid":false,"given":"Marc","family":"Roth","sequence":"additional","affiliation":[]},{"given":"Johannes","family":"Schmitt","sequence":"additional","affiliation":[]},{"given":"Philip","family":"Wellnitz","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,12,7]]},"reference":[{"key":"894_CR1","doi-asserted-by":"publisher","unstructured":"Abhyankar, S.S.: Lectures on algebra, vol. I. World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ (2006). https:\/\/doi.org\/10.1142\/9789812773449","DOI":"10.1142\/9789812773449"},{"key":"894_CR2","doi-asserted-by":"publisher","unstructured":"Biggs, N.: Algebraic graph theory, 2nd (edn.). Cambridge Mathematical Library. Cambridge University Press, Cambridge (1993). https:\/\/doi.org\/10.1017\/CBO9780511608704","DOI":"10.1017\/CBO9780511608704"},{"key":"894_CR3","doi-asserted-by":"publisher","unstructured":"Bj\u00f6rklund, A., Dell, H., Husfeldt, T.: The parity of set systems under random restrictions with applications to exponential time problems. In: Automata, Languages, and Programming\u201442nd International Colloquium, ICALP 2015, Kyoto, Japan, 6\u201310 July, 2015, Proceedings, Part I, pp. 231\u2013242 (2015). https:\/\/doi.org\/10.1007\/978-3-662-47672-7_19","DOI":"10.1007\/978-3-662-47672-7_19"},{"key":"894_CR4","doi-asserted-by":"publisher","unstructured":"Chen, H., Mengel, S.: Counting answers to existential positive queries: A complexity classification. In: Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2016, San Francisco, CA, USA, June 26\u2013July 01, 2016, pp. 315\u2013326 (2016). https:\/\/doi.org\/10.1145\/2902251.2902279","DOI":"10.1145\/2902251.2902279"},{"issue":"2","key":"894_CR5","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1016\/j.ic.2005.05.001","volume":"201","author":"J Chen","year":"2005","unstructured":"Chen, J., Chor, B., Fellows, M., Huang, X., Juedes, D.W., Kanj, I.A., Xia, G.: Tight lower bounds for certain parameterized NP-hard problems. Inf. Comput. 201(2), 216\u2013231 (2005). https:\/\/doi.org\/10.1016\/j.ic.2005.05.001","journal-title":"Inf. Comput."},{"issue":"8","key":"894_CR6","doi-asserted-by":"publisher","first-page":"1346","DOI":"10.1016\/j.jcss.2006.04.007","volume":"72","author":"J Chen","year":"2006","unstructured":"Chen, J., Huang, X., Kanj, I.A., Xia, G.: Strong computational lower bounds via parameterized complexity. J. Comput. Syst. Sci. 72(8), 1346\u20131367 (2006). https:\/\/doi.org\/10.1016\/j.jcss.2006.04.007","journal-title":"J. Comput. Syst. Sci."},{"key":"894_CR7","unstructured":"Curticapean, R.: The simple, little and slow things count: On parameterized counting complexity. Ph.D. thesis, Saarland University (2015). http:\/\/scidok.sulb.uni-saarland.de\/volltexte\/2015\/6217\/"},{"key":"894_CR8","doi-asserted-by":"publisher","unstructured":"Curticapean, R., Dell, H., Marx, D.: Homomorphisms are a good basis for counting small subgraphs. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, 19\u201323 June, 2017, pp. 210\u2013223 (2017). https:\/\/doi.org\/10.1145\/3055399.3055502","DOI":"10.1145\/3055399.3055502"},{"issue":"1\u20133","key":"894_CR9","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/j.tcs.2004.08.008","volume":"329","author":"V Dalmau","year":"2004","unstructured":"Dalmau, V., Jonsson, P.: The complexity of counting homomorphisms seen from the other side. Theor. Comput. Sci. 329(1\u20133), 315\u2013323 (2004). https:\/\/doi.org\/10.1016\/j.tcs.2004.08.008","journal-title":"Theor. Comput. Sci."},{"key":"894_CR10","doi-asserted-by":"publisher","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"J Edmonds","year":"1965","unstructured":"Edmonds, J.: Paths, trees, and flowers. Can. J. Math. 17, 449\u2013467 (1965). https:\/\/doi.org\/10.4153\/CJM-1965-045-4","journal-title":"Can. J. Math."},{"issue":"4","key":"894_CR11","doi-asserted-by":"publisher","first-page":"892","DOI":"10.1137\/S0097539703427203","volume":"33","author":"J Flum","year":"2004","unstructured":"Flum, J., Grohe, M.: The parameterized complexity of counting problems. SIAM J. Comput. 33(4), 892\u2013922 (2004). https:\/\/doi.org\/10.1137\/S0097539703427203","journal-title":"SIAM J. Comput."},{"key":"894_CR12","doi-asserted-by":"publisher","unstructured":"Flum, J., Grohe, M.: Parameterized complexity theory. Texts in Theoretical Computer Science. An EATCS Series. Springer (2006). https:\/\/doi.org\/10.1007\/3-540-29953-X","DOI":"10.1007\/3-540-29953-X"},{"issue":"4","key":"894_CR13","doi-asserted-by":"publisher","first-page":"702","DOI":"10.1016\/j.jcss.2014.11.015","volume":"81","author":"M Jerrum","year":"2015","unstructured":"Jerrum, M., Meeks, K.: The parameterised complexity of counting connected subgraphs and graph motifs. J. Comput. Syst. Sci. 81(4), 702\u2013716 (2015). https:\/\/doi.org\/10.1016\/j.jcss.2014.11.015","journal-title":"J. Comput. Syst. Sci."},{"key":"894_CR14","doi-asserted-by":"publisher","unstructured":"Jerrum, M., Meeks, K.: Some hard families of parameterized counting problems. TOCT 7(3), 11:1\u201311:18 (2015). https:\/\/doi.org\/10.1145\/2786017","DOI":"10.1145\/2786017"},{"issue":"5","key":"894_CR15","doi-asserted-by":"publisher","first-page":"965","DOI":"10.1007\/s00493-016-3338-5","volume":"37","author":"M Jerrum","year":"2017","unstructured":"Jerrum, M., Meeks, K.: The parameterised complexity of counting even and odd induced subgraphs. Combinatorica 37(5), 965\u2013990 (2017). https:\/\/doi.org\/10.1007\/s00493-016-3338-5","journal-title":"Combinatorica"},{"issue":"4","key":"894_CR16","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1007\/BF02579140","volume":"4","author":"J Kahn","year":"1984","unstructured":"Kahn, J., Saks, M.E., Sturtevant, D.: A topological approach to evasiveness. Combinatorica 4(4), 297\u2013306 (1984). https:\/\/doi.org\/10.1007\/BF02579140","journal-title":"Combinatorica"},{"key":"894_CR17","doi-asserted-by":"crossref","unstructured":"Lov\u00e1sz, L.: Large networks and graph limits, Colloquium Publications, vol.\u00a060. American Mathematical Society (2012). http:\/\/www.ams.org\/bookstore-getitem\/item=COLL-60","DOI":"10.1090\/coll\/060"},{"issue":"1\u20133","key":"894_CR18","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1016\/j.apal.2005.06.010","volume":"138","author":"C McCartin","year":"2006","unstructured":"McCartin, C.: Parameterized counting problems. Ann. Pure Appl. Logic 138(1\u20133), 147\u2013182 (2006). https:\/\/doi.org\/10.1016\/j.apal.2005.06.010","journal-title":"Ann. Pure Appl. Logic"},{"key":"894_CR19","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1016\/j.dam.2015.06.019","volume":"198","author":"K Meeks","year":"2016","unstructured":"Meeks, K.: The challenges of unbounded treewidth in parameterised subgraph counting problems. Discrete Appl. Math. 198, 170\u2013194 (2016). https:\/\/doi.org\/10.1016\/j.dam.2015.06.019","journal-title":"Discrete Appl. Math."},{"issue":"4","key":"894_CR20","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1561\/0400000055","volume":"7","author":"CA Miller","year":"2013","unstructured":"Miller, C.A.: Evasiveness of graph properties and topological fixed-point theorems. Found. Trends Theor. Comput. Sci. 7(4), 337\u2013415 (2013). https:\/\/doi.org\/10.1561\/0400000055","journal-title":"Found. Trends Theor. Comput. Sci."},{"key":"894_CR21","doi-asserted-by":"publisher","unstructured":"Rivest, R.L., Vuillemin, J.: On recognizing graph properties from adjacency matrices. Theoret. Comput. Sci. 3(3), 371\u2013384 (1976\/77). https:\/\/doi.org\/10.1016\/0304-3975(76)90053-0","DOI":"10.1016\/0304-3975(76)90053-0"},{"key":"894_CR22","doi-asserted-by":"publisher","unstructured":"Roth, M., Schmitt, J.: Counting induced subgraphs: A topological approach to #W[1]-hardness. In: 13th International Symposium on Parameterized and Exact Computation, IPEC 2018, 20\u201324 August, 2018, Helsinki, Finland, pp. 24:1\u201324:14 (2018). https:\/\/doi.org\/10.4230\/LIPIcs.IPEC.2018.24","DOI":"10.4230\/LIPIcs.IPEC.2018.24"},{"issue":"5","key":"894_CR23","doi-asserted-by":"publisher","first-page":"865","DOI":"10.1137\/0220053","volume":"20","author":"S Toda","year":"1991","unstructured":"Toda, S.: PP is as hard as the polynomial-time hierarchy. SIAM J. Comput. 20(5), 865\u2013877 (1991). https:\/\/doi.org\/10.1137\/0220053","journal-title":"SIAM J. Comput."},{"key":"894_CR24","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"LG Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of computing the permanent. Theor. Comput. Sci. 8, 189\u2013201 (1979). https:\/\/doi.org\/10.1016\/0304-3975(79)90044-6","journal-title":"Theor. Comput. Sci."},{"key":"894_CR25","doi-asserted-by":"publisher","first-page":"534","DOI":"10.2307\/2033425","volume":"6","author":"AJ Weir","year":"1955","unstructured":"Weir, A.J.: The Sylow subgroups of the symmetric groups. Proc. Amer. Math. Soc. 6, 534\u2013541 (1955). https:\/\/doi.org\/10.2307\/2033425","journal-title":"Proc. Amer. Math. Soc."},{"key":"894_CR26","doi-asserted-by":"publisher","unstructured":"Williams, V.V., Wang, J.R., Williams, R.R., Yu, H.: Finding four-node subgraphs in triangle time. In: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, 4\u20136 January, 2015, pp. 1671\u20131680 (2015). https:\/\/doi.org\/10.1137\/1.9781611973730.111","DOI":"10.1137\/1.9781611973730.111"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00894-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00894-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00894-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,2,15]],"date-time":"2022-02-15T07:05:10Z","timestamp":1644908710000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00894-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,12,7]]},"references-count":26,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,2]]}},"alternative-id":["894"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00894-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,12,7]]},"assertion":[{"value":"13 October 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 November 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 December 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declaration"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}