Beating Treewidth for Average-Case Subgraph Isomorphism

Gregory Rosenthal

For any fixed graph $G$, the subgraph isomorphism problem asks whether an $n$-vertex input graph has a subgraph isomorphic to $G$. A well-known algorithm of Alon, Yuster and Zwick…