2019/04/07 by Mina Dalirrooyfard, Dalirrooyfard, Mina, Thuy Duong Vuong +3 · 5 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Limits and Structures in Graph Theory #Machine Learning and Algorithms
paper · pdf · doi:10.48550/arxiv.1904.03741
openalex publication_date 2019/04/07 · openalex created_date 2022/07/29 · openalex updated_date 2026/07/28
We consider the pattern detection problem in graphs: given a constant size\npattern graph H and a host graph G, determine whether G contains a\nsubgraph isomorphic to H. Our main results are:\n * We prove that if a pattern H contains a k-clique subgraph, then\ndetecting whether an n node host graph contains a not necessarily induced\ncopy of H requires at least the time for detecting whether an n node graph\ncontains a k-clique. The previous result of this nature required that H\ncontains a k-clique which is disjoint from all other k-cliques of H.\n * We show that if the famous Hadwiger conjecture from graph theory is true,\nthen detecting whether an n node host graph contains a not necessarily\ninduced copy of a pattern with chromatic number t requires at least the time\nfor detecting whether an n node graph contains a t-clique. This implies\nthat: (1) under Hadwiger's conjecture for every k-node pattern H, finding\nan induced copy of H requires at least the time of \√ k-clique\ndetection, and at least size \ω(n\√(k)/4) for any constant depth\ncircuit, and (2) unconditionally, detecting an induced copy of a random\nG(k,p) pattern w.h.p. requires at least the time of \Θ(k/\log k)-clique\ndetection, and hence also at least size n\Ω(k/\log k) for circuits of\nconstant depth.\n * Finally, we consider the case when the pattern is a directed cycle on k\nnodes, and we would like to detect whether a directed m-edge graph G\ncontains a k-Cycle as a not necessarily induced subgraph. We resolve a 14\nyear old conjecture of [Yuster-Zwick SODA'04] on the complexity of k-Cycle\ndetection by giving a tight analysis of their k-Cycle algorithm. Our analysis\nimproves the best bounds for k-Cycle detection in directed graphs, for all\nk>5.\n