Counting small induced subgraphs with hereditary properties. (English) Zbl 07774436
Leonardi, Stefano (ed.) et al., Proceedings of the 54th annual ACM SIGACT symposium on theory of computing, STOC ’22, Rome, Italy June 20–24, 2022. New York, NY: Association for Computing Machinery (ACM). 1543-1551 (2022).
MSC:
| 68Qxx | Theory of computing |
Keywords:
counting complexity; fine-grained complexity; graph homomorphisms; hereditary properties; induced subgraphs; parameterized complexityReferences:
| [1] | Noga Alon, Phuong Dao, Iman Hajirasouliha, Fereydoun Hormozdiari, and S. Cenk Sahinalp. 2008. Biomolecular network motif counting and discovery by color coding. Bioinformatics, 24, 13 (2008), 07, i241-i249. issn:1367-4803 https://doi.org/10.1093/bioinformatics/btn163 |
| [2] | Vikraman Arvind and Venkatesh Raman. 2002. Approximation Algorithms for Some Parameterized Counting Problems. In Algorithms and Computation, 13th International Symposium, ISAAC 2002 Vancouver, BC, Canada, November 21-23, 2002, Proceedings. 453-464. https://doi.org/10.1007/3-540-36136-7_40 10.1007/3-540-36136-7_40 · Zbl 1019.68135 |
| [3] | Hubie Chen and Stefan Mengel. 2016. 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. 315-326. https://doi.org/10.1145/2902251.2902279 10.1145/2902251.2902279 |
| [4] | Jianer Chen, Benny Chor, Mike Fellows, Xiuzhen Huang, David W. Juedes, Iyad A. Kanj, and Ge Xia. 2005. Tight lower bounds for certain parameterized NP-hard problems. Inf. Comput., 201, 2 (2005), 216-231. https://doi.org/10.1016/j.ic.2005.05.001 10.1016/j.ic.2005.05.001 · Zbl 1161.68476 |
| [5] | Jianer Chen, Xiuzhen Huang, Iyad A. Kanj, and Ge Xia. 2006. Strong computational lower bounds via parameterized complexity. J. Comput. Syst. Sci., 72, 8 (2006), 1346-1367. https://doi.org/10.1016/j.jcss.2006.04.007 10.1016/j.jcss.2006.04.007 · Zbl 1119.68092 |
| [6] | Yijia Chen, Marc Thurley, and Mark Weyer. 2008. Understanding the Complexity of Induced Subgraph Isomorphisms. In Automata, Languages and Programming, 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part I: Tack A: Algorithms, Automata, Complexity, and Games. 587-596. https://doi.org/10.1007/978-3-540-70575-8_48 10.1007/978-3-540-70575-8_48 · Zbl 1153.68387 |
| [7] | Radu Curticapean, Holger Dell, and Dániel Marx. 2017. 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. 210-223. https://doi.org/10.1145/3055399.3055502 10.1145/3055399.3055502 · Zbl 1369.05191 |
| [8] | Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. 2015. Parameterized Algorithms. Springer. isbn:978-3-319-21274-6 https://doi.org/10.1007/978-3-319-21275-3 10.1007/978-3-319-21275-3 · Zbl 1334.90001 |
| [9] | Víctor Dalmau and Peter Jonsson. 2004. The complexity of counting homomorphisms seen from the other side. Theor. Comput. Sci., 329, 1-3 (2004), 315-323. https://doi.org/10.1016/j.tcs.2004.08.008 10.1016/j.tcs.2004.08.008 · Zbl 1086.68054 |
| [10] | Holger Dell, John Lapinskas, and Kitty Meeks. 2020. Approximately counting and sampling small witnesses using a colourful decision oracle. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, Shuchi Chawla (Ed.). SIAM, 2201-2211. https://doi.org/10.1137/1.9781611975994.135 10.1137/1.9781611975994.135 · Zbl 07304159 |
| [11] | Julian Dörfler, Marc Roth, Johannes Schmitt, and Philip Wellnitz. 2022. Counting Induced Subgraphs: An Algebraic Approach to #W[1]-Hardness. Algorithmica, 84, 2 (2022), 379-404. https://doi.org/10.1007/s00453-021-00894-9 10.1007/s00453-021-00894-9 · Zbl 1518.68259 |
| [12] | David Eppstein, Siddharth Gupta, and Elham Havvaei. 2021. Parameterized Complexity of Finding Subgraphs with Hereditary Properties on Hereditary Graph Classes. In Fundamentals of Computation Theory - 23rd International Symposium, FCT 2021, Athens, Greece, September 12-15, 2021, Proceedings, Evripidis Bampis and Aris Pagourtzis (Eds.) (Lecture Notes in Computer Science, Vol. 12867). Springer, 217-229. https://doi.org/10.1007/978-3-030-86593-1_15 10.1007/978-3-030-86593-1_15 · Zbl 07530235 |
| [13] | Jörg Flum and Martin Grohe. 2003. Describing parameterized complexity classes. Inf. Comput., 187, 2 (2003), 291-319. https://doi.org/10.1016/S0890-5401(03)00161-5 10.1016/S0890-5401(03)00161-5 · Zbl 1076.68031 |
| [14] | Jörg Flum and Martin Grohe. 2006. Parameterized Complexity Theory. Springer. isbn:978-3-540-29952-3 https://doi.org/10.1007/3-540-29953-X 10.1007/3-540-29953-X · Zbl 1143.68016 |
| [15] | Jacob Focke and Marc Roth. 2021. Counting Small Induced Subgraphs with Hereditary Properties. CoRR, abs/2111.02277 (2021), arXiv:2111.02277. |
| [16] | Joshua A. Grochow and Manolis Kellis. 2007. Network Motif Discovery Using Subgraph Enumeration and Symmetry-Breaking. In Research in Computational Molecular Biology, Terry Speed and Haiyan Huang (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg. 92-106. isbn:978-3-540-71681-5 |
| [17] | Martin Grohe, Thomas Schwentick, and Luc Segoufin. 2001. When is the evaluation of conjunctive queries tractable? In Proceedings on 33rd Annual ACM Symposium on Theory of Computing, July 6-8, 2001, Heraklion, Crete, Greece. 657-666. https://doi.org/10.1145/380752.380867 10.1145/380752.380867 · Zbl 1323.68251 |
| [18] | Russell Impagliazzo and Ramamohan Paturi. 2001. On the Complexity of k-SAT. J. Comput. Syst. Sci., 62, 2 (2001), 367-375. https://doi.org/10.1006/jcss.2000.1727 10.1006/jcss.2000.1727 · Zbl 0990.68079 |
| [19] | Mark Jerrum and Kitty Meeks. 2015. The parameterised complexity of counting connected subgraphs and graph motifs. J. Comput. Syst. Sci., 81, 4 (2015), 702-716. https://doi.org/10.1016/j.jcss.2014.11.015 10.1016/j.jcss.2014.11.015 · Zbl 1320.68101 |
| [20] | Mark Jerrum and Kitty Meeks. 2015. Some Hard Families of Parameterized Counting Problems. TOCT, 7, 3 (2015), 11:1-11:18. https://doi.org/10.1145/2786017 10.1145/2786017 · Zbl 1348.68066 |
| [21] | Mark Jerrum and Kitty Meeks. 2017. The parameterised complexity of counting even and odd induced subgraphs. Combinatorica, 37, 5 (2017), 965-990. https://doi.org/10.1007/s00493-016-3338-5 10.1007/s00493-016-3338-5 · Zbl 1413.68063 |
| [22] | Pieter W. Kasteleyn. 1961. The statistics of dimers on a lattice: I. The number of dimer arrangements on a quadratic lattice. Physica, 27, 12 (1961), 1209-1225. https://doi.org/10.1016/0031-8914(61)90063-5 10.1016/0031-8914(61)90063-5 · Zbl 1244.82014 |
| [23] | Pieter W. Kasteleyn. 1963. Dimer Statistics and Phase Transitions. J. Math. Phys., 4, 2 (1963), 287-293. https://doi.org/10.1063/1.1703953 10.1063/1.1703953 |
| [24] | Subhash Khot and Venkatesh Raman. 2002. Parameterized complexity of finding subgraphs with hereditary properties. Theor. Comput. Sci., 289, 2 (2002), 997-1008. https://doi.org/10.1016/S0304-3975(01)00414-5 10.1016/S0304-3975(01)00414-5 · Zbl 1061.68061 |
| [25] | Kitty Meeks. 2016. The challenges of unbounded treewidth in parameterised subgraph counting problems. Discrete Applied Mathematics, 198 (2016), 170-194. https://doi.org/10.1016/j.dam.2015.06.019 10.1016/j.dam.2015.06.019 · Zbl 1327.05244 |
| [26] | Ron Milo, Shalev Itzkovitz, Nadav Kashtan, Reuven Levitt, Shai Shen-Orr, Inbal Ayzenshtat, Michal Sheffer, and Uri Alon. 2004. Superfamilies of Evolved and Designed Networks. Science, 303, 5663 (2004), 1538-1542. issn:0036-8075 https://doi.org/10.1126/science.1089167 10.1126/science.1089167 |
| [27] | R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii, and U. Alon. 2002. Network Motifs: Simple Building Blocks of Complex Networks. Science, 298, 5594 (2002), 824-827. issn:0036-8075 https://doi.org/10.1126/science.298.5594.824 10.1126/science.298.5594.824 |
| [28] | Jaroslav Nešetřil and Svatopluk Poljak. 1985. On the complexity of the subgraph problem. Commentationes Mathematicae Universitatis Carolinae, 26, 2 (1985), 415-419. · Zbl 0571.05050 |
| [29] | Marc Roth and Johannes Schmitt. 2020. Counting Induced Subgraphs: A Topological Approach to #W[1]-hardness. Algorithmica, 82, 8 (2020), 2267-2291. https://doi.org/10.1007/s00453-020-00676-9 10.1007/s00453-020-00676-9 · Zbl 1452.68086 |
| [30] | Marc Roth, Johannes Schmitt, and Philip Wellnitz. 2020. Counting Small Induced Subgraphs Satisfying Monotone Properties. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020. IEEE, 1356-1367. https://doi.org/10.1109/FOCS46700.2020.00128 10.1109/FOCS46700.2020.00128 · Zbl 07510283 |
| [31] | Benjamin Schiller, Sven Jager, Kay Hamacher, and Thorsten Strufe. 2015. StreaM - A Stream-Based Algorithm for Counting Motifs in Dynamic Graphs. In Algorithms for Computational Biology, Adrian-Horia Dediu, Francisco Hernández-Quiroz, Carlos Martín-Vide, and David A. Rosenblueth (Eds.). Springer International Publishing, Cham. 53-67. isbn:978-3-319-21233-3 |
| [32] | Falk Schreiber and Henning Schwöbbermeyer. 2005. Frequency Concepts and Pattern Detection for the Analysis of Motifs in Networks. In Transactions on Computational Systems Biology III, Corrado Priami, Emanuela Merelli, Pablo Gonzalez, and Andrea Omicini (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg. 89-104. isbn:978-3-540-31446-2 · Zbl 1151.92301 |
| [33] | Harold N. V. Temperley and Michael E. Fisher. 1961. Dimer problem in statistical mechanics-an exact result. The Philosophical Magazine: A Journal of Theoretical Experimental and Applied Physics, 6, 68 (1961), 1061-1063. https://doi.org/10.1080/14786436108243366 10.1080/14786436108243366 · Zbl 0126.25102 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
