×

zbMATH — the first resource for mathematics

Unique subgraphs are not easier to find. (English) Zbl 1310.68113
Summary: Given a pattern graph \(H\) with \(l\) edges, and a host graph \(G\) guaranteed to contain at most one occurrence of a subgraph isomorphic to \(H\), we show that the time complexity of the problem of finding such an occurrence (if any) in \(G\) as well as that of the decision version of the problem are within a multiplicative factor \(O(l)\) of the time complexity for the corresponding problem in the general case, when \(G\) may contain several occurrences of \(H\). It follows that for pattern graphs of constant size, the aforementioned uniqueness guarantee cannot yield any asymptotic speed up. We also derive analogous results with the analogous multiplicative factor linear in the number of vertices of \(H\) in the induced case when occurrences of induced subgraphs of \(G\) isomorphic to \(H\) are sought.

MSC:
68Q25 Analysis of algorithms and problem complexity
05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
05C85 Graph algorithms (graph-theoretic aspects)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] DOI: 10.1007/BF01940874 · Zbl 0857.68055 · doi:10.1007/BF01940874
[2] DOI: 10.1145/210332.210337 · Zbl 0885.68116 · doi:10.1145/210332.210337
[3] DOI: 10.1007/BF02523189 · Zbl 0865.68093 · doi:10.1007/BF02523189
[4] Alon, N., Dao, P., Hajirasouliha, I., Hormozdiari, F. and Sahinalp, S. C. 2008. Biomolecular network motif counting and discovery by color coding. Proceedings 16th International Conference on Intelligent Systems for Molecular Biology (ISMB). July19–232008, Toronto, Canada. pp.241–249.
[5] DOI: 10.1093/bioinformatics/btp297 · Zbl 05744098 · doi:10.1093/bioinformatics/btp297
[6] DOI: 10.1137/0214017 · Zbl 0572.68053 · doi:10.1137/0214017
[7] DOI: 10.1016/j.tcs.2004.05.009 · Zbl 1071.68030 · doi:10.1016/j.tcs.2004.05.009
[8] DOI: 10.7155/jgaa.00014 · Zbl 0949.05055 · doi:10.7155/jgaa.00014
[9] DOI: 10.1006/jagm.2001.1167 · Zbl 0982.05094 · doi:10.1006/jagm.2001.1167
[10] Garey M. R., Computers and Intractability. A Guide to the Theory of NP-Completeness. A Series of Books in the Mathematical Sciences (2003)
[11] DOI: 10.1006/jcom.1998.0476 · Zbl 0919.65030 · doi:10.1006/jcom.1998.0476
[12] DOI: 10.1137/0207033 · Zbl 0386.68064 · doi:10.1137/0207033
[13] DOI: 10.1016/S0020-0190(00)00047-8 · Zbl 1339.05394 · doi:10.1016/S0020-0190(00)00047-8
[14] Kowaluk, M. and Lingas, A. Unique lowest common ancestors in dags are almost as easy as matrix multiplication. Proceedings of the 15th Annual Symposium on Algorithms, ESA. October8–102007, Eilat, Israel. pp.265–274. Berlin: Springer. · Zbl 1151.68429
[15] Kowaluk, M., Lingas, A. and Lundell, E. M. Counting and detecting small subgraphs via equations and matrix multiplication. Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA. January23–252011, San Francisco, CA, USA. pp.1468–1476. Philadelphia: SIAM. · Zbl 1275.68161
[16] DOI: 10.1007/BF02579206 · Zbl 0632.68041 · doi:10.1007/BF02579206
[17] Nešetřil J., Comment. Math. Univ. Carolin. 26 (2) pp 415– (1985)
[18] Plehn, J. and Voigt, B. Finding minimally weighted subgraphs. Proceedings of the 16th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 1990. June20–221990, Berlin, Germany. pp.18–29. London: Springer.
[19] Seidel, R. On the all-pairs-shortest-path problem. Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing, STOC 1992. May4–61992, Victoria, British Columbia, Canada. pp.745–749. New York: ACM.
[20] DOI: 10.1016/0304-3975(86)90135-0 · Zbl 0621.68030 · doi:10.1016/0304-3975(86)90135-0
[21] Vassilevska, V. and Williams, R. Finding, minimizing, and counting weighted subgraphs. Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009. May31–June 22009, New York, Bethesda, MD, USA. pp.455–464. ACM. · Zbl 1304.05102
[22] DOI: 10.1145/1640457.1640458 · Zbl 05741251 · doi:10.1145/1640457.1640458
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.