Graph pattern detection: Hardness for all induced patterns and faster non-induced cycles
© 2019 Association for Computing Machinery. We consider the pattern detection problem in graphs: given a constant size pattern graph H and a host graph G, determine whether G contains a subgraph isomorphic to H. We present the following new improved upper and lower bounds: We prove that if a pattern...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Association for Computing Machinery (ACM)
2021
|
| Online Access: | https://hdl.handle.net/1721.1/137813 |
| _version_ | 1826196166179553280 |
|---|---|
| author | Dalirrooyfard, Mina Vuong, Thuy Duong Williams, Virginia Vassilevska |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Dalirrooyfard, Mina Vuong, Thuy Duong Williams, Virginia Vassilevska |
| author_sort | Dalirrooyfard, Mina |
| collection | MIT |
| description | © 2019 Association for Computing Machinery. We consider the pattern detection problem in graphs: given a constant size pattern graph H and a host graph G, determine whether G contains a subgraph isomorphic to H. We present the following new improved upper and lower bounds: We prove that if a pattern H contains a k-clique subgraph, then detecting whether an n node host graph contains a not necessarily induced copy of H requires at least the time for detecting whether an n node graph contains a k-clique. The previous result of this nature required that H contains a k-clique which is disjoint from all other k-cliques of H. We show that if the famous Hadwiger conjecture from graph theory is true, then detecting whether an n node host graph contains a not necessarily induced copy of a pattern with chromatic number t requires at least the time for detecting whether an n node graph contains a t-clique. This implies that: (a) under Hadwiger’s conjecture for every k-node pattern H, finding an induced copy of H requires at least the time of k-clique detection and size ω(n k/4) for any constant depth circuit, and (b) unconditionally, detecting an induced copy of a random G(k, p) pattern w.h.p. requires at least the time of Θ(k/log k)-clique detection, and hence also at least size nΩ(k/log k) for circuits of constant depth. We show that for every k, there exists a k-node pattern that contains a k − 1-clique and that can be detected as an induced subgraph in n node graphs in the best known running time for k − 1-Clique detection. Previously such a result was only known for infinitely many k. Finally, we consider the case when the pattern is a directed cycle on k nodes, and we would like to detect whether a directed m-edge graph G contains a k-Cycle as a not necessarily induced subgraph. We resolve a 14 year old conjecture of [Yuster-Zwick SODA’04] on the complexity of k-Cycle detection by giving a tight analysis of their k-Cycle algorithm. Our analysis improves the best bounds for k-Cycle detection in directed graphs, for all k > 5. |
| first_indexed | 2024-09-23T10:22:34Z |
| format | Article |
| id | mit-1721.1/137813 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T10:22:34Z |
| publishDate | 2021 |
| publisher | Association for Computing Machinery (ACM) |
| record_format | dspace |
| spelling | mit-1721.1/1378132022-09-26T17:28:49Z Graph pattern detection: Hardness for all induced patterns and faster non-induced cycles Dalirrooyfard, Mina Vuong, Thuy Duong Williams, Virginia Vassilevska Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory © 2019 Association for Computing Machinery. We consider the pattern detection problem in graphs: given a constant size pattern graph H and a host graph G, determine whether G contains a subgraph isomorphic to H. We present the following new improved upper and lower bounds: We prove that if a pattern H contains a k-clique subgraph, then detecting whether an n node host graph contains a not necessarily induced copy of H requires at least the time for detecting whether an n node graph contains a k-clique. The previous result of this nature required that H contains a k-clique which is disjoint from all other k-cliques of H. We show that if the famous Hadwiger conjecture from graph theory is true, then detecting whether an n node host graph contains a not necessarily induced copy of a pattern with chromatic number t requires at least the time for detecting whether an n node graph contains a t-clique. This implies that: (a) under Hadwiger’s conjecture for every k-node pattern H, finding an induced copy of H requires at least the time of k-clique detection and size ω(n k/4) for any constant depth circuit, and (b) unconditionally, detecting an induced copy of a random G(k, p) pattern w.h.p. requires at least the time of Θ(k/log k)-clique detection, and hence also at least size nΩ(k/log k) for circuits of constant depth. We show that for every k, there exists a k-node pattern that contains a k − 1-clique and that can be detected as an induced subgraph in n node graphs in the best known running time for k − 1-Clique detection. Previously such a result was only known for infinitely many k. Finally, we consider the case when the pattern is a directed cycle on k nodes, and we would like to detect whether a directed m-edge graph G contains a k-Cycle as a not necessarily induced subgraph. We resolve a 14 year old conjecture of [Yuster-Zwick SODA’04] on the complexity of k-Cycle detection by giving a tight analysis of their k-Cycle algorithm. Our analysis improves the best bounds for k-Cycle detection in directed graphs, for all k > 5. 2021-11-08T20:15:31Z 2021-11-08T20:15:31Z 2019-06 2021-01-25T17:22:30Z Article http://purl.org/eprint/type/ConferencePaper https://hdl.handle.net/1721.1/137813 Dalirrooyfard, Mina, Vuong, Thuy Duong and Williams, Virginia Vassilevska. 2019. "Graph pattern detection: Hardness for all induced patterns and faster non-induced cycles." Proceedings of the Annual ACM Symposium on Theory of Computing. en 10.1145/3313276.3316329 Proceedings of the Annual ACM Symposium on Theory of Computing Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Association for Computing Machinery (ACM) arXiv |
| spellingShingle | Dalirrooyfard, Mina Vuong, Thuy Duong Williams, Virginia Vassilevska Graph pattern detection: Hardness for all induced patterns and faster non-induced cycles |
| title | Graph pattern detection: Hardness for all induced patterns and faster non-induced cycles |
| title_full | Graph pattern detection: Hardness for all induced patterns and faster non-induced cycles |
| title_fullStr | Graph pattern detection: Hardness for all induced patterns and faster non-induced cycles |
| title_full_unstemmed | Graph pattern detection: Hardness for all induced patterns and faster non-induced cycles |
| title_short | Graph pattern detection: Hardness for all induced patterns and faster non-induced cycles |
| title_sort | graph pattern detection hardness for all induced patterns and faster non induced cycles |
| url | https://hdl.handle.net/1721.1/137813 |
| work_keys_str_mv | AT dalirrooyfardmina graphpatterndetectionhardnessforallinducedpatternsandfasternoninducedcycles AT vuongthuyduong graphpatterndetectionhardnessforallinducedpatternsandfasternoninducedcycles AT williamsvirginiavassilevska graphpatterndetectionhardnessforallinducedpatternsandfasternoninducedcycles |