Subgraph Counting in Subquadratic Time for Bounded Degeneracy Graphs

As a secondary result, we are able to show that cycle counting in bounded degeneracy graphs can be done even faster. These results are tight, in the sense that any improvement will imply beating long standing cycle detection algorithms for sparse graphs. Let ${𝒞}_k$ denote the $k$-cycle and $d_k$ be the exponent (in terms of edges) of the current fastest algorithm for $k$-cycle detection in general graphs (see (3) and [29]). Gishboliner-Levanzov-Shapira-Yuster (henceforth GLSY) recently showed that homomorphism counting of ${𝒞}_{2k}$ in bounded degeneracy graphs can be done in time $O(n^{d_k})$ [29]. We prove that this complexity can be matched for the problem of subgraph counting. Cycle counting is more challenging, since it involves compute linear combinations of homomorphisms of non-cyclic patterns (which requires other techniques).

Previously, for bounded degeneracy graphs, subquadratic results were only known for detecting cycles, by a result of Alon, Yuster and Zwick [3]. Theorem 1.2 improves or matches their bounds in all cases, despite solving the harder problem of counting. The lower bounds relating to cycle counting in general graphs follow directly from the techniques of GLSY [29]. We note that the exponents $d_k$ have not been improved for twenty years [3, 53]. As a side corollary of our methods, we also get a better algorithm for counting $5$-cycles in arbitrary graphs (Corollary 1.7).

It is well-known (from [3]) that linear-time orientation based methods hit an obstruction at $6$-cycles. Consider the oriented $6$-cycle in the left of Fig. 1. It is basically a “triangle” of out-out wedges (as given by the red lines); indeed, one can show that $6$-cycle counting in bounded degeneracy graphs is essentially equivalent to triangle counting in arbitrary graphs [6, 7, 5]. This observation can be converted into an algorithm, as was shown by GLSY [29]. Starting with $\overrightarrow{G}$, we create a new graph with edges (the red lines) corresponding to the endpoints of out-out wedges. Since $\overrightarrow{G}$ has bounded outdegree, the number of edges in the new graph is $O(n)$. Every triangle in the new graph corresponds to a (directed) $6$-cycle homomorphism in $\overrightarrow{G}$. Triangle counting in the new graph can be done in $O(n^{1.41})$ time (or $n^{3/2}$ time using a combinatorial algorithm) [3]. Getting the subgraph count is more involved, but we can use existing methods that reduce to homomorphism counting [19].

One can extend this idea more generally as follows. Let $\overrightarrow{H}$ be a directed pattern, a source is any vertex with no incoming arcs, and we define an intersection vertex as any vertex that can be “reached” by two different sources.

Suppose there are $k$ sources and $k$ intersection vertices. Suppose further that there is an ordering of the sources $\{s_0,\mathrm{\dots },s_{k-1}\}$ and the intersection vertices $\{i_0,\mathrm{\dots },i_{k-1}\}$ of $\overrightarrow{H}$ such that, for all $j$, only the sources $s_j$ and $s_{j+1}$ (taking modulo $k$ in the indexes) can both reach the vertex $i_j$. This is the case of the oriented ${𝒞}_6$ and ${𝒞}_8$ in Fig. 1 or of any acyclic orientation of any cycle. One can then construct a new graph $G^{\prime }$ such that ${\mathrm{Sub}}_{{𝒞}_k}(G^{\prime })$ is the same as ${\mathrm{Hom}}_{\overrightarrow{H}}(\overrightarrow{G})$ (where ${\mathrm{Hom}}_{\overrightarrow{H}}(\overrightarrow{G})$ denotes the homomorphism count).

So far, the algorithmic approach only makes sense for cycle patterns. Our main contribution is a framework that generalizes this approach to count homomorphisms and subgraphs of more complex patterns.

The first part of our framework is the concept of $P$-reducible patterns. Let $P$ be a hypergraph, a directed pattern is $P$-reducible if we can reduce counting homomorphisms of it to counting $P$ subgraphs in a sparse hypergraph. The formal definition is technical and can be seen in §3. We provide a simplified exposition in this section.

Consider a directed pattern $\overrightarrow{H}$, for example the left image in Fig. 2. We can replace every source with a hyperedge connecting the intersection vertices reachable from the source. The result is a graph (or hypergraph) $P$ such that $\overrightarrow{H}$ is $P$-reducible.

However, our framework allows for even more freedom: instead of looking at individual sources, we partition sources into sets of sources $S_e$. See the rightmost figure in Fig. 2 for an example, where the $6$ sources are divided into $4$ sets of sources. The sub-patterns induced by the vertices reachable from every set of sources are “easy” to count using existing techniques. We can also arrange the intersection vertices into sets $I_v$ such that every set of sources will reach some sets of intersection vertices. We can obtain $P$ by replacing every set of intersection vertices with a vertex and every set of sources $S_e$ with a hyperedge $e$ that contains the vertices corresponding to the sets of intersection vertices that can be reached by $S_e$.

In the second example of Fig. 2, the intersection of the vertices reachable from source sets forms a “cyclic arrangement”. The intersection vertices reachable from $S_1$ are also reachable from $S_2$ and $S_4$, and similarly for the other sets of sources, giving that the pattern will be ${𝒞}_4$-reducible.

The second part of our framework is the reduced graph. If a pattern is $P$-reducible, then for any directed input graph $\overrightarrow{G}$, we can construct a colored weighted graph $G_P$ with the following property. The number of homomorphisms of the original pattern relates to the number of colorful copies of $P$ in $G_P$.

The reduced graph consists of $|V(P)|$ layers of vertices, where each layer is related to one intersection set of $\overrightarrow{H}$. Specifically, there is a vertex in the $j$-th layer for every possible image of the corresponding intersection set $I_j$ in $\overrightarrow{G}$, that is, every set of vertices in $\overrightarrow{G}$ such that $I_j$ can be mapped to it. Moreover, the vertices of every layer will have the same color. For example, for every intersection set $I_j$ in $\overrightarrow{H}$ and any map $\varphi :I_j\to \overrightarrow{G}$ there is a vertex $(\varphi (I_j)-j)$ in $G_P$ with color $j$.³³3There could be $O(n^{|I_j|})$ such vertices, however, as we will note later, there will be at most $O(n)$ edges, so we can ignore vertices with degree $0$ and we do not need to even create them.

The edges have weights that represent the number of homomorphisms mapping the intersection sets to the corresponding images. For example, let $S$ be a source set reaching two intersection sets $I_j=\{i_j\}$ and $I_{j^{\prime }}=\{i_{j^{\prime }}\}$, and let $u,v\in \overrightarrow{G}$. An edge $e$ connecting $(u-j)$ and $(v-j^{\prime })$ with weight $w=w(e)$ indicates that there are $w$ different homomorphisms mapping $\overrightarrow{H}(S)$ (the subgraph of $\overrightarrow{H}$ induced by the vertices reachable from $S$) to $\overrightarrow{G}$ that map $j$ to $u$ and $j^{\prime }$ to $v$. Additionally we can show that if $\overrightarrow{G}$ has bounded outdegree, then the new reduced graph will have $O(n)$ edges.

We give an example in Fig. 3. For simplicity of exposition, the graph $\overrightarrow{G}$ is smaller than the pattern. Each vertex of $\overrightarrow{G}$ has three copies (each with a different color) in the reduced graph, denoted $G_{{𝒞}_3}$. Since the vertex $a$ cannot be the image of any intersection vertex (it has zero indegree), copies of this vertex do not appear in $G_{{𝒞}_3}$. Observe that there is no mapping of an out-out wedge where $b$ is one endpoint and $d$ is the other endpoint. Hence, there is no edge from a copy of $b$ to a copy of $d$.

Every colorful copy of $P$ in $G_P$ correspond to fixing the positions of the intersection sets in $\overrightarrow{G}$, and the weight of each hyperedge will correspond to the number of homomorphisms mapping that portion of the graph. Hence the product of the weights of all hyperedges in each copy will give the total number of homomorphisms mapping all the intersection sets to the corresponding vertices in $\overrightarrow{G}$. Therefore, the total number of homomorphisms will be equal to the quantity ${\text{Col-WSub}}_P(G_P)$, which corresponds to the sum of products of weights of colorful copies of $P$. That is:

Here, $\text{Col-}𝒮(P,G_P)$ denotes the set of distinct colorful copies of $P$ in $G_P$. We are able to show that solving ${\text{Col-WSub}}_P(G_P)$ is equivalent to counting the number of homomorphisms of $\overrightarrow{H}$ in $\overrightarrow{G}$.

Therefore, we can count homomorphisms of $P$-reducible patterns in the same time as counting colorful copies of $P$ in the reduced graph.

To extend our reduction framework to undirected graphs we introduce the concept of $𝒫$-computable patterns. Note that different acyclic orientations of the same pattern might reduce to different graphs. Let $𝒫$ be a set of graphs, we say that a pattern $H$ is $𝒫$-computable if all the acyclic orientations of $H$ can be computed in linear time or are $P$-reducible for some $P\in 𝒫$. If for all the patterns in $𝒫$ we can compute ${\text{Col-WSub}}_P$ in time $O(m^c)$ then we can use Lemma 1.3 to get a bound on the complexity of ${\mathrm{Hom}}_H(G)$.

For each $k\ge 6$, we find a set of hypergraphs ${𝒫}_k$ such that all patterns with $k$ vertices are ${𝒫}_k$-computable. These sets grow with $k$ and we have ${𝒫}_k\subseteq {𝒫}_{k+1}$. We give a definition of these sets in Section §5 and prove the following lemma.

For $k=9$ we are able to show that there exists a subset ${𝒫}_9^{\ast }$ of ${𝒫}_9$ such that every $9$-vertex pattern is also ${𝒫}_9^{\ast }$-computable and for every pattern $P\in {𝒫}_9^{\ast }$ we can compute ${\text{Col-WSub}}_P$ in $\tilde{O}(m^{5/3})$ time. Allowing us to show that for all patterns with $9$ vertices or less we can count the number of homomorphisms in subquadratic time.

We can also show similar results for cycles. All orientations of cycle patterns can be reduced to cycles of half their length. This means that any $2k$-cycle and $2k+1$-cycle are $\{{𝒞}_k\cup \mathrm{\dots }\cup {𝒞}_3\}$-computable (in these cases we will simply write ${𝒞}_k$-computable).

We can also show that for all cycles we can compute ${\text{Col-WSub}}_{{𝒞}_k}(G)$ in $\tilde{O}(m^{d_k})$ time, the fastest time for detecting $k$-cycles in general graphs.

This means that we can compute the number of homomorphisms of ${𝒞}_{2k}$ and ${𝒞}_{2k+1}$ in time $\tilde{O}(m^{d_k})$, similar result to the one obtained in GLSY [29].

At this point, we have algorithms for computing various pattern homomorphisms. To get subgraph counts, we need the inclusion-exclusion techniques of [19]. One can express the $H$-subgraph count as a linear combination of $H^{\prime }$-homomorphism counts, where $H^{\prime }$ is a pattern in $Spasm(H)$. The $Spasm(H)$ consists of all patterns $H^{\prime }$ such that $H$ has a surjective homomorphism to $H^{\prime }$. Thus, every pattern in the spasm has at most as many vertices as $H$.

Hence for any pattern $H$ with $k$ vertices, all the patterns in $Spasm(H)$ will have at most $k$ vertices and hence they will also be ${𝒫}_k$-computable, giving Theorem 1.1.

In the case of the cycles, to be able to extend the results from last section to the $Sub$ problem, we analyze the spasm of the different cycles. For $k\le 10$ we are able to show that the patterns in the spasms of ${𝒞}_k$ are also ${𝒞}_{\lfloor k/2\rfloor }$-computable. That combined with Lemma 1.5 implies the upper bound of Theorem 1.2.

We show that in some cases our reduction procedure is optimal. For example, counting small cycles in general graphs can be reduced to counting cycles of twice the length in graphs of degeneracy $\kappa =2$. The reduction is quite simple and just involves subdividing the edges. With a slight modification, the subdivision approach can be used to show lower bounds for odd cycles too, which gives the lower bound of Theorem 1.2. We note that an analogous result for counting homomorphisms was shown in GLSY [29].

This inversion of the reduction procedure also gives us an algorithm for counting undirected $5$-cycles in general graphs which improves on the current state of the art, and matches the complexity for $5$-cycle detection.

The approach of subdividing edges can be used to prove a relation between other patterns too. In the case of hypergraphs, we can replace hyperedges of arity $r$ by $r$-stars. We are able to show a strong relation between the hypergraph ${\mathscr{H}}_{\mathrm{△}}$ depicted in Fig. 4, and a $10$-vertex pattern. We conjecture that for this pattern we can not count the number of subgraphs in subquadratic time.

This conjecture implies that there are no subquadratic algorithms for computing the number of subgraphs of all $10$-vertex patterns.

We consider it an interesting open problem to relate our conjecture with existing fine-grained complexity assumptions. Some previous works prove barriers for subquadratic listing in general graphs [16], but no similar results exist for counting hypergraphs.