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

DOI10.1145/3313276.3316329zbMath1433.68289arXiv1904.03741OpenAlexW2962817833MaRDI QIDQ5212856

Thuy Duong Vuong, Mina Dalirrooyfard, 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

cliquessubgraph isomorphismfine-grained complexitycycle detection

Mathematics Subject Classification ID

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

Related Items (5)

Counting Subgraphs in Degenerate Graphs ⋮ Counting Homomorphic Cycles in Degenerate Graphs ⋮ Finding a shortest even hole in polynomial time ⋮ Unnamed Item ⋮ Rare siblings speed-up deterministic detection and counting of small pattern graphs

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