A classification of subquadratic patterns for minimum-weight, enumeration, and listing subgraph isomorphism problems

isomorphism problem for a general pattern graph H is a big open
problem in parameterized complexity. We answer this question for
patterns with low time complexity for Minimum Weight, Listing, and
Enumeration versions of the problem. We develop optimal algorithms and
matching conditional lower bounds for all pattern graphs H, for which
the problem can be solved in truly subquadratic time in terms of the
number of edges in the input graph. As a consequence, we also classify
all the pattern graphs with submodular widths smaller than two and
find the exact values of their submodular widths. Furthermore, for the
first time, we present a pattern graph H, for which the celebrated
high-degree-low-degree method is not sufficient to get an optimal
algorithm.