Are unique subgraphs not easier to find?

*(English)*Zbl 06855757Summary: Consider a pattern graph \(H\) with \(l\) edges, and a host graph \(G\) which may contain several occurrences of \(H\). In [15], we claimed that the time complexity of the problems of finding an occurrence of \(H\) (if any) in \(G\) as well as that of the decision version of the problem are within a multiplicative factor \(\widetilde{O}(l^3)\) of the time complexity for the corresponding problem, where the host graph is guaranteed to contain at most one occurrence of a subgraph isomorphic to \(H\), and the notation \(\widetilde{O}()\) suppresses polylogarithmic in \(n\) factors. We show a counterexample to this too strong claim and correct it by providing an \(\widetilde{O}((l(d-1)+2)^l)\) bound on the multiplicative factor instead, where \(d\) is the maximum number of occurrences of \(H\) that can share the same edge in the input host graph. We provide also an analogous correction in the induced case when occurrences of induced subgraphs isomorphic to \(H\) are sought.

##### MSC:

68Q | Theory of computing |

##### Keywords:

algorithms; subgraph isomorphism; induced subgraph isomorphism; unique subgraph occurrence; time complexity
PDF
BibTeX
XML
Cite

\textit{M. Kowaluk} and \textit{A. Lingas}, Inf. Process. Lett. 134, 57--61 (2018; Zbl 06855757)

Full Text:
DOI

##### References:

[1] | Alon, N.; Dao, P.; Hajirasouliha, I.; Hormozdiari, F.; Sahinalp, S. C., Biomolecular network motif counting and discovery by color coding, (Proceedings 16th International Conference on Intelligent Systems for Molecular Biology (ISMB), Toronto, Canada, July 19-23, 2008, (2008)), 241-249 |

[2] | Alon, N.; Naor, M., Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions, Algorithmica, 16, 4, 434-449, (1996) · Zbl 0857.68055 |

[3] | Alon, N.; Yuster, R.; Zwick, U., Color-coding, J. ACM, 42, 4, 844-856, (1995) · Zbl 0885.68116 |

[4] | Alon, N.; Yuster, R.; Zwick, U., Finding and counting given length cycles, Algorithmica, 17, 3, 209-223, (1997) · Zbl 0865.68093 |

[5] | Bachman, P.; Liu, Y., Structure discovery in PPI networks using pattern-based network decomposition, Bioinformatics, 25, 14, 1814-1821, (2009) |

[6] | Chiba, N.; Nishizeki, T., Arboricity and subgraph listing algorithms, SIAM J. Comput., 14, 1, 210-223, (1985) · Zbl 0572.68053 |

[7] | Eisenbrand, F.; Grandoni, F., On the complexity of fixed parameter clique and dominating set, Theor. Comput. Sci., 326, 1-3, 57-67, (2004) · Zbl 1071.68030 |

[8] | Eppstein, David, Subgraph isomorphism in planar graphs and related problems, J. Graph Algorithms Appl., 3, 3, 1-27, (1999) · Zbl 0949.05055 |

[9] | Gabow, H. N.; Kaplan, H.; Tarjan, R. E., Unique maximum matching algorithms, J. Algorithms, 40, 2, 159-183, (2001) · Zbl 0982.05094 |

[10] | Garey, M. R.; Johnson, D. S., Computers and intractability. A guide to the theory of NP-completeness, A Series of Books in the Mathematical Sciences, (2003), WH Freeman and Company New York |

[11] | Huang, X.; Pan, V. Y., Fast rectangular matrix multiplications and applications, J. Complex., 14, 257-299, (1998) · Zbl 0919.65030 |

[12] | Itai, A.; Rodeh, M., Finding a minimum circuit in a graph, SIAM J. Comput., 7, 413-423, (1978) · Zbl 0386.68064 |

[13] | Kloks, T.; Kratsch, D.; Muller, H., Finding and counting small induced subgraphs efficiently, Inf. Process. Lett., 74, 3, 115-121, (2000) · Zbl 1339.05394 |

[14] | Kowaluk, M.; Lingas, A., Unique lowest common ancestors in dags are almost as easy as matrix multiplication, (Proceedings of the 15th Annual Symposium on Algorithms (ESA), (2007)), 265-274 · Zbl 1151.68429 |

[15] | Kowaluk, M.; Lingas, A.; Lundell, E., Unique subgraphs are not easier to find, Int. J. Comput. Math., 90, 6, 1247-1257, (2013) · Zbl 1310.68113 |

[16] | Kowaluk, M.; Lingas, A.; 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), (2011)), 1468-1476 · Zbl 1376.05151 |

[17] | Nešetřil, J.; Poljak, S., On the complexity of the subgraph problem, Comment. Math. Univ. Carol., 26, 2, 415-419, (1985) · Zbl 0571.05050 |

[18] | Plehn, J.; Voigt, B., Finding minimally weighted subgraphs, (Graph-Theoretic Concepts in Computer Science (WG), (1991)), 18-29 · Zbl 0768.68170 |

[19] | Schank, T.; Finding, Wagner D., Counting and listing all triangles in large graphs, an experimental study, (Proceedings of WEA 2005, (1992)), 606-609 · Zbl 1121.68360 |

[20] | Seidel, R., On the all-pairs-shortest-path problem, (Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing (STOC), (1992)), 745-749 |

[21] | Valiant, L. G.; Vazirani, V. V., NP is as easy as detecting unique solutions, Theor. Comput. Sci., 47, 85-93, (1986) · Zbl 0621.68030 |

[22] | Vassilevska, V.; Williams, R., Finding, minimizing, and counting weighted subgraphs, (Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC), (2009)), 455-464 · Zbl 1304.05102 |

[23] | Vassilevska Williams, V.; Wang, J. R.; Williams, R.; Yu, H., Finding four-node subgraphs in triangle time, (Proceedings of SODA 2015, (2015)), 1671-1680 · Zbl 1371.05292 |

[24] | Wolinski, C.; Kuchcinski, K.; Raffin, E., Automatic design of application-specific reconfigurable processor extensions with upak synthesis kernel, ACM Trans. Des. Autom. Electron. Syst. (TODAES), 15, 1, 1-36, (2009) |

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.