Graph Pattern Detection: Hardness for all Induced Patterns and Faster Noninduced Cycles
DOI10.1137/20M1335054zbMath1478.05145MaRDI QIDQ5860479
Thuy Duong Vuong, Mina Dalirrooyfard, Virginia Vassilevska Williams
Publication date: 19 November 2021
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Pattern recognition, speech recognition (68T10) Paths and cycles (05C38) Complexity of computation (including implicit computational complexity) (03D15) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Finding and counting small induced subgraphs efficiently
- Faster algorithms for finding and counting subgraphs
- Finding and counting given length cycles
- On the complexity of fixed parameter clique and dominating set
- Induced subgraph isomorphism: are some patterns substantially easier than others?
- Efficient algorithms for clique problems
- Hadwiger's conjecture is true for almost every graph
- Hadwiger's conjecture for \(K_ 6\)-free graphs
- The four-colour theorem
- Cycles of even length in graphs
- Any 7-chromatic graph has \(K_7\) or \(K_{4,4}\) as a minor
- Tight lower bounds for certain parameterized NP-hard problems
- Über eine Eigenschaft der ebenen Komplexe
- Counting and Detecting Small Subgraphs via Equations
- Detecting and Counting Small Pattern Graphs
- On the Primes in the Interval [3n, 4n]
- A Fast Deterministic Detection of Small Pattern Graphs in Graphs Without Large Cliques
- Powers of tensors and fast matrix multiplication
- A simple linear-time algorithm for computing the center of an interval graph
- A Linear Recognition Algorithm for Cographs
- Finding a Minimum Circuit in a Graph
- Color-coding
- If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser
- Finding even cycles even faster
- Finding even cycles faster via capped k-walks
- Homomorphisms are a good basis for counting small subgraphs
- Finding, minimizing, and counting weighted subgraphs
- Finding Four-Node Subgraphs in Triangle Time
- Multiplying matrices faster than coppersmith-winograd
- On the interval containing at least one prime number
- The chromatic number of random graphs
- On the complexity of \(k\)-SAT
This page was built for publication: Graph Pattern Detection: Hardness for all Induced Patterns and Faster Noninduced Cycles
