Counting and Detecting Small Subgraphs via Equations
Mirosław Kowaluk, Andrzej Lingas, Eva-Marta Lundell · SIAM Journal on Discrete Mathematics · 2013
We present a general technique for detecting and counting small subgraphs. It consists of forming special linear combinations of the numbers of occurrences of different induced subgraphs of fixed size in a graph. These combinations can be efficiently computed by rectangular matrix multiplication. Our two main results utilizing the technique are as follows. Let $H$ be a fixed graph with $k$ vertices and an independent set of size $s.$ 1. Detecting if an $n$-vertex graph contains a (not necessarily induced) subgraph isomorphic to $H$ can be done in time $O(n^{\omega(\lceil (k-s)/2 \rceil, 1, \lfloor (k-s)/2 \rfloor )})$, where $\omega (p,q,r)$ is the exponent of fast arithmetic matrix multiplication of an $n^p\times n^q$ matrix by an $n^q\times n^r$ matrix. 2. When $s=2,$ counting the number of (not necessarily induced) subgraphs isomorphic to $H$ can be done in the same time, i.e., in time $O(n^{\omega(\lceil (k-2)/2 \rceil, 1, \lfloor (k-2)/2 \rfloor )}).$ It follows in particular that we can count the number of subgraphs isomorphic to any $H$ on four vertices that is not $K_4$ in time $O(n^{\omega})$, where $\omega =\omega (1,1,1)$ is known to be smaller than 2.373. Similarly, we can count the number of subgraphs isomorphic to any $H$ on five vertices that is not $K_5$ in time $O(n^{\omega(2,1,1)}),$ where $\omega(2,1,1)$ is known to be smaller than 3.257. Finally, we derive input-sensitive variants of our time upper bounds. They are partially expressed in terms of the number $m$ of edges of the input graph and do not rely on fast matrix multiplication.