Counting and detecting small subgraphs via equations and matrix multiplication
Mirosław Kowaluk, Andrzej Lingas, Eva-Marta Lundell · 2011
We present a general technique for detecting and counting small subgraphs.It consists in forming special linear combinations of the numbers of occurrences of different induced subgraphs of fixed size in a graph.The 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 (nonnecessarily induced) subgraph isomorphic to H can be done in timewhere ω(p, q, r) is the exponent of fast arithmetic matrix multiplication of an n p × n q matrix by an n q × n r matrix.2. When s = 2, counting the number of (nonnecessarily induced) subgraphs isomorphic to H can be done in the same time, i.e., in time O(n k-2 + n ω( (k-2)/2 ,1, (k-2)/2 ) ). (This improves for s = 2 on a counting algorithm of Vassilevska and Williams, running in time O(n k-s+3 ).)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 ω ), where ω = ω(1, 1, 1) is known to be smaller than 2.376.Similarly, we can count the number of subgraphs isomorphic to any H on five vertices that is not K 5 in time O(n ω(2,1,1) ), where ω(2, 1, 1) is known to be smaller than 3.334.