{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,17]],"date-time":"2026-01-17T03:52:01Z","timestamp":1768621921919,"version":"3.49.0"},"reference-count":61,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2021,3,11]],"date-time":"2021-03-11T00:00:00Z","timestamp":1615420800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,3,11]],"date-time":"2021-03-11T00:00:00Z","timestamp":1615420800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2021,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We study the parameterized complexity of the problem of counting graph homomorphisms with given partial injectivity constraints, i.e., inequalities between pairs of vertices, which subsumes counting of graph homomorphisms, subgraph counting and, more generally, counting of answers to equi-join queries with inequalities. Our main result presents an exhaustive complexity classification for the problem in fixed-parameter tractable and <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\#\\mathsf {W[1]}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mo>#<\/mml:mo>\n                    <mml:mrow>\n                      <mml:mi>W<\/mml:mi>\n                      <mml:mo>[<\/mml:mo>\n                      <mml:mn>1<\/mml:mn>\n                      <mml:mo>]<\/mml:mo>\n                    <\/mml:mrow>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-complete cases. The proof relies on the framework of linear combinations of homomorphisms as independently discovered by Chen and Mengel (PODS\u00a016) and by Curticapean, Dell and Marx in the recent breakthrough result regarding the exact complexity of the subgraph counting problem (STOC\u00a017). Moreover, we invoke Rota\u2019s NBC-Theorem to obtain an explicit criterion for fixed-parameter tractability based on treewidth. The abstract classification theorem is then applied to the problem of counting locally injective graph homomorphisms from small pattern graphs to large target graphs. As a consequence, we are able to fully classify its parameterized complexity depending on the class of allowed pattern graphs.\n<\/jats:p>","DOI":"10.1007\/s00453-021-00805-y","type":"journal-article","created":{"date-parts":[[2021,3,11]],"date-time":"2021-03-11T06:02:56Z","timestamp":1615442576000},"page":"1829-1860","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Parameterized Counting of Partially Injective Homomorphisms"],"prefix":"10.1007","volume":"83","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3159-9418","authenticated-orcid":false,"given":"Marc","family":"Roth","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,3,11]]},"reference":[{"key":"805_CR1","first-page":"203","volume":"28","author":"T van Aardenne-Ehrenfest","year":"1951","unstructured":"van Aardenne-Ehrenfest, T., de Bruijn, N.G.: Circuits and trees in oriented linear graphs. Simon Stevin: Wis- en Natuurkundig Tijdschrift 28, 203\u2013217 (1951)","journal-title":"Simon Stevin: Wis- en Natuurkundig Tijdschrift"},{"key":"805_CR2","doi-asserted-by":"publisher","unstructured":"Backens, M.: A Complete Dichotomy for Complex-Valued Holant$$^c$$. In: 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, pp. 12:1\u201312:14 (2018). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2018.12","DOI":"10.4230\/LIPIcs.ICALP.2018.12"},{"key":"805_CR3","doi-asserted-by":"publisher","unstructured":"Barvinok, A.I.: Combinatorics and Complexity of Partition Functions, Algorithms and combinatorics, vol.\u00a030. Springer (2016). https:\/\/doi.org\/10.1007\/978-3-319-51829-9","DOI":"10.1007\/978-3-319-51829-9"},{"key":"805_CR4","doi-asserted-by":"publisher","unstructured":"Brand, C., Roth, M.: Parameterized Counting of Trees, Forests and Matroid Bases. In: Computer Science - Theory and Applications - 12th International Computer Science Symposium in Russia, CSR 2017, Kazan, Russia, June 8-12, 2017, Proceedings, pp. 85\u201398 (2017). https:\/\/doi.org\/10.1007\/978-3-319-58747-9_10","DOI":"10.1007\/978-3-319-58747-9_10"},{"key":"805_CR5","doi-asserted-by":"publisher","unstructured":"Bulatov, A.A.: A Dichotomy Theorem for Nonuniform CSPs. In: 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pp. 319\u2013330 (2017). https:\/\/doi.org\/10.1109\/FOCS.2017.37","DOI":"10.1109\/FOCS.2017.37"},{"key":"805_CR6","doi-asserted-by":"publisher","unstructured":"Cai, J., Fu, Z., Guo, H., Williams, T.: A Holant Dichotomy: Is the FKT Algorithm Universal? In: IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pp. 1259\u20131276 (2015). https:\/\/doi.org\/10.1109\/FOCS.2015.81","DOI":"10.1109\/FOCS.2015.81"},{"issue":"3","key":"805_CR7","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1007\/s00453-012-9626-6","volume":"64","author":"J Cai","year":"2012","unstructured":"Cai, J., Huang, S., Lu, P.: From Holant to #CSP and Back: Dichotomy for Holant$$^c$$ Problems. Algorithmica 64(3), 511\u2013533 (2012). https:\/\/doi.org\/10.1007\/s00453-012-9626-6","journal-title":"Algorithmica"},{"issue":"1","key":"805_CR8","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/j.jcss.2010.06.005","volume":"77","author":"J Cai","year":"2011","unstructured":"Cai, J., Lu, P.: Holographic algorithms: From art to science. J. Comput. Syst. Sci. 77(1), 41\u201361 (2011). https:\/\/doi.org\/10.1016\/j.jcss.2010.06.005","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"805_CR9","doi-asserted-by":"publisher","first-page":"853","DOI":"10.1137\/16M1073984","volume":"46","author":"J Cai","year":"2017","unstructured":"Cai, J., Lu, P., Xia, M.: Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP. SIAM J. Comput. 46(3), 853\u2013889 (2017). https:\/\/doi.org\/10.1137\/16M1073984","journal-title":"SIAM J. Comput."},{"key":"805_CR10","doi-asserted-by":"publisher","unstructured":"Cai, J., Lu, P., Xia, M.: Dichotomy for Real Holant$$^c$$ Problems. In: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pp. 1802\u20131821 (2018). https:\/\/doi.org\/10.1137\/1.9781611975031.118","DOI":"10.1137\/1.9781611975031.118"},{"key":"805_CR11","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 - July 01, 2016, pp. 315\u2013326 (2016). https:\/\/doi.org\/10.1145\/2902251.2902279","DOI":"10.1145\/2902251.2902279"},{"issue":"2","key":"805_CR12","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":"805_CR13","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":"805_CR14","doi-asserted-by":"publisher","unstructured":"Curticapean, R.: Counting Matchings of Size k is W[1]-Hard. In: Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part I, pp. 352\u2013363 (2013). https:\/\/doi.org\/10.1007\/978-3-642-39206-1_30","DOI":"10.1007\/978-3-642-39206-1_30"},{"key":"805_CR15","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":"805_CR16","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, June 19-23, 2017, pp. 210\u2013223 (2017). https:\/\/doi.org\/10.1145\/3055399.3055502","DOI":"10.1145\/3055399.3055502"},{"key":"805_CR17","doi-asserted-by":"publisher","unstructured":"Curticapean, R., Marx, D.: Complexity of Counting Subgraphs: Only the Boundedness of the Vertex-Cover Number Counts. In: 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pp. 130\u2013139 (2014). https:\/\/doi.org\/10.1109\/FOCS.2014.22","DOI":"10.1109\/FOCS.2014.22"},{"key":"805_CR18","doi-asserted-by":"publisher","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer (2015). https:\/\/doi.org\/10.1007\/978-3-319-21275-3","DOI":"10.1007\/978-3-319-21275-3"},{"issue":"1\u20133","key":"805_CR19","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":"805_CR20","doi-asserted-by":"publisher","unstructured":"Dell, H., Roth, M., Wellnitz, P.: Counting Answers to Existential Questions. In: 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece., pp. 113:1\u2013113:15 (2019). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2019.113","DOI":"10.4230\/LIPIcs.ICALP.2019.113"},{"key":"805_CR21","unstructured":"Dell, H., Roth, M., Wellnitz, P.: Counting Answers to Existential Questions. CoRR abs\/1902.04960 (2019)"},{"issue":"1\u20132","key":"805_CR22","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1016\/S0304-3975(02)00017-8","volume":"281","author":"J D\u00edaz","year":"2002","unstructured":"D\u00edaz, J., Serna, M.J., Thilikos, D.M.: Counting H-colorings of partial k-trees. Theor. Comput. Sci. 281(1\u20132), 291\u2013309 (2002). https:\/\/doi.org\/10.1016\/S0304-3975(02)00017-8","journal-title":"Theor. Comput. Sci."},{"issue":"3\u20134","key":"805_CR23","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1016\/j.jcss.2009.08.003","volume":"76","author":"ME Dyer","year":"2010","unstructured":"Dyer, M.E., Goldberg, L.A., Jerrum, M.: An approximation trichotomy for Boolean #CSP. J. Comput. Syst. Sci. 76(3\u20134), 267\u2013277 (2010). https:\/\/doi.org\/10.1016\/j.jcss.2009.08.003","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"805_CR24","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1137\/S0097539794266766","volume":"28","author":"T Feder","year":"1998","unstructured":"Feder, T., Vardi, M.Y.: The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory. SIAM J. Comput. 28(1), 57\u2013104 (1998). https:\/\/doi.org\/10.1137\/S0097539794266766","journal-title":"SIAM J. Comput."},{"issue":"2","key":"805_CR25","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/j.cosrev.2008.06.001","volume":"2","author":"J Fiala","year":"2008","unstructured":"Fiala, J., Kratochv\u00edl, J.: Locally constrained graph homomorphisms - structure, complexity, and applications. Computer Science Review 2(2), 97\u2013111 (2008). https:\/\/doi.org\/10.1016\/j.cosrev.2008.06.001","journal-title":"Computer Science Review"},{"issue":"4","key":"805_CR26","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":"805_CR27","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"},{"key":"805_CR28","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1112\/S1461157000000243","volume":"3","author":"LA Goldberg","year":"2000","unstructured":"Goldberg, L.A., Jerrum, M.: Counting Unlabelled Subtrees of a Tree is #P-complete. LMS Journal of Computation and Mathematics 3, 117\u2013124 (2000). https:\/\/doi.org\/10.1112\/S1461157000000243","journal-title":"LMS Journal of Computation and Mathematics"},{"key":"805_CR29","doi-asserted-by":"crossref","unstructured":"Goldreich, O.: Computational Complexity - A Conceptual Perspective. Cambridge University Press, (2008)","DOI":"10.1017\/CBO9780511804106"},{"key":"805_CR30","doi-asserted-by":"publisher","unstructured":"Grohe, M., Marx, D.: On tree width, bramble size, and expansion. J. Comb. Theory, Ser. B 99(1), 218\u2013228 (2009). https:\/\/doi.org\/10.1016\/j.jctb.2008.06.004","DOI":"10.1016\/j.jctb.2008.06.004"},{"key":"805_CR31","doi-asserted-by":"publisher","unstructured":"Guo, H., Liao, C., Lu, P., Zhang, C.: Zeros of Holant problems: locations and algorithms. In: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pp. 2262\u20132278 (2019). https:\/\/doi.org\/10.1137\/1.9781611975482.137","DOI":"10.1137\/1.9781611975482.137"},{"issue":"1","key":"805_CR32","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1016\/0020-0190(71)90019-6","volume":"1","author":"JE Hopcroft","year":"1971","unstructured":"Hopcroft, J.E., Tarjan, R.E.: A V$${^2}$$ Algorithm for Determining Isomorphism of Planar Graphs. Inf. Process. Lett. 1(1), 32\u201334 (1971). https:\/\/doi.org\/10.1016\/0020-0190(71)90019-6","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"805_CR33","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1007\/s00037-015-0118-3","volume":"25","author":"S Huang","year":"2016","unstructured":"Huang, S., Lu, P.: A Dichotomy for Real Weighted Holant Problems. Computational Complexity 25(1), 255\u2013304 (2016). https:\/\/doi.org\/10.1007\/s00037-015-0118-3","journal-title":"Computational Complexity"},{"issue":"2","key":"805_CR34","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the Complexity of k-SAT. J. Comput. Syst. Sci. 62(2), 367\u2013375 (2001). https:\/\/doi.org\/10.1006\/jcss.2000.1727","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"805_CR35","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/0020-0190(94)00085-9","volume":"51","author":"M Jerrum","year":"1994","unstructured":"Jerrum, M.: Counting Trees in a Graph is #P-Complete. Inf. Process. Lett. 51(3), 111\u2013116 (1994). https:\/\/doi.org\/10.1016\/0020-0190(94)00085-9","journal-title":"Inf. Process. Lett."},{"issue":"6","key":"805_CR36","doi-asserted-by":"publisher","first-page":"1149","DOI":"10.1137\/0218077","volume":"18","author":"M Jerrum","year":"1989","unstructured":"Jerrum, M., Sinclair, A.: Approximating the Permanent. SIAM J. Comput. 18(6), 1149\u20131178 (1989). https:\/\/doi.org\/10.1137\/0218077","journal-title":"SIAM J. Comput."},{"issue":"12","key":"805_CR37","doi-asserted-by":"publisher","first-page":"1209","DOI":"10.1016\/0031-8914(61)90063-5","volume":"27","author":"PW Kasteleyn","year":"1961","unstructured":"Kasteleyn, P.W.: The statistics of dimers on a lattice: I. The number of dimer arrangements on a quadratic lattice. Physica 27(12), 1209\u20131225 (1961). https:\/\/doi.org\/10.1016\/0031-8914(61)90063-5","journal-title":"Physica"},{"issue":"2","key":"805_CR38","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1063\/1.1703953","volume":"4","author":"PW Kasteleyn","year":"1963","unstructured":"Kasteleyn, P.W.: Dimer Statistics and Phase Transitions. Journal of Mathematical Physics 4(2), 287\u2013293 (1963). https:\/\/doi.org\/10.1063\/1.1703953","journal-title":"Journal of Mathematical Physics"},{"issue":"1","key":"805_CR39","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1145\/321864.321877","volume":"22","author":"RE Ladner","year":"1975","unstructured":"Ladner, R.E.: On the structure of polynomial time reducibility. J. ACM 22(1), 155\u2013171 (1975). https:\/\/doi.org\/10.1145\/321864.321877","journal-title":"J. ACM"},{"issue":"5","key":"805_CR40","doi-asserted-by":"publisher","first-page":"34:1","DOI":"10.1145\/3212622","volume":"65","author":"B Lin","year":"2018","unstructured":"Lin, B.: The Parameterized Complexity of the k-Biclique Problem. J. ACM 65(5), 34:1\u201334:23 (2018). https:\/\/doi.org\/10.1145\/3212622","journal-title":"J. ACM"},{"key":"805_CR41","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","key":"805_CR42","doi-asserted-by":"publisher","first-page":"85","DOI":"10.4086\/toc.2010.v006a005","volume":"6","author":"D Marx","year":"2010","unstructured":"Marx, D.: Can You Beat Treewidth? Theory of Computing 6(1), 85\u2013112 (2010). https:\/\/doi.org\/10.4086\/toc.2010.v006a005","journal-title":"Theory of Computing"},{"issue":"3","key":"805_CR43","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/0020-0190(79)90004-8","volume":"8","author":"R Mathon","year":"1979","unstructured":"Mathon, R.: A Note on the Graph Isomorphism Counting Problem. Inf. Process. Lett. 8(3), 131\u2013132 (1979). https:\/\/doi.org\/10.1016\/0020-0190(79)90004-8","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"805_CR44","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1137\/0130017","volume":"30","author":"SB Maurer","year":"1976","unstructured":"Maurer, S.B.: Matrix Generalizations of Some Theorems on Trees, Cycles and Cocycles in Graphs. SIAM Journal on Applied Mathematics 30(1), 143\u2013148 (1976). https:\/\/doi.org\/10.1137\/0130017","journal-title":"SIAM Journal on Applied Mathematics"},{"issue":"1\u20133","key":"805_CR45","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"},{"issue":"3","key":"805_CR46","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1016\/0012-365X(71)90014-8","volume":"1","author":"J Ne\u0161et\u0159il","year":"1971","unstructured":"Ne\u0161et\u0159il, J.: Homomorphisms of derivative graphs. Discrete Mathematics 1(3), 257\u2013268 (1971). https:\/\/doi.org\/10.1016\/0012-365X(71)90014-8","journal-title":"Discrete Mathematics"},{"issue":"1","key":"805_CR47","doi-asserted-by":"publisher","first-page":"2:1","DOI":"10.1145\/2656335","volume":"40","author":"D Olteanu","year":"2015","unstructured":"Olteanu, D., Z\u00e1vodn\u00fd, J.: Size Bounds for Factorised Representations of Query Results. ACM Trans. Database Syst. 40(1), 2:1\u20132:44 (2015). https:\/\/doi.org\/10.1145\/2656335","journal-title":"ACM Trans. Database Syst."},{"key":"805_CR48","doi-asserted-by":"crossref","unstructured":"Oxley, J.G.: Matroid theory, 2nd edn. Oxford University Press, (2011)","DOI":"10.1093\/acprof:oso\/9780198566946.001.0001"},{"key":"805_CR49","doi-asserted-by":"crossref","unstructured":"Rota, G.C.: On the foundations of combinatorial theory I. Theory of M\u00f6bius functions. Zeitschrift f\u00fcr Wahrscheinlichkeitstheorie und verwandte Gebiete 2(4), 340\u2013368 (1964)","DOI":"10.1007\/BF00531932"},{"key":"805_CR50","doi-asserted-by":"publisher","unstructured":"Roth, M.: Counting Restricted Homomorphisms via M\u00f6bius Inversion over Matroid Lattices. In: 25th Annual European Symposium on Algorithms, ESA 2017, September 4-6, 2017, Vienna, Austria, pp. 63:1\u201363:14 (2017). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2017.63","DOI":"10.4230\/LIPIcs.ESA.2017.63"},{"key":"805_CR51","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, August 20-24, 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"},{"key":"805_CR52","doi-asserted-by":"publisher","unstructured":"Schaefer, T.J.: The Complexity of Satisfiability Problems. In: Proceedings of the 10th Annual ACM Symposium on Theory of Computing, May 1-3, 1978, San Diego, California, USA, pp. 216\u2013226 (1978). https:\/\/doi.org\/10.1145\/800133.804350","DOI":"10.1145\/800133.804350"},{"key":"805_CR53","doi-asserted-by":"crossref","unstructured":"Stanley, R.P.: Enumerative Combinatorics: vol. 1. Cambridge University Press, (2011)","DOI":"10.1017\/CBO9781139058520.002"},{"issue":"68","key":"805_CR54","doi-asserted-by":"publisher","first-page":"1061","DOI":"10.1080\/14786436108243366","volume":"6","author":"HNV Temperley","year":"1961","unstructured":"Temperley, H.N.V., Fisher, M.E.: Dimer problem in statistical mechanics-an exact result. The Philosophical Magazine: A Journal of Theoretical Experimental and Applied Physics 6(68), 1061\u20131063 (1961). https:\/\/doi.org\/10.1080\/14786436108243366","journal-title":"The Philosophical Magazine: A Journal of Theoretical Experimental and Applied Physics"},{"issue":"2","key":"805_CR55","doi-asserted-by":"publisher","first-page":"398","DOI":"10.1137\/S0097539797321602","volume":"31","author":"SP Vadhan","year":"2001","unstructured":"Vadhan, S.P.: The Complexity of Counting in Sparse, Regular, and Planar Graphs. SIAM J. Comput. 31(2), 398\u2013427 (2001). https:\/\/doi.org\/10.1137\/S0097539797321602","journal-title":"SIAM J. Comput."},{"key":"805_CR56","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."},{"issue":"3","key":"805_CR57","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1137\/0208032","volume":"8","author":"LG Valiant","year":"1979","unstructured":"Valiant, L.G.: The Complexity of Enumeration and Reliability Problems. SIAM J. Comput. 8(3), 410\u2013421 (1979). https:\/\/doi.org\/10.1137\/0208032","journal-title":"SIAM J. Comput."},{"issue":"5","key":"805_CR58","doi-asserted-by":"publisher","first-page":"1565","DOI":"10.1137\/070682575","volume":"37","author":"LG Valiant","year":"2008","unstructured":"Valiant, L.G.: Holographic Algorithms. SIAM J. Comput. 37(5), 1565\u20131594 (2008). https:\/\/doi.org\/10.1137\/070682575","journal-title":"SIAM J. Comput."},{"key":"805_CR59","unstructured":"Welsh, D.J.: Matroid theory. Courier Corporation (2010)"},{"issue":"1","key":"805_CR60","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/j.tcs.2007.05.023","volume":"384","author":"M Xia","year":"2007","unstructured":"Xia, M., Zhang, P., Zhao, W.: Computational complexity of counting problems on 3-regular planar graphs. Theor. Comput. Sci. 384(1), 111\u2013125 (2007). https:\/\/doi.org\/10.1016\/j.tcs.2007.05.023","journal-title":"Theor. Comput. Sci."},{"key":"805_CR61","doi-asserted-by":"publisher","unstructured":"Zhuk, D.: A Proof of CSP Dichotomy Conjecture. In: 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pp. 331\u2013342 (2017). https:\/\/doi.org\/10.1109\/FOCS.2017.38","DOI":"10.1109\/FOCS.2017.38"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00805-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00805-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00805-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,25]],"date-time":"2021-05-25T10:05:11Z","timestamp":1621937111000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00805-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3,11]]},"references-count":61,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2021,6]]}},"alternative-id":["805"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00805-y","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,3,11]]},"assertion":[{"value":"17 July 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 January 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 March 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}