SIAM Journal on Discrete Mathematics · 2013 · 43 citations · 22 references
ComputingComputer ScienceMathematicsAlgorithmsCombinatoricsTheory Of ComputationComputational ComplexityGraph AlgorithmsGraph TheoryMatrix ComputationComputational Complexity Of Graph AlgorithmsCounting ComplexityGraph EnumerationIndependent Set AlgorithmsMatrix ExponentiationMatrix MultiplicationSubgraph CountingSubgraph Isomorphism
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.
22
Matrix multiplication via arithmetic progressions
Don Coppersmith, S. Winograd · Journal of Symbolic Computation · 1990 · 2.3K citations
Noga Alon, Raphael Yuster, Uri Zwick · Journal of the ACM · 1995 · 1K citations · Full text
Multiplying matrices faster than coppersmith-winograd
Virginia Vassilevska Williams · 2012 · 887 citations
Arboricity and Subgraph Listing Algorithms
Norishige Chiba, Takao Nishizeki · SIAM Journal on Computing · 1985 · 665 citations
Finding and counting given length cycles
Noga Alon, Raphael Yuster, Uri Zwick · Algorithmica · 1997 · 613 citations