Unique subgraphs are not easier to find

References

• Alon , N. and Naor , M. 1996 . Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions . Algorithmica , 16 ( 4 ) : 434 – 449 . (doi:10.1007/BF01940874)
   Web of Science ®Google Scholar
• Alon , N. , Yuster , R. and Zwick , U. 1995 . Color-coding . J. ACM , 42 ( 4 ) : 844 – 856 . (doi:10.1145/210332.210337)
   Web of Science ®Google Scholar
• Alon , N. , Yuster , R. and Zwick , U. 1997 . Finding and counting given length cycles . Algorithmica , 17 ( 3 ) : 209 – 223 . (doi:10.1007/BF02523189)
   Web of Science ®Google Scholar
• 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) . July 19–23 2008 , Toronto , Canada. pp. 241 – 249 .
   Google Scholar
• Bachman , P. and Liu , Y. 2009 . Structure discovery in PPI networks using pattern-based network decomposition . Bioinformatics , 25 ( 14 ) : 1814 – 1821 . (doi:10.1093/bioinformatics/btp297)
   PubMed Web of Science ®Google Scholar
• Chiba , N. and Nishizeki , T. 1985 . Arboricity and subgraph listing algorithms . SIAM J. Comput. , 14 ( 1 ) : 210 – 223 . (doi:10.1137/0214017)
   Web of Science ®Google Scholar
• Eisenbrand , F. and Grandoni , F. 2004 . On the complexity of fixed parameter clique and dominating set . Theoret. Comput. Sci. , 326 ( 1–3 ) : 57 – 67 . (doi:10.1016/j.tcs.2004.05.009)
   Web of Science ®Google Scholar
• Eppstein , D. 1999 . Subgraph isomorphism in planar graphs and related problems . J. Graph Algorithms Appl. , 3 ( 3 ) : 1 – 27 . (doi:10.7155/jgaa.00014)
   Google Scholar
• Gabow , H. N. , Kaplan , H. and Tarjan , R. E. 2001 . Unique maximum matching algorithms . J. Algorithms , 40 ( 2 ) : 159 – 183 . (doi:10.1006/jagm.2001.1167)
   Web of Science ®Google Scholar
• Garey , M. R. and Johnson , D. S. 2003 . Computers and Intractability. A Guide to the Theory of NP-Completeness. A Series of Books in the Mathematical Sciences , New York : WH Freeman and Company .
   Google Scholar
• Huang , X. and Pan , V. Y. 1998 . Fast rectangular matrix multiplications and applications . J. Complexity , 14 : 257 – 299 . (doi:10.1006/jcom.1998.0476)
   Web of Science ®Google Scholar
• Itai , A. and Rodeh , M. 1978 . Finding a minimum circuit in a graph . SIAM J. Comput. , 7 : 413 – 423 . (doi:10.1137/0207033)
   Web of Science ®Google Scholar
• Kloks , T. , Kratsch , D. and Muller , H. 2000 . Finding and counting small induced subgraphs efficiently . Inform. Process. Lett. , 74 ( 3 ) : 115 – 121 . (doi:10.1016/S0020-0190(00)00047-8)
   Web of Science ®Google Scholar
• 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 . October 8–10 2007 , Eilat , Israel. pp. 265 – 274 . Berlin : Springer .
   Google Scholar
• 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 . January 23–25 2011 , San Francisco , CA , USA. pp. 1468 – 1476 . Philadelphia : SIAM .
   Google Scholar
• Mulmuley , M. , Vazirani , U. V. and Vazirani , V. V. 1987 . Matching is as easy as matrix inversion . Combinatorica , 7 ( 1 ) : 105 – 113 . (doi:10.1007/BF02579206)
   Web of Science ®Google Scholar
• Nešetřil , J. and Poljak , S. 1985 . On the complexity of the subgraph problem . Comment. Math. Univ. Carolin. , 26 ( 2 ) : 415 – 419 .
   Google Scholar
• Plehn , J. and Voigt , B. Finding minimally weighted subgraphs . Proceedings of the 16th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 1990 . June 20–22 1990 , Berlin , Germany. pp. 18 – 29 . London : Springer .
   Google Scholar
• Seidel , R. On the all-pairs-shortest-path problem . Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing, STOC 1992 . May 4–6 1992 , Victoria , British Columbia , Canada. pp. 745 – 749 . New York : ACM .
   Google Scholar
• Valiant , L. G. and Vazirani , V. V. 1986 . NP is as easy as detecting unique solutions . Theoret. Comput. Sci. , 47 : 85 – 93 . (doi:10.1016/0304-3975(86)90135-0)
   Web of Science ®Google Scholar
• Vassilevska , V. and Williams , R. Finding, minimizing, and counting weighted subgraphs . Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009 . May 31–June 2 2009 , New York, Bethesda , MD , USA. pp. 455 – 464 . ACM .
   Google Scholar
• Wolinski , C. , Kuchcinski , K. and Raffin , E. 2009 . Automatic design of application-specific reconfigurable processor extensions with UPaK synthesis kernel . ACM Trans. Des. Autom. Electron. Syst. , 15 ( 1 ) : 1 – 36 . (doi:10.1145/1640457.1640458)
   Web of Science ®Google Scholar