Graph pattern detection: hardness for all induced patterns and faster non-induced cycles

DOI10.1145/3313276.3316329MaRDI QIDQ5212856zbMATH OpenOpenAlexFDO

Authors M. Dalirrooyfard, Thuy Duong Vuong, Virginia Vassilevska Williams

Publication date 30 January 2020

Published in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1904.03741

zbMATH Keywords

cliquescycle detectionfine-grained complexitysubgraph isomorphism

Mathematics Subject Classification ID

Paths and cycles (05C38) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Abstract: 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$. Our main results are: * 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: (1) under Hadwiger's conjecture for every $k$-node pattern $H$, finding an induced copy of $H$ requires at least the time of $sqrtk$-clique detection, and at least size $omega(n^{sqrtk/4})$ for any constant depth circuit, and (2) unconditionally, detecting an induced copy of a random $G(k,p)$ pattern w.h.p. requires at least the time of $Theta(k/logk)$-clique detection, and hence also at least size $n^{Omega(k/logk)}$ for circuits of constant depth. * 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$.

Recommendations

• Graph pattern detection: hardness for all induced patterns and faster noninduced cycles
• A fast deterministic detection of small pattern graphs in graphs without large cliques
• A fast deterministic detection of small pattern graphs in graphs without large cliques
• Induced subgraph isomorphism: are some patterns substantially easier than others?
• Detecting and counting small pattern graphs

Cited in

(18)

• A fast deterministic detection of small pattern graphs in graphs without large cliques
• Induced subgraph isomorphism: are some patterns substantially easier than others?
• A fast deterministic detection of small pattern graphs in graphs without large cliques
• Algorithms and hardness for diameter in dynamic graphs
• Graph pattern detection: hardness for all induced patterns and faster noninduced cycles
• Counting Subgraphs in Degenerate Graphs
• Rare siblings speed-up deterministic detection and counting of small pattern graphs
• Counting Homomorphic Cycles in Degenerate Graphs
• Finding a shortest even hole in polynomial time
• Faster combinatorial \(k\)-clique algorithms
• Blazing a trail via matrix multiplications: a faster algorithm for non-shortest induced paths
• Finding and counting small tournaments in large tournaments
• The strongish planted clique hypothesis and its consequences
• Current algorithms for detecting subgraphs of bounded treewidth are probably optimal
• Improved algorithms for perfect graphs and odd holes
• Faster combinatorial k-clique algorithms
• Testing C_k-freeness in bounded admissibility graphs
• Induced subgraph isomorphism: are some patterns substantially easier than others?

This page was built for publication: Graph pattern detection: hardness for all induced patterns and faster non-induced cycles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5212856)