#### 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.

Done