Alladi Ramakrishnan Hall

Finding Graph Patterns

Balagopal Komarath

Saarland University, Germany

In this talk, we will look at algorithms
for the (induced and not necessarily induced) subgraph
isomorphism problem when the pattern graph is a fixed
graph. Very little progress has been made on the induced
version since Nesetril and Poljak (1985) showed how to use
fast matrix multiplication to speed up detection and
counting of all k-vertex pattern graphs. One of the open
questions stated in their work was whether there exists
some k-vertex patterns that are easier than the k-clique
(the hardest pattern). We (BKS 2018) show that there are
k-vertex patterns that are easier than k-cliques.

The main technical contribution of this work is the notion
of a reduction that captures algorithms that reduce graph
pattern detection into the multilinear monomial detection
problem in some polynomial family. All known algorithms for
fixed-pattern induced subgraph isomorphism can be stated in
this fashion. We show that within this framework, so-called
graph homomorphism polynomials are the most efficient.
i.e., if a fixed-pattern subgraph isomorphism problem can
be reduced to multilinear monomial detection in some
efficiently-constructible polynomial family, then we can
efficiently construct the graph homomorphism polynomial for
that pattern and use it to solve the problem. This explains
the prevalence of graph homomorphism polynomials in
algorithms for fixed-pattern subgraph isomorphism.