Faster algorithms for finding and counting subgraphs

摘要

In the Subgraph Isomorphism problem we are given two graphs F and G on k and n vertices respectively as an input, and the question is whether there exists a subgraph of G isomorphic to F. We show that if the treewidth of F is at most t, then there is a randomized algorithm for the Subgraph Isomorphism problem running in time O⁎(2kn2t). Our proof is based on a novel construction of an arithmetic circuit of size at most nO(t) for a new multivariate polynomial, Homomorphism Polynomial, of degree at most k, which in turn is used to solve the Subgraph Isomorphism problem. For the counting version of the Subgraph Isomorphism problem, where the objective is to count the number of distinct subgraphs of G that are isomorphic to F, we give a deterministic algorithm running in time and space O⁎((nk/2)n2p) or (nk/2)nO(tlogk). We also give an algorithm running in time O⁎(2k(nk/2)n5p) and taking O⁎(np) space. Here p and t denote the pathwidth and the treewidth of F, respectively. Our work improves on the previous results on Subgraph Isomorphism, it also extends and unifies most of the known results on sub-path and sub-tree isomorphisms.