Counting Homomorphic Cycles in Degenerate Graphs
Article No.: 2, Pages 1 - 22
Abstract
Since counting subgraphs in general graphs is, by and large, a computationally demanding problem, it is natural to try and design fast algorithms for restricted families of graphs. One such family that has been extensively studied is that of graphs of bounded degeneracy (e.g., planar graphs). This line of work, which started in the early 80’s, culminated in a recent work of Gishboliner et al., which highlighted the importance of the task of counting homomorphic copies of cycles (i.e., cyclic walks) in graphs of bounded degeneracy.
Our main result in this paper is a surprisingly tight relation between the above task and the well-studied problem of detecting (standard) copies of directed cycles in general directed graphs. More precisely, we prove the following:
•
One can compute the number of homomorphic copies of C2k and C2k+1 in n-vertex graphs of bounded degeneracy in time Õ(ndk), where the fastest known algorithm for detecting directed copies of Ck in general m-edge digraphs runs in time Õ(mdk).
•
Conversely, one can transform any O(nbk) algorithm for computing the number of homomorphic copies of C2k or of C2k+1 in n-vertex graphs of bounded degeneracy, into an Õ(mbk) time algorithm for detecting directed copies of Ck in general m-edge digraphs.
We emphasize that our first result does not use a black-box reduction (as opposed to the second result which does). Instead, we design an algorithm for computing the number of Ck-homomorphisms in degenerate graphs and show that one part of its analysis can be reduced to the analysis of the fastest known algorithm for detecting directed cycles in general digraphs, which was carried out in a recent breakthrough of Dalirrooyfard, Vuong and Vassilevska Williams. As a by-product of our algorithm, we obtain a new algorithm for detecting k-cycles in directed and undirected graphs of bounded degeneracy that is faster than all previously known algorithms for 7 ≤ k ≤ 11, and faster for all k ≥ 7 if the matrix multiplication exponent is 2.
1 Introduction
Counting occurrences of small subgraphs in a given input graph is among the most fundamental algorithmic problems. Most prominently, it is the subject of a rich line of research in parameterized complexity theory [12, 13, 15, 18, 19, 25, 27, 31, 36], which has by now produced several important general results on the fixed-parameter tractability of subgraph counting problems [15, 19, 25]. Works in this area are too numerous to survey here, so we refer the reader to the above-cited papers for further references. On the practical side of things, subgraph counting is important due to the role played by subgraph counts in the analysis of real-world networks, see, e.g., [28, 32], and the references therein.
1.1 Detecting and Counting Cycles
One of the most fundamental and well-studied cases of subgraph-counting is that of counting (and detecting) cycles. Such questions have been studied in both undirected and directed graphs. We will always denote by \(n\) the number of vertices of the input graph and by \(m\) its number of edges. The problem of counting copies of a \(k\) -length cycle is known to be \(\#W[1]\) -hard [18], meaning that it is unlikely to admit an algorithm which runs in time \(f(k) \cdot n^{O(1)}\) for any computable function \(f\) . For cycle detection, however, efficient algorithms exist and are the subject of numerous works [3, 4, 16, 21, 22, 29, 38, 39]. Notably, Alon, Yuster, and Zwick [4] presented several cycle detection algorithms for both the undirected and directed settings, improving upon earlier results of Itai and Rodeh [21] and Monien [29]. Some of these algorithms used the technique of color-coding, introduced earlier in [3]. Most relevant for us is the problem of detecting directed cycles in digraphs, where [4] provided a classical algorithm that detects a directed \(k\) -cycle (for a fixed \(k\) ) in an \(m\) -edge directed graph running in time
\begin{equation} O(m^{2-1/\lceil k/2 \rceil }). \end{equation}
(1)
This is still the fastest combinatorial algorithm for directed \(k\) -cycle detection in terms of \(m\) ; see the remark at the end of Section 1.4 concerning its optimality. However, faster algorithms exist if we use algebraic algorithms relying on fast matrix multiplication. Let \(\omega\) denote the exponent of fast matrix multiplication, namely the infimum over all constants \(t\) such that two \(n \times n\) matrices can be multiplied using \(\tilde{O}(n^t)\) field operations. It is known that \(\omega \lt 2.373\) [2, 23]. Indeed, motivated by a simple \(O(m^{2\omega /(\omega +1)})\) time algorithm of [4] for detecting a 3-cycle, Yuster and Zwick [38] set out to use fast matrix multiplication for \(k\) -cycle detection (for a fixed \(k\) ). They obtained an algorithm running in time \(\tilde{O}(m^{c_k})\) , and were able to show that for \(k=4,5\) , the value of \(c_k\) (which they explicitly computed for \(k=4,5\) ) is strictly smaller than \(2-1/\lceil k/2 \rceil\) , thereby improving upon the aforementioned combinatorial algorithm. It is, to date, the fastest algorithm for directed \(k\) -cycle detection when \(k=4,5\) in terms of \(m\) . For \(k \ge 6\) , the exact value of \(c_k\) turned out to be hard to analyze, due to an involved use of dynamic programming, which resulted in a complicated recursive relation. This led Yuster and Zwick to raise a conjecture1 regarding the runtime of their algorithm (i.e., the value of \(c_k\) ). This conjecture was recently resolved by Dalirrooyfard, Vuong, and Vassilevska Williams [14], establishing that the algorithm of Yuster and Zwick detects a directed \(k\) -cycle in a graph with \(m\) edges in time \(\tilde{O}(m^{c_k})\) , where2
\begin{align} c_k & \le \frac{(k+1)\omega }{2\omega + k-1} \qquad \qquad \mbox{if } k \mbox{ is odd,} \\ c_k & \le \frac{k\omega - \frac{4}{k}}{2\omega + k-2-\frac{4}{k}} \qquad \, \mbox{if } k \mbox{ is even.} \nonumber \nonumber \end{align}
(2)
It should be noted that equality holds in the odd case when \(\omega \le \frac{2k}{k-1}\) .3 Moreover, it was proved in [14] that equality holds also in the even case if \(\omega =2\) and the exact value of \(c_6\) was determined for all \(\omega\) . To date, for any pair \((k,\omega)\) with \(k \ge 3\) and \(2 \le \omega \lt 2.373\) , the fastest algorithm for detecting a directed \(k\) -cycle in a directed \(m\) -edge graph (i.e., in terms of \(m\) alone) is either the combinatorial \(O(m^{2-1/\lceil k/2 \rceil })\) algorithm or the \(\tilde{O}(m^{c_k})\) algorithm (which of them is faster depends on \((k,\omega)\) ). It is easy to verify that if \(\omega \gt 2\) , then for all large enough \(k\) the \(O(m^{2-1/\lceil k/2 \rceil })\) is faster, while if \(\omega = 2\) then \(\tilde{O}(m^{c_k})\) is always faster, and \(c_k\) is approximately \(2 - \frac{4}{k}\) in this case (for \(k\) large).
1.2 Counting Homomorphisms in Degenerate Graphs
In this work we are concerned with the problem of counting homomorphisms of cycles (i.e., cyclic walks of a given length) in graphs of bounded degeneracy.4 Arguably, homomorphism-counting is the most basic subgraph counting problem, to which other natural problems — such as counting copies or induced copies — can be reduced [12].
Recall that a graph is called \(d\) -degenerate if it admits a vertex ordering \(v_1,\dots ,v_n\) such that \(v_i\) has at most \(d\) neighbors among \(v_{i+1},\dots ,v_n\) (for every \(1 \le i \le n\) ). In the setting considered here, we look for algorithms which run in time \(f(d) \cdot n^{\alpha }\) , where \(d\) is the degeneracy5 of the input graph, \(n\) is its number of vertices, and \(\alpha\) does not depend on \(d\) . Such algorithms are particularly useful when the input graph has bounded degeneracy. The family of such graphs is rich, including for example all non-trivial minor-closed graph classes (in particular, planar graphs), preferential attachment graphs [5], and bounded expansion graphs [30].
The study of subgraph counting in degenerate graphs goes back to a classical work of Chiba and Nishizeki [11] from the early 1980s. Very recently, this research direction has seen several substantial developments [6, 7, 8, 10]. Bressan [10] gave a general algorithm for counting homomorphisms in bounded-degeneracy graphs, which in particular implies a sufficient condition6 (on graphs \(H\) ) under which \(H\) -homomorphisms can be counted in time \(\tilde{O}(n)\) . In [6], it was shown that this sufficient condition is also necessary, and moreover, a clean combinatorial characterization of the graphs \(H\) satisfying it was obtained. Specifically, it was shown that \(H\) -homomorphisms in bounded-degeneracy graphs can be counted in time \(\tilde{O}(n)\) if and only if \(H\) contains no induced cycles of length 6 or larger.7 A similar result has been independently obtained in [8]. These results highlight the important role played by cycles of length at least 6, as being the minimal graphs whose homomorphisms cannot be counted in (almost) linear time (in bounded-degeneracy graphs). This motivates the study of the time complexity of counting homomorphisms of such cycles (with the intention of improving the running time of Bressan’s general algorithm for cycles), which is precisely the question studied in the present paper.
1.3 Our Results
Let \(C_k\) denote the cycle of length \(k\) (where \(k\) is fixed throughout the paper). Here we state our results regarding the problem of counting \(C_k\) -homomorphisms in graphs of bounded degeneracy. By the aforementioned result of Bressan [10], if \(3 \le k \le 5\) then \(C_k\) -homomorphisms can be counted in near-linear time (which is optimal), and we therefore focus on the case \(k \ge 6\) . As our main results in this paper show, the problem of counting \(C_{2k}\) - and \(C_{2k+1}\) -homomorphisms in bounded-degeneracy graphs is related to the problem of detecting directed \(k\) -cycles in general (i.e., not necessarily degenerate) digraphs. In particular, we shall design two algorithms: a combinatorial algorithm for counting cycle homomorphisms whose runtime corresponds to the runtime of the combinatorial \(k\) -cycle detection algorithm of [4], and an algorithm for counting cycle homomorphisms whose runtime obeys the same recursive relation as the aforementioned directed-cycle detection algorithm of Yuster and Zwick [38]. Combining these two algorithms and the work of Dalirrooyfard, Vuong and Vassilevska Williams [14], we will obtain the following theorem, which is our main result in this paper. Let \({\rm\small HOM-CNT}_{H}\) denote the problem of computing the number of \(H\) -homomorphisms.
For every \(k \ge 2\) , the following hold:
(i) \({\rm\small HOM-CNT}_{C_{2k}}\) and \({\rm\small HOM-CNT}_{C_{2k+1}}\) can be solved in bounded-degeneracy graphs in time \(\tilde{O}(n^{c_k})\) , where \(c_k\) is as defined in (9).
(ii) \({\rm\small HOM-CNT}_{C_{2k}}\) and \({\rm\small HOM-CNT}_{C_{2k+1}}\) can be solved in bounded-degeneracy graphs in time \(\tilde{O}(n^{2-1/\lceil k/2 \rceil })\) .
The algorithm of case (i) in Theorem 1 combines the general structure of the Yuster-Zwick algorithm with several significant additional twists used in the setting of degenerate graphs, inspired by the approach in [10].
As opposed to the algorithm of case (i) which relies on fast matrix multiplication, the algorithm of case (ii) is purely combinatorial. Furthermore, it can be modified to give a combinatorial algorithm for counting \(C_k\) -homomorphisms in general (i.e., not necessarily degenerate) graphs, both directed and undirected, which runs in time \(\tilde{O}(m^{2-1/\lceil k/2 \rceil })\) . This algorithm can in turn be used to obtain a new combinatorial algorithm for directed \(k\) -cycle detection, which essentially matches the runtime of the best such combinatorial algorithm to date, namely the algorithm of [4] mentioned above, while being somewhat simpler. It should be noted that another combinatorial cycle-detection algorithm with the same runtime was given in [37] (see also [22]). The details appear in Section 7.
The relation to directed-cycle detection is in fact more robust, as is evidenced by our next result, which states that counting \(C_{2k}\) - or \(C_{2k+1}\) -homomorphisms already in 2-degenerate graphs is at least as hard as detecting a directed \(k\) -cycle in general digraphs. Note that if \(k=2\) then both problems can be solved in time linear in the number of edges, so the interesting case is when \(k \ge 3\) . Formally, we prove the following theorem.
Let \(k \ge 3\) . If there is an algorithm that computes \({\rm\small HOM-CNT}_{C_{2k}}\) or \({\rm\small HOM-CNT}_{C_{2k+1}}\) in 2-degenerate graphs in \(O(n^\alpha)\) time, then there is an algorithm that decides if an arbitrary directed \(m\) -edge graph has a directed \(k\) -cycle in time \(O(m^\alpha)\) (randomized) and \(O(m^\alpha \log m)\) (deterministic).
To make the relation between directed-cycle detection in general graphs and counting cycle homomorphisms in bounded-degeneracy graphs even sharper, recall that for all \(k \ge 3\) , the presently fastest \(k\) -cycle detection algorithm in \(m\) -edge directed graphs is either the \(O(m^{2-1/\lceil k/2 \rceil })\) algorithm [4] or the \(\tilde{O}(m^{c_k})\) algorithm [14, 38]. Let us therefore define for a given \(2 \le \omega \lt 2.373\) Recall that if \(\omega \gt 2,\) then for all large enough \(k\) we have \(d_k = 2-1/{\lceil k/2 \rceil }\) (i.e., the second term is smaller), while if \(\omega = 2,\) then \(d_k = c_k\) for all \(k \ge 3\) . The following corollary immediately follows from Theorems 1 and 2.
\begin{equation*} d_k = \min \lbrace c_k \,,\,2-1/{\lceil k/2 \rceil }\rbrace \;. \end{equation*}
Let \(k \ge 3\) . If the fastest algorithm (in terms of the number of edges \(m\) ) for deciding if a directed graph has a directed \(k\) -cycle runs in \(\tilde{O}(m^{d_k})\) time, then the fastest algorithm for computing \({\rm\small HOM-CNT}_{C_{2k}}\) in degenerate graphs runs in \(\tilde{O}(n^{d_k})\) time and the fastest algorithm for computing \({\rm\small HOM-CNT}_{C_{2k+1}}\) in degenerate graphs runs in \(\tilde{O}(n^{d_k})\) time.
In particular, for every \(\varepsilon \gt 0\) , if we can improve the bound in Theorem 1 and compute, say, \({\rm\small HOM-CNT}_{C_{2k}}\) in time \(O(n^{d_k-\varepsilon })\) , then we could decide if a digraph with \(m\) edges has a directed \(k\) -cycle in time \(O(m^{d_k-\varepsilon })\) , which is faster (in terms of \(m\) ) than the presently fastest known algorithm for the latter problem.
Another interesting by-product of Theorem 1 is that it can be used (together with a standard application of the color-coding method) to give an algorithm for (directed or undirected) \(k\) -cycle detection in bounded-degeneracy graphs.
Let \(k \ge 6\) . There is an algorithm that detects if a (directed) bounded-degeneracy graph has a (directed) \(k\) -cycle in \(\tilde{O}(n^{d_{\lfloor k/2 \rfloor }})\) time.
As can easily be verified by examining the values of \(c_k\) (hence \(d_k\) ), the algorithm of Theorem 4 is faster than any known algorithm for cycle detection in degenerate graphs for \(7 \le k \le 11\) . If \(\omega = 2\) , it is faster for all \(k \ge 7\) . In any case it is never slower (up to polylogarithmic factors) than the previously fastest algorithm for this problem, given in [4], Theorem 4.2.
Let us give some more details of the proof of Theorem 1. For (di)graphs \(G,H\) , let us denote by \(\hom (H,G)\) the number of homomorphisms from \(H\) to \(G\) . Suppose that we want to compute \(\hom (C_{\ell },G)\) for a given \(d\) -degenerate input graph \(G\) . As is usual when working with degenerate graphs, we approach this task by first finding a degeneracy ordering8 \(v_1,\dots ,v_n\) of \(G\) — i.e., a vertex ordering in which each vertex \(v_i\) has at most \(d\) neighbors succeeding it — and then considering the orientation \(\vec{G}\) of \(G\) in which all edges are oriented forward with respect to this ordering, namely, from \(v_i\) to \(v_j\) for \(\lbrace v_i,v_j\rbrace \in E(G)\) with \(i \lt j\) . Observe that \(\vec{G}\) can be obtained in linear time (in \(|E(G)|=O(dn)\) ), that it is acyclic, and that all of its vertices have out-degree at most \(d\) . Moreover, it is not hard to see that \(\hom (C_\ell ,G) = \sum _{\vec{H}}{\hom (\vec{H},\vec{G})}\) , where \(\vec{H}\) runs over all acyclic orientations of \(C_{\ell }\) . It follows that counting \(C_{\ell }\) -homomorphisms in \(d\) -degenerate graphs reduces to counting homomorphisms of (all) acyclic orientations of \(C_{\ell }\) in directed acyclic graphs (DAGs) of maximum out-degree \(d\) .
As it turns out, there is a particular orientation of \(C_{\ell }\) which is harder, in a sense, than all others; this is the orientation with the maximum number of sources, namely, the orientation where edges are oriented in an alternating fashion (with the exception of one edge in the case that \(\ell\) is odd). We call this the alternating orientation of \(C_{\ell }\) . To establish that this is indeed the “hardest orientation”, we show (roughly speaking) that for every DAG \(\vec{H}\) and for every directed subdivision \(\vec{H}^{\prime }\) of \(\vec{H}\) , counting \(\vec{H}^{\prime }\) -homomorphisms can be reduced to counting \(\vec{H}\) -homomorphisms (in input DAGs of bounded maximum degree). It is easy to see that every acyclic orientation \(\vec{H}\) of \(C_{\ell }\) (with at least two sources) is a directed subdivision of the alternating orientation of \(C_{\ell ^{\prime }}\) for some even \(\ell ^{\prime } \le \ell\) , and that \(\ell ^{\prime } = \ell\) if and only if \(\vec{H}\) itself is alternating.9 It follows that the running time of counting \(C_{\ell }\) -homomorphisms is dominated by the running time of counting homomorphisms of alternating orientations of cycles of even length at most \(\ell\) .
The aforementioned general reduction for directed subdivisions is stated in the following theorem. For technical reasons, the reduction reduces the problem of counting \(\vec{H^{\prime }}\) -homomorphisms to the problem of counting \(\vec{H}\) -homomorphisms in weighted digraphs. We denote by \({\rm\small W-HOM-CNT}_{\vec{H}}\) the weighted analogue of \({\rm\small HOM-CNT}_{\vec{H}}\) ; see Section 3 for the precise definition.
Let \(\vec{H}\) be a DAG and let \(\vec{H^{\prime }}\) be a directed subdivision of \(\vec{H}\) . If \({\rm\small W-HOM-CNT}_{\vec{H}}\) can be solved in time \(O(n^\alpha)\) in \(n\) -vertex weighted degenerate digraphs,10 then \({\rm\small HOM-CNT}_{\vec{H}^{\prime }}\) can be solved in time \(O(n^\alpha)\) in \(n\) -vertex degenerate digraphs.
We believe Theorem 5 to be of independent interest. With this theorem at hand, it remains to give an efficient algorithm which counts homomorphisms of the alternating orientation of \(C_{2k}\) (in DAGs of bounded maximum out-degree) for every \(k \ge 3\) , which is the main step towards proving Theorem 1. Since applying Theorem 5 requires that the algorithm works in the more general weighted setting, we need to modify it accordingly (this modification is straightforward and does not pose additional difficulties).
1.4 Related Work
While the fastest algorithm for \(k\) -cycle detection in directed \(m\) -edge graphs runs in \(\tilde{O}(m^{d_k})\) time, it is worth noting that there are other algorithms expressed in terms of both \(n\) and \(m\) (or \(n\) alone). Indeed, the color-coding method [3] shows that a simple directed or undirected cycle of size \(k\) in a directed or undirected graph can be detected in either \(\tilde{O}(nm)\) time or \(\tilde{O}(n^\omega)\) time. For dense graphs, this is faster than the \(\tilde{O}(m^{d_k})\) time algorithm. Eisenbrand and Grandoni [16] proved that a directed \(C_4\) can be detected in time \(O(m^{2-2/\omega }n^{1/\omega })\) . This algorithm is inferior to the \(\tilde{O}(m^{c_k})\) algorithm for sparse graphs and inferior to the \(O(n^\omega)\) algorithm for dense graphs, but is better than both in some intermediate range.
As for hardness, Lincoln et al. [22] proved conditional lower bounds for \(k\) -cycle detection. Under a widely-believed assumption, \(K_k\) cannot be detected faster than \(O(C(n,k))\) time, where \(C(n,k) = M(n^{\lceil k/3 \rceil },n^{\lfloor k/3 \rfloor },n^{\lceil (k-1)/3 \rceil })\) and where \(M(a,b,c)\) is the fastest known runtime for multiplying an \(a \times b\) by a \(b \times c\) matrix. Assuming this, they proved that detecting a directed \(k\) -cycle in an \(m\) -edge graph requires \(m^{\frac{2\omega k}{3(k+1)}-o(1)}\) time. The same reduction also shows that any combinatorial algorithm for detecting a directed \(k\) -cycle in an \(m\) -edge graph requires \(m^{2-1/\lceil k/2 \rceil - o(1)}\) time, in this case under the suitable hardness hypothesis that any combinatorial algorithm for \(K_k\) -detection requires \(n^{k-o(1)}\) time. This lower bound of \(m^{2-1/\lceil k/2 \rceil - o(1)}\) coincides with the runtime in (1), showing that the algorithms of [4, 22, 37], as well as our combinatorial algorithm for directed-cycle detection given in Section 7, are optimal (for combinatorial algorithms). The same applies to the algorithm given by Part (ii) of Theorem 1.
Paper Overview:. The goal of Section 2 is to introduce the definitions we will use in subsequent sections. Section 3 is devoted to proving Theorem 5. Theorem 1 is proved in Sections 4 and 5: the former deals with Part (ii) of the theorem and the latter with Part (i). Section 6 contains the proofs of Theorems 2 and 4. Finally, in Section 7 we apply our methods to obtain combinatorial algorithms for counting \(C_k\) -homomorphisms and for \(C_k\) -detection in general graphs (both directed and undirected).
2 Preliminaries
Here we introduce the basic definitions to be used throughout the paper. Recall that for (undirected) graphs \(G,H\) , a homomorphism from \(H\) to \(G\) is a map \(\varphi : V(H) \rightarrow V(G)\) such that \(\lbrace \varphi (u),\varphi (v)\rbrace \in E(G)\) whenever \(\lbrace u,v\rbrace \in E(H)\) . Similarly, for digraphs \(\vec{G},\vec{H}\) , a homomorphism from \(\vec{H}\) to \(\vec{G}\) is a map \(\varphi : V(\vec{H}) \rightarrow V(\vec{G})\) such that \((\varphi (u),\varphi (v)) \in E(\vec{G})\) whenever \((u,v) \in E(\vec{H})\) . We will consider (di)graphs with edge weights. Let us define what we mean by the weight of a homomorphism.
Let \(\vec{H}\) be a digraph, let \(\vec{G}\) be a weighted digraph with a weight function \(w_{\vec{G}}: E(\vec{G}) \rightarrow \mathbb {R}_{\ge 0}\) , and let \(\varphi : V(\vec{H}) \rightarrow V(\vec{G})\) be a homomorphism. The weight of \(\varphi\) , denoted \(W(\varphi)\) , is defined as follows:
\begin{equation*} W(\varphi) := \prod _{(u,v) \in E(\vec{H})} w_{\vec{G}}((\varphi (u), \varphi (v))). \end{equation*}
For digraphs \(\vec{G},\vec{H}\) , denote by \(\text{Hom}(\vec{H}, \vec{G})\) the set of all homomorphisms from \(\vec{H}\) to \(\vec{G}\) . For a weight-function \(w_{\vec{G}}\) on the edges of \(\vec{G}\) , define the weighted homomorphism count as follows:As mentioned above, we denote by \({\rm\small W-HOM-CNT}_{\vec{H}}\) the problem of computing \(\hom (\vec{H}, \vec{G}, w_{\vec{G}})\) for a given weighted input digraph \(\vec{G}\) . (Usual — i.e., unweighted — homomorphism counts can be cast in this setting by letting all edge-weights be 1.)
\begin{equation*} \hom (\vec{H}, \vec{G}, w_{\vec{G}}) := \sum _{\varphi \in \text{Hom}(\vec{H}, \vec{G})} W(\varphi). \end{equation*}
Finally, we recall the notion of subdivision for directed graphs:
Let \(\vec{H}\) be a directed graph and write \(E(\vec{H}) = \lbrace e_1, \dots , e_t\rbrace\) . Let \((x_1, \dots , x_t)\) be a sequence of positive integers. The directed \((x_1,\dots ,x_t)\) -subdivision of \(\vec{H}\) is the digraph obtained from \(\vec{H}\) by replacing each edge \(e_i\) with a directed path with \(x_i\) edges, where paths replacing different edges are internally disjoint. We call \((x_1,\dots ,x_t)\) the subdivision sequence. We say that a digraph \(\vec{H}^{\prime }\) is a directed subdivision of \(\vec{H}\) if it is the directed \((x_1,\dots ,x_t)\) -subdivision of \(\vec{H}\) for some \((x_1,\dots ,x_t)\) .
3 Homomorphism Counting and Graph Subdivisions
In this section we prove Theorem 5, showing that counting (weighted) homomorphisms of a directed graph is at least as hard as counting homomorphisms of its directed subdivisions. The main tool in the proof is (a digraph variant of) an extremely useful result of Curticapean, Dell, and Marx [12], stated below as Lemma 3.1. This lemma deals with computing linear combinations of homomorphism counts. For digraphs \(\vec{H_1}, \dots , \vec{H_k}\) and non-zero constants \(c_1, \dots , c_k\) , let \({\rm\small HOM-CNT}_{c_1 \vec{H_1} + \dots + c_k \vec{H_k}}\) be the problem of computing \(c_1 \cdot \hom (\vec{H_1},\vec{G}) + \dots + c_k \cdot \hom (\vec{H_k},\vec{G})\) for an input digraph \(\vec{G}\) . Lemma 3.1 states that solving \({\rm\small HOM-CNT}_{c_1 \vec{H_1} + \dots + c_k \vec{H_k}}\) is essentially equivalent to solving \({\rm\small HOM-CNT}_{\vec{H_i}}\) for all \(1 \le i \le k\) .
Let \(\vec{H_1}, \dots , \vec{H_k}\) be pairwise non-isomorphic digraphs and let \(c_1, \dots , c_k\) be non-zero constants. Then \({\rm\small HOM-CNT}_{c_1 \vec{H_1} + \dots + c_k \vec{H_k}}\) can be solved in time \(O(n^\alpha)\) in \(n\) -vertex degenerate digraphs if and only if \({\rm\small HOM-CNT}_{\vec{H_i}}\) can be solved in time \(O(n^\alpha)\) in \(n\) -vertex degenerate digraphs for all \(1 \le i \le k\) .
The undirected version of Lemma 3.1 was proved in [12], and subsequently used in [6] to study homomorphism-counting in degenerate graphs. The proof uses tensor products and a result of Erdős, Lovász, and Spencer [17] regarding linear independence of homomorphism counts. Since the proof of the directed variant (namely, Lemma 3.1) is essentially the same as that of the undirected one, we postpone it to the appendix.
We are now in a position to prove Theorem 5.
Let \(\vec{H}\) be a fixed digraph and write \(E(\vec{H}) = \lbrace e_1, \dots , e_t\rbrace\) . We assume that \({\rm\small W-HOM-CNT}_{\vec{H}}\) can be solved in time \(O(n^\alpha)\) (for some \(\alpha \ge 1\) ) in \(n\) -vertex weighted degenerate digraphs. For an integer \(p \ge 1\) , we denote by \(SD_{\vec{H}, p}\) the set of all directed subdivisions of \(\vec{H}\) where each edge is replaced by a directed path of length at most \(p\) , and the original vertices (i.e., the vertices of \(\vec{H}\) ) are labeled as in \(\vec{H}\) . We will prove the theorem simultaneously for all digraphs \(\vec{H}^{\prime } \in SD_{\vec{H}, p}\) (this is clearly sufficient as \(p\) was arbitrary). Note that every digraph in \(SD_{\vec{H}, p}\) is defined by a unique subdivision sequence \(x=(x_1, \dots , x_t) \in [p]^t\) . Our goal is to show that \({\rm\small HOM-CNT}_{\vec{H}^{\prime }}\) can be solved in time \(O(n^\alpha)\) in bounded-degeneracy digraphs for every digraph \(\vec{H}^{\prime } \in SD_{\vec{H}, p}\) . To this end, we will show that a certain linear combination of \(\hom (\vec{H}^{\prime }, \vec{G})\) , where \(\vec{H}^{\prime }\) runs over all digraphs \(\vec{H}^{\prime } \in SD_{\vec{H}, p}\) , can be computed in time \(O(n^\alpha)\) . We will then apply Lemma 3.1 to complete the proof.
Let \(\vec{G}\) be an \(n\) -vertex digraph where all out-degrees are at most \(\kappa = O(1)\) . We construct a weighted digraph \(\vec{F}\) , that will have the same vertex set as \(\vec{G}\) , as follows. For every pair \(x,y \in V(\vec{G})\) and every \(\ell \in [p]\) , let \(w_\ell (x,y)\) denote the number of directed walks of length exactly \(\ell\) from \(x\) to \(y\) in \(\vec{G}\) . LetIf \(w(x,y) \gt 0\) , then the graph \(\vec{F}\) will have the edge \((x,y)\) with weight \(w(x,y)\) , and otherwise (i.e., if \(w(x,y) = 0\) ), it will not have the edge \((x,y)\) . Namely, the weight function of \(\vec{F}\) is \(w_{\vec{F}}(u,v) = w(u,v)\) . We observe that the graph \(\vec{F}\) can be constructed in \(O(n)\) time. Indeed, for each \(x \in V(\vec{G})\) , there are at most \(\kappa ^\ell\) vertices \(y\) such that there is a directed walk of length \(\ell\) from \(x\) to \(y\) , as all out-degrees in \(\vec{G}\) are at most \(\kappa\) . Thus, for each \(x \in V(\vec{G})\) , it takes constant time to compute \(w(x,y)\) for all \(y\) such that \(w(x,y) \gt 0\) . Moreover, we observe that the out-degree of every vertex in \(\vec{F}\) is constant.
\begin{equation*} w(x,y) = \sum _{\ell =1}^p w_\ell (x,y). \end{equation*}
Now, let \(\varphi : V(\vec{H}) \rightarrow V(\vec{F})\) be a homomorphism. We have thatand soWrite \(e_i = (u_i,v_i)\) for \(1 \le i \le t\) . Crucially, observe that for a digraph \(\vec{H}^{\prime } \in SD_{\vec{H}, p}\) with subdivision sequence \((x_1, \dots , x_t) \in [p]^t\) , a homomorphism \(\psi : V(\vec{H}^{\prime }) \rightarrow V(\vec{G})\) corresponds to a homomorphism \(\varphi : V(\vec{H}) \rightarrow V(\vec{F})\) such that \(\varphi (v) = \psi (v)\) for every \(v \in V(\vec{H})\) , together with a directed walk \(\psi (u_i) \rightarrow \psi (s_{e_i}^1) \rightarrow \dots \rightarrow \psi (s_{e_i}^{x_i-1}) \rightarrow \psi (v_i)\) of length \(x_i\) in \(\vec{G}\) (where \(\lbrace s_{e_i}^j\rbrace \in V(\vec{H}^{\prime })\) are the subdivision vertices of the path corresponding to the edge \(e_i\) ), for every \(1 \le i \le t\) . Since for each \(i\) the number of such walks (in \(\vec{G}\) ) is \(w_{x_i}(\varphi (u_i), \varphi (v_i))\) , we have thatRecalling that every \(\vec{H}^{\prime } \in SD_{\vec{H}, p}\) is defined by a unique sequence \((x_1, \dots , x_t) \in [p]^t\) , by combining (3) and (4), we get
\begin{equation*} W(\varphi) = \prod _{(u,v) \in E(\vec{H})} w_{\vec{F}}((\varphi (u), \varphi (v))) = \prod _{(u,v) \in E(\vec{H})} (w_1(\varphi (u), \varphi (v)) + \dots + w_p(\varphi (u), \varphi (v))), \end{equation*}
\begin{equation} \hom (\vec{H}, \vec{F}, w_{\vec{F}}) = \sum _{\varphi \in \text{Hom}(\vec{H}, \vec{F})} \, \prod _{(u,v) \in E(\vec{H})} (w_1(\varphi (u), \varphi (v)) + \dots + w_p(\varphi (u), \varphi (v))). \end{equation}
(3)
\begin{equation} \hom (\vec{H}^{\prime }, \vec{G}) = \sum _{\varphi \in \text{Hom}(\vec{H}, \vec{F})} \, \prod _{e_i = (u_i, v_i) \in E(\vec{H})} w_{x_i}(\varphi (u_i), \varphi (v_i)). \end{equation}
(4)
\begin{align} \sum _{\vec{H}^{\prime } \in SD_{\vec{H}, p}} \hom (\vec{H}^{\prime }, \vec{G}) &= \sum _{\varphi \in \text{Hom}(\vec{H}, \vec{F})} \, \sum _{(x_1, \dots , x_t) \in [p]^t} \, \prod _{e_i = (u_i, v_i) \in E(\vec{H})} w_{x_i}(\varphi (u_i), \varphi (v_i)) \nonumber \nonumber\\ &= \sum _{\varphi \in \text{Hom}(\vec{H}, \vec{F})} \, \prod _{e_i = (u_i, v_i) \in E(\vec{H})} (w_1(\varphi (u_i), \varphi (v_i)) + \dots + w_p(\varphi (u_i), \varphi (v_i))) \\ &= \hom (\vec{H}, \vec{F}, w_{\vec{F}}). \nonumber \nonumber \end{align}
(5)
We were able to express \(\hom (\vec{H}, \vec{F}, w_{\vec{F}})\) as a linear combination of \(\hom (\vec{H}^{\prime }, \vec{G})\) (with \(\vec{H}^{\prime } \in SD_{\vec{H}, p}\) ), where all of the coefficients are equal to 1. We observe that for isomorphic graphs \(\vec{H}^{\prime }, \vec{H}^{\prime \prime } \in SD_{\vec{H}, p}\) , \(\hom (\vec{H}^{\prime }, \vec{G}) = \hom (\vec{H}^{\prime \prime }, \vec{G})\) , and thus we can “combine like terms” in (5). Namely, let \(\vec{H_1}, \dots , \vec{H_k}\) be an enumeration of all graphs in \(SD_{\vec{H}, p}\) up to isomorphism (that is, \(\vec{H_1}, \dots , \vec{H_k}\) are pairwise non-isomorphic). Then, there exist positive constants \(c_1, \dots , c_k \gt 0\) such that
\begin{equation} \hom (\vec{H}, \vec{F}, w_{\vec{F}}) = \sum _{i=1}^k c_i \cdot \hom (\vec{H_i}, \vec{G}). \end{equation}
(6)
As \(\vec{F}\) is a weighted digraph where all out-degrees are constant, \(\hom (\vec{H}, \vec{F}, w_{\vec{F}})\) can be computed in time \(O(n^\alpha)\) , by our assumption. Combined with (6), we get that \({\rm\small HOM-CNT}_{c_1 \vec{H_1} + \dots + c_k \vec{H_k}}\) can be solved in time \(O(n^\alpha)\) in bounded-degeneracy digraphs.
By Lemma 3.1, \({\rm\small HOM-CNT}_{\vec{H_i}}\) can be solved in time \(O(n^\alpha)\) in degenerate digraphs, for each \(1 \le i \le k\) . This completes the proof, since every digraph \(\vec{H}^{\prime } \in SD_{\vec{H}, p}\) is isomorphic to one of \(\vec{H_1}, \dots , \vec{H_k}\) .□
4 Counting Homomorphisms of Cycles: A Combinatorial Algorithm
In this section we prove the second part of Theorem 1. We prefer to prove this part first as it is technically simpler than the first part. Let \(P_r\) denote the oriented path with vertices \(1,\dots ,2r+1\) (so \(e(P_r) = 2r\) ), and where the vertices \(1, 3,\ldots ,2r+1\) are sinks and the vertices \(2, 4,\ldots ,2r\) are sources.
There is an algorithm which, given integers \(r,\Delta \ge 1\) and a weighted degenerate \(n\) -vertex input DAG \(\vec{G}\) , computes the following:
(1)
For every \(x,y \in V(\vec{G})\) , the total weight \(N_{r,\Delta }(x,y)\) of homomorphisms \(\varphi : P_r \rightarrow \vec{G}\) such that \(\varphi (1) = x\) , \(\varphi (2r+1) = y\) , and \(\mbox{in-deg}(\varphi (t)) \le \Delta\) for every sink \(t\) of \(P_r\) other than \(1,2r+1\) .
(2)
For every \(x,y \in V(\vec{G})\) with \(\mbox{in-deg}(x) \gt \Delta\) and for every function \(f : \lbrace 3,5,\dots ,2r+1\rbrace \rightarrow \lbrace \mbox{low, high}\rbrace\) , the total weight \(M_{r,\Delta ,f}(x,y)\) of homomorphisms \(\varphi : P_r \rightarrow \vec{G}\) such that \(\varphi (1) = x\) and \(\varphi (2r+1) = y\) , and such that for every \(t \in \lbrace 3,5,\dots ,2r+1\rbrace\) it holds that \(\mbox{in-deg}(\varphi (t)) \le \Delta\) if \(f(t) = \mbox{low}\) and \(\mbox{in-deg}(\varphi (t)) \gt \Delta\) if \(f(t) = \mbox{high}\) .
The computation for Item 1 takes time \(\tilde{O}(n\Delta ^{r-1})\) and the computation for Item 2 takes time \(\tilde{O}(n^2/\Delta)\) . Furthermore, the number of pairs \(x,y\) with \(N_{r,\Delta }(x,y) \gt 0\) is \(O(n\Delta ^{r-1})\) .
We will use a hash map to store the counts \(N_{r,\Delta }(x,y)\) and \(M_{r,\Delta ,f}(x,y)\) (for all pairs \((x,y)\) for which the counts are non-zero). Using such a hash map is the reason for the logarithmic factors implicit in the \(\tilde{O}\) -notation in the runtime bound, since the hash-map operations require time \(\tilde{O}(1)\) . This logarithmic factor can be avoided at the cost of allowing randomized algorithms (in which case we should speak of expected runtime).
Let \(w_{\vec{G}}\) be the weight function of \(\vec{G}\) . We start with Item 1. Here we enumerate all homomorphisms \(\varphi : P_r \rightarrow \vec{G}\) such that \(\mbox{in-deg}(\varphi (t)) \le \Delta\) for every sink \(t \in V(P_r)\) other than \(1,2r+1\) . Enumerating all such homomorphisms is clearly sufficient to produce the desired counts. To choose such a homomorphism \(\varphi\) , we first choose \(\varphi (2)\) , for which there are \(n\) choices. Having chosen \(\varphi (2)\) , we have \(O(1)\) choices for \(\varphi (1)\) and \(\varphi (3)\) , where we only go over the choices for \(\varphi (3)\) which satisfy \(\mbox{in-deg}(\varphi (3)) \le \Delta\) . Having chosen \(\varphi (3)\) , there are at most \(\Delta\) choices for \(\varphi (4)\) , since \(\varphi (4)\) must be an in-neighbor of \(\varphi (3)\) . Continuing in this fashion, we see that there are \(O(1)\) choices for each of the vertices \(\varphi (1),\varphi (3),\dots ,\varphi (2r+1)\) and at most \(\Delta\) choices for each of the vertices \(\varphi (4),\varphi (6),\dots ,\varphi (2r)\) . Hence, the total number of choices is \(n\Delta ^{r-1}\) . In particular, the number of pairs \(x,y\) with \(N_{r,\Delta }(x,y) \gt 0\) (namely, which are the endpoints in such a homomorphism) is at most \(O(n\Delta ^{r-1})\) , as required.
We now establish Item 2, whose proof is by induction on \(r\) . First, let us handle the base case \(r=1\) . Observe that \(P_1\) is just the two-edge oriented path with the middle vertex 2 being a source and the two endpoints 1,3 being sinks. We can enumerate all homomorphisms \(\varphi\) from \(P_1\) to \(\vec{G}\) in time \(O(n)\) , by going over all (at most \(n\) ) choices for \(\varphi (2)\) and for each such choice, going over all (at most \(O(1)\) ) pairs of out-neighbors of \(\varphi (2)\) . Enumerating all homomorphisms of \(P_1\) is clearly enough to compute the desired counts.
We now proceed to the induction step. Assume, by the induction hypothesis, that we have already computed the desired counts for \(P_{r-1}\) . To achieve this for \(P_r\) , go over all choices for vertices \(x,u \in V(\vec{G})\) such that \(\mbox{in-deg}(x) \gt \Delta\) . The number of such choices is at most \(O(n^2/\Delta)\) , since there are at most \(n\) choices for \(u\) and at most \(O(n/\Delta)\) choices for \(x\) . Now go over all pairs \(v,y\) of out-neighbors of \(u\) . For each such pair \(v,y\) , and for each function \(g : \lbrace 3,5,\dots ,2r-1\rbrace \rightarrow \lbrace \mbox{low, high}\rbrace\) , we have already computed the total weight \(M_{r-1,\Delta ,g}(x,v)\) of homomorphisms \(\psi : P_{r-1} \rightarrow \vec{G}\) such that \(\psi (1) = x\) and \(\psi (2r-1) = v\) , and such that for every \(t \in \lbrace 3,5,\dots ,2r-1\rbrace\) it holds that \(\mbox{in-deg}(\varphi (t)) \le \Delta\) if \(g(t) = \mbox{low}\) and \(\mbox{in-deg}(\varphi (t)) \gt \Delta\) if \(g(t) = \mbox{high}\) . Now, for each such \(\psi\) and \(g\) , the map \(\varphi : V(P_r) \rightarrow V(\vec{G})\) which agrees with \(\psi\) on \(P_r[\lbrace 1,\dots ,2r-1\rbrace ] = P_{r-1}\) and satisfies \(\varphi (2r) = u\) and \(\varphi (2r+1) = y\) , is a homomorphism from \(P_r\) to \(\vec{G}\) satisfying \(\varphi (1) = x\) and \(\varphi (2r+1) = y\) . Furthermore, the function \(f : \lbrace 3,5,\dots ,2r+1\rbrace \rightarrow \lbrace \mbox{low, high}\rbrace\) corresponding to \(\varphi\) is simply the function which agrees with \(g\) on \(\lbrace 3,5,\dots ,2r-1\rbrace\) and satisfies \(f(2r+1) = \mbox{low}\) if \(\mbox{in-deg}(y) \le \Delta\) and \(f(2r+1) = \mbox{high}\) if \(\mbox{in-deg}(y) \gt \Delta\) . Hence, multiplying the weight of \(\psi\) by \(w(u,v) \cdot w(u,y)\) and summing over all such \(\psi\) , we obtain the desired count for the pair \(x,y\) .□
Let \(\vec{C}_{2\ell }\) denote the alternating orientation of \(C_{2\ell }\) .
For every \(\ell \ge 2\) , there is an algorithm which, given a weighted degenerate \(n\) -vertex input DAG \(\vec{G}\) , computes the total weight of homomorphisms from \(\vec{C}_{2\ell }\) to \(\vec{G}\) in time \(\tilde{O}(n^{2 - 1/\lceil \ell /2 \rceil })\) .
Set \(\Delta := n^{1/\lceil \ell /2 \rceil }\) . Denote the sinks of \(\vec{C}_{2\ell }\) by \(t_1,\dots ,t_{\ell }\) . In order to compute \(\hom (\vec{C}_{2\ell },\vec{G},w_{\vec{G}})\) , we will compute, for every function \(g : \lbrace t_1,\dots ,t_{\ell }\rbrace \rightarrow \lbrace \mbox{low, high}\rbrace\) , the total weight \(\hom _g\) of homomorphisms \(\varphi : \vec{C}_{2\ell } \rightarrow \vec{G}\) such that \(\mbox{in-deg}(\varphi (t_i)) \le \Delta\) if \(g(t_i) = \mbox{low}\) and \(\mbox{in-deg}(\varphi (t_i)) \gt \Delta\) if \(g(t_i) = \mbox{high}\) (for every \(1 \le i \le \ell\) ). Clearly, \(\hom (\vec{C}_{2\ell },\vec{G},w_{\vec{G}}) = \sum _{g}{\hom _g}\) . We consider two cases. Suppose first that \(g(t_i) = \mbox{low}\) for every \(1 \le i \le \ell\) . It is easy to see that \(\vec{C}_{2\ell }\) consists of a copy of \(P_{\lfloor \ell /2 \rfloor }\) and a copy of \(P_{\lceil \ell /2 \rceil }\) , glued together at their endpoints. It is now easy to see that for this particular \(g\) , one haswhere \(N_{r,\Delta }(x,y)\) is as defined in Item 1 of Lemma 4.1. Since we can compute the counts \(N_{\lfloor \ell /2 \rfloor ,\Delta }(x,y), N_{\lceil \ell /2 \rceil ,\Delta }(x,y)\) for all pairs of vertices \(x,y \in V(G)\) (simultaneously) in time \(\tilde{O}(n \Delta ^{\lceil \ell /2 \rceil -1})\) , and since the total number of pairs for which these counts are non-zero is \(O(n \Delta ^{\lceil \ell /2 \rceil -1})\) , the above sum can be computed in time \(\tilde{O}(n \Delta ^{\lceil \ell /2 \rceil -1}) = \tilde{O}(n^{2 - 1/\lceil \ell /2 \rceil })\) , as required.
\begin{equation*} \hom _g = \sum _{{c}x,y \in V(\vec{G}): \\ \mbox{in-deg}(x) \le \Delta \\ \mbox{in-deg}(y) \le \Delta } {N_{\lfloor \ell /2 \rfloor ,\Delta }(x,y) \cdot N_{\lceil \ell /2 \rceil ,\Delta }(x,y)}, \end{equation*}
Suppose now that \(g(t_i) = \mbox{high}\) for some \(1 \le i \le \ell\) . We proceed similarly to the previous case. Decompose \(\vec{C}_{2\ell }\) into a copy \(P\) of \(P_{\lfloor \ell /2 \rfloor }\) and a copy \(P^{\prime }\) of \(P_{\lceil \ell /2 \rceil }\) , such that \(t_i\) is an endpoint of both of these paths. Let \(f,f^{\prime }\) be the “low/high signatures” corresponding the paths \(P,P^{\prime }\) , respectively. Again, it is not hard to see thatBy Item 2 of Lemma 4.1, one can compute \(M_{\lfloor \ell /2 \rfloor ,\Delta ,f}(x,y)\) and \(M_{\lceil \ell /2 \rceil ,\Delta ,f^{\prime }}(x,y)\) for all pairs \(x,y \in V(\vec{G})\) with \(\mbox{in-deg}(x) \gt \Delta\) in time \(\tilde{O}(n^2/\Delta)\) . Furthermore, the number of such pairs \(x,y\) is \(O(n^2/\Delta)\) , because there are \(O(n/\Delta)\) choices for \(x\) . We conclude that the above sum can be computed in time \(\tilde{O}(n^2/\Delta) = \tilde{O}(n^{2 - 1/\lceil \ell /2 \rceil })\) , as required. This completes the proof of the theorem.□
\begin{equation*} \hom _g = \sum _{{c}x,y \in V(\vec{G}): \\ \mbox{in-deg}(x) \gt \Delta } {M_{\lfloor \ell /2 \rfloor ,\Delta ,f}(x,y) \cdot M_{\lceil \ell /2 \rceil ,\Delta ,f^{\prime }}(x,y) }. \end{equation*}
Let \(G\) be an \(n\) -vertex degenerate graph and consider the DAG \(\vec{G}\) obtained (in linear time) from a degenerate ordering of \(G\) . We need to compute \(\hom (C_{2k},G)\) in \(O(n^{2-1/\lceil k/2 \rceil })\) time (the proof for \(\hom (C_{2k+1},G)\) is analogous). Recall that this amounts to computing \(\hom (\vec{H},\vec{G})\) for every acyclic orientation \(\vec{H}\) of \(C_{2k}\) . So, consider some such \(\vec{H}\) . If \(\vec{H}\) has exactly one source, then we can enumerate all homomorphisms from \(\vec{H}\) to \(\vec{G}\) — and in particular compute \(\hom (\vec{H},\vec{G})\) — in linear time11; see, e.g., [10]. Suppose then that \(\vec{H}\) has at least two sources, and recall that \(\vec{H}\) is a directed subdivision of the alternating orientation \(\vec{C}_{2\ell }\) of \(C_{2\ell }\) for some \(2 \le \ell \le k\) . It now follows from Theorem 5 that it suffices to show that \({\rm\small W-HOM-CNT}_{\vec{C}_{2\ell }}\) can be solved in time \(\tilde{O}(n^{2-1/\lceil k/2 \rceil })\) in weighted degenerate DAGs, which is precisely the statement of Theorem 6.□
5 Counting Homomorphisms of Cycles: Using Matrix Multiplication
In this section we prove the first part of Theorem 1. We begin with describing an algorithm for counting weighted homomorphisms of alternating orientations of cycles. As mentioned in the introduction, our algorithm is inspired by the algorithm of Yuster and Zwick [38] for finding a directed \(k\) -cycle in a (general) directed graph but bears several significant differences and tweaks. As in [38], our approach for enumerating (weighted) homomorphisms is by classifying them into a polylogarithmic number of classes, according to the in-degrees of the images of the (sink) vertices of the \(\vec{C}_{2k}\) (the alternating orientation of \(C_{2k}\) ).
Let \(k \ge 2\) and let \(\vec{C}_{2k}\) be the alternating orientation of \(C_{2k}\) . Then, the \({\rm\small W-HOM-CNT}_{\vec{C}_{2k}}\) problem can be solved in degenerate digraphs in time \(\tilde{O}(n^{c_k})\) .
Let \(\vec{G}\) be an \(n\) -vertex degenerate weighted digraph with weight function \(w_{\vec{G}}\) . Let us denote by \(u_0, \dots , u_{k-1}\) the source vertices of \(\vec{C}_{2k}\) , and by \(s_0, \dots , s_{k-1}\) the sink vertices of \(\vec{C}_{2k}\) , such that \((u_i,s_i), (u_i, s_{i-1})\) are edges for all \(i\) (here and in what follows, indices are taken modulo \(k\) ).
We call a triple of vertices \(x,y,z \in V(\vec{G})\) such that \((z,x), (z,y)\) are edges a cherry. We start by observing that in \(O(n)\) time one can enumerate all the cherries in \(\vec{G}\) , as the out-degree of every vertex in \(\vec{G}\) is bounded. In particular, for every pair of vertices \(x,y \in V(\vec{G})\) , we will store in a hash table, denoted \(\mathcal {HM}\) , the sum of weight products of cherries with endpoints \(x,y\) (i.e., the sum of \(w_{\vec{G}}(z,x) \cdot w_{\vec{G}}(z,y)\) over all vertices \(z\) such that \((z,x), (z,y)\) are edges). This number will be denoted by \(\mathcal {HM}[x,y]\) . Note that there are only \(O(n)\) pairs \((x,y)\) for which \(\mathcal {HM}[x,y] \gt 0\) .
Let us partition the vertices of \(\vec{G}\) into \(\log n\) degree classes, as follows. For every \(0 \le i \lt \log n\) , letWe refer to a degree class \(W_j\) by its index \(j\) , for simplicity of notation. Clearly, we have that \(|W_i| = O(n/2^i)\) (recall that \(\vec{G}\) has \(O(n)\) edges).
\begin{equation*} W_i = \lbrace v \in V(\vec{G}) \, | \, 2^i \le \text{in-deg}(v) \lt 2^{i+1}\rbrace . \end{equation*}
Our approach for enumerating (weighted) homomorphisms from \(\vec{C}_{2k}\) to \(\vec{G}\) will be classifying them into \(O(\log ^k n)\) classes, according to the degree classes of the images of \(s_0, \dots , s_{k-1}\) .
Now, let us fix a tuple of degree classes \(f = (f_0, \dots , f_{k-1})\) with \(f_r \in \lbrace 0, \dots , \log n\rbrace\) . Our goal is to compute the weighted homomorphism count of homomorphisms \(\varphi : \vec{C}_{2k} \rightarrow \vec{G}\) such that \(\varphi (s_j) \in W_{f_j}\) for all \(0 \le j \lt k\) (i.e., \(\varphi (s_j)\) has in-degree roughly \(2^{f_j}\) ). For \(i,j \in \lbrace 0, \dots , \log n\rbrace\) , we denote by \(A_{i,j}\) the \(|W_i| \times |W_j|\) matrix such that for every \(x \in W_i, y \in W_j\) , \(A_{i,j}(x,y) = \mathcal {HM}[x,y]\) . We will sometimes represent \(A_{i,j}\) as a sparse matrix, e.g., using adjacency lists. Note that \(A_{i,j}\) has only \(O(n)\) non-zero entries, since there are in total only \(O(n)\) pairs \(x,y \in V(\vec{G})\) for which \(\mathcal {HM}[x,y] \gt 0\) . Hence, a sparse representation of \(A_{i,j}\) can be obtained in time \(O(n)\) .
Now, for \(p,q \in \lbrace 0, \dots , k-1\rbrace\) , we letObserve that for a given \(p \in \lbrace 0, \dots , k-1\rbrace\) , \(A_{f_p, f_{p+1}}(x,y)\) corresponds to the number of homomorphisms \(\varphi\) of \(\vec{C}_{2k}[\lbrace s_p, u_{p+1}, s_{p+1} \rbrace ]\) such that \(\varphi (s_p) = x\) , \(\varphi (s_{p+1}) = y\) . We thus get that \(B^f_{p,q}(x,y)\) corresponds to the number of homomorphisms \(\varphi\) of \(\vec{C}_{2k}[\lbrace s_p, u_{p+1}, s_{p+1}, \dots , u_q, s_q \rbrace ]\) such that \(\varphi (s_p) = x\) , \(\varphi (s_q) = y\) , and \(\varphi (s_j) \in W_{f_j}\) for all \(p \lt j \lt q\) . (This is a variation of the standard way of counting \(r\) -walks in a digraph using the \(r^{\text{th}}\) power of its adjacency matrix.) Now, one can observe that the weighted homomorphism count of homomorphisms \(\varphi : \vec{C}_{2k} \rightarrow \vec{G}\) such that \(\varphi (s_j) \in W_{f_j}\) for \(0 \le j \lt k\) can be obtained in the following way. We consider the matrix chain product \(B^f_{0,k} = A_{f_0, f_1} A_{f_1, f_2} \cdots A_{f_{k-2}, f_{k-1}} A_{f_{k-1}, f_0}\) . The sum of the diagonal entries of \(B^f_{0,k}\) (i.e., \(\text{trace}(B^f_{0,k})\) ) gives the desired weighted homomorphism count. In order to compute \(\text{trace}(B^f_{0,k})\) efficiently, our approach will be to pick a particular pair \(i, j \in \lbrace 0, \dots , k-1\rbrace\) , compute \(B^f_{i,j}\) and \(B^f_{j,i}\) , and then use them to compute \(\text{trace}(B^f_{i,j} B^f_{j,i}) = \text{trace}(B^f_{0,k})\) . Our choice of \(i,j\) will be such that the running time is minimized.
\begin{equation*} B^f_{p,q} = A_{f_p, f_{p+1}} A_{f_{p+1}, f_{p+2}} \cdots A_{f_{q-1}, f_q}. \end{equation*}
It will be more convenient to express the degrees in terms of the number of edges in \(\vec{G}\) , which is \(O(n)\) . Specifically, when considering a \(k\) -tuple of degree classes \((f_0, \dots , f_{k-1})\) with \(f_r \in \lbrace 0, \dots , \log n\rbrace\) , we will let \(n^{d_j} = 2^{f_j}\) , and so \(d_j = f_j / \log n\) . Notice that \(0 \le d_j \le 1\) , and that \(|W_j| = O(n^{1-d_j})\) .
For a fixed tuple of degree classes \(d = (d_0, \dots , d_{k-1})\) , let \(P^d_{i,j}\) be the minimum such that \(B^d_{i,j}\) can be computed in time \(O(n^{P^d_{i,j}})\) . We observe that this also gives an upper bound on the number of non-zero entries in \(B^d_{i,j}\) . The matrix \(B^d_{i,j}\) can be computed in three ways, as follows:
(1)
Compute a sparse representation of \(B^d_{i,j-1}\) . Then, for every entry \((x,y) \in W_{f_i} \times W_{f_{j-1}}\) of \(B^d_{i,j-1}\) , traverse all of the in-neighbors of \(y\) , and denote by \(S_y\) the set of their out-neighbors in \(W_{f_j}\) (i.e., \(w \in S_y\) if and only if \(w \in W_{f_j}\) and there exists \(u \in V(\vec{G})\) such that \((u,y),(u,w) \in E(\vec{G})\) ). Now, for each \(w \in S_y\) , update \(B^d_{i,j}(x,w) = B^d_{i,j}(x,w) + B^d_{i,j-1}(x,y) \cdot \mathcal {HM}[y,w]\) . The computation of \(B^d_{i,j-1}\) takes \(O(n^{P^d_{i,j-1}})\) time. Now, each \(y \in W_{f_{j-1}}\) has at most \(O(n^{d_{j-1}})\) in-neighbors, with each having \(O(1)\) out-neighbors (i.e., \(|S_y|=O(n^{d_{j-1}})\) for each \(y \in W_{f_{j-1}}\) ). Therefore, a sparse representation of \(B^d_{i,j}\) can be computed in time \(O(n^{P^d_{i,j-1} + d_{j-1}})\) (as the size of a sparse representation of \(B^d_{i,j-1}\) is \(O(n^{P^d_{i,j-1}})\) ).
(2)
Similar to the above, but reversing the roles of \(j-1\) and \(i\) : Compute a sparse representation of \(B^d_{i+1,j}\) . Then, for every entry \((x,y) \in W_{f_{i+1}} \times W_{f_j}\) of \(B^d_{i+1,j}\) , traverse all of the in-neighbors of \(x\) , and denote by \(S_x\) the set of their out-neighbors in \(W_{f_i}\) (i.e., \(w \in S_x\) if and only if \(w \in W_{f_i}\) and there exists \(u \in V(\vec{G})\) such that \((u,x),(u,w) \in E(\vec{G})\) ). Now, for each \(w \in S_x\) , update \(B^d_{i,j}(w,y) = B^d_{i,j}(w,y) + \mathcal {HM}[w,x] \cdot B^d_{i+1,j}(x,y)\) . The computation of \(B^d_{i+1,j}\) takes \(O(n^{P^d_{i+1,j}})\) time. Now, each \(x \in W_{f_{i+1}}\) has at most \(O(n^{d_{i+1}})\) in-neighbors, with each having \(O(1)\) out-neighbors (i.e., \(|S_x|=O(n^{d_{i+1}})\) for each \(x \in W_{f_{i+1}}\) ). Therefore, a sparse representation of \(B^d_{i,j}\) can be computed in time \(O(n^{P^d_{i+1,j} + d_{i+1}})\) (as the size of a sparse representation of \(B^d_{i+1,j}\) is \(O(n^{P^d_{i+1,j}})\) ).
(3)
For some \(i \lt r \lt j\) , compute \(B^d_{i,r}\) and \(B^d_{r,j}\) . Then, compute their product to obtain \(B^d_{i,j}\) . It takes \(O(n^{P^d_{i,r}} + n^{1-d_i}n^{1-d_r})\) time to compute the (non-sparse) matrix representation of \(B^d_{i,r}\) , and \(O(n^{P^d_{r,j}} + n^{1-d_r}n^{1-d_j})\) time to compute the (non-sparse) matrix representation of \(B^d_{r,j}\) . Finally, it takes \(O(n^{M(1-d_i, 1-d_r, 1-d_j)})\) time to compute their product, where \(M(a,b,c)\) is the smallest \(g\) such that one can multiply an \(n^a \times n^b\) by an \(n^b \times n^c\) matrix in time \(O(n^g)\) . It is not difficult to see (see, e.g., [20]), that \(M(a,b,c) \le a+b+c - (3-\omega)\min \lbrace a,b,c\rbrace\) .
Now, the exponent of the running time in Item 1 is recursively bounded as \(P^d_{i,j} \le P^d_{i,j-1} + d_{j-1}\) . Similarly, for Item 2 we have the bound \(P^d_{i,j} \le P^d_{i+1,j} + d_{i+1}\) . On the other hand, the running time of Item 3 is bounded by
\begin{equation*} P^d_{i,j} \le \min _{i \lt r \lt j} \max \left\lbrace P^d_{i,r}, P^d_{r,j}, M(1-d_i, 1-d_r, 1-d_j)\right\rbrace . \end{equation*}
We observe that \(P^d_{i,i+1} = 1\) as a sparse representation of \(B^d_{i,i+1} = A_{f_{i},f_{i+1}}\) can be obtained in time \(O(n)\) . To summarize, we have the following inductive definition:
\begin{equation} \begin{gathered}P^d_{i,i+1} = 1 \\ P^d_{i,j} = \min \left\lbrace P^d_{i,j-1} + d_{j-1}, P^d_{i+1,j} + d_{i+1}\right., \min _{i \lt r \lt j} \max \left.\left\lbrace P^d_{i,r}, P^d_{r,j}, M(1-d_i, 1-d_r, 1-d_j)\right\rbrace \right\rbrace \end{gathered} \end{equation}
(7)
Now, given sparse representations of \(B^d_{i,j}\) and \(B^d_{j,i}\) for some \(i, j \in \lbrace 0, \dots , k-1\rbrace\) , we can compute \(\text{trace}(B^d_{i,j} B^d_{j,i})\) in time of the number of non-zero entries in \(B^d_{i,j}\) and \(B^d_{j,i}\) , which is \(O(n^{P^d_{i,j}} + n^{P^d_{j,i}})\) . This is true as \(\text{trace}(B^d_{i,j} B^d_{j,i}) = \sum _{p,q} (B^d_{i,j})_{p,q} \cdot (B^d_{j,i})_{q,p}\) , and so we can exploit the sparse representations of \(B^d_{i,j}\) and \(B^d_{j,i}\) .12 We note that if \(B^d_{i,j}\) and \(B^d_{j,i}\) are given in (non-sparse) matrix representations, we can always convert them into spare representations, as the running time of this conversion is dominated by the time it took to create those matrices. Finally, recall that \(\text{trace}(B^d_{i,j} B^d_{j,i})\) corresponds to the weighted homomorphism count for the current degree class \(d\) .
For \(d = (d_0, \dots , d_{k-1})\) , define
\begin{equation} C_k(d_0, \dots , d_{k-1}) = \min _{0 \le i \lt j \le k-1} \max \left\lbrace P^d_{i,j}, P^d_{j,i}\right\rbrace . \end{equation}
(8)
Now, given \(d = (d_0, \dots , d_{k-1})\) , the algorithm solves a dynamic programming problem of constant size, based on (7) and (8), and determines the optimal way of computing the weighted homomorphism count of the current degree class. This is then repeated for all degree classes.
Therefore, the running time for computing the weighted homomorphism count for a degree class \(d\) is \(O(n^{C_k(d_0, \dots , d_{k-1})})\) , and so the total running time is \(\tilde{O}(n^{c_k})\) , where
\begin{equation} c_k = \max _{d=(d_0, \dots , d_{k-1})} C_k(d_0, \dots , d_{k-1}).{\href{#fn13}{^{13}}} \end{equation}
(9)
Both (7) and (8) are defined by Dalirrooyfard et al. (see Section 5 in [14]) in the exact same manner, as part of their description and analysis of the Yuster-Zwick algorithm [38].
We conclude that the \({\rm\small W-HOM-CNT}_{\vec{C}_{2k}}\) problem can be solved in degenerate graphs in time \(\tilde{O}(n^{c_k})\) .□
This is analogous to the proof of Part (ii), except that now we use Theorem 7. So, let \(G\) be an \(n\) -vertex degenerate graph and let \(\vec{G}\) be the DAG corresponding to a degenerate ordering of \(G\) . We need to compute \(\hom (C_{2k},G)\) in \(\tilde{O}(n^{c_k})\) time (the proof for \(\hom (C_{2k+1},G)\) is analogous). As in the proof of Part (ii), it suffices to show that for \(2 \le \ell \le k\) , \({\rm\small W-HOM-CNT}_{\vec{C}_{2\ell }}\) can be solved in time \(\tilde{O}(n^{c_k})\) in weighted degenerate digraphs. And this is indeed the case by Theorem 7.□
6 Counting Cycle Homomorphisms Vs. Directed-cycle Detection
In this section we prove Theorems 2 and 4 as they bear some similarity. An important ingredient in the proof of Theorem 2 is the fact that the number of cycle transversals in partite graphs can be computed efficiently using an inclusion-exclusion procedure. To make this statement precise we need the following definition.
Let \(G\) be a \(p\) -partite graph with a given vertex partition \({\mathcal {P}}=\lbrace V_1,\ldots ,V_p\rbrace\) . A \({\mathcal {P}}\) -cycle transversal of \(G\) is a simple cycle of length \(p\) in \(G\) containing a single vertex from each part of \({\mathcal {P}}\) .
A family of graphs \({\mathcal {F}}\) is subgraph-closed if \(G \in {\mathcal {F}}\) implies that every subgraph of \(G\) is also in \({\mathcal {F}}\) . For example, \(d\) -degenerate graphs are subgraph-closed.
14 Let \(p \ge 3\) . Suppose that \({\mathcal {F}}\) is a subgraph-closed family of graphs and that \({\rm\small HOM-CNT}_{C_p}\) can be computed in \(f(n)\) time for graphs in \({\mathcal {F}}\) . Then, given a \(p\) -partite \(n\) -vertex graph \(G \in {\mathcal {F}}\) together with a vertex partition \({\mathcal {P}}\) , the number of \({\mathcal {P}}\) -cycle transversals of \(G\) can be computed in \(O(f(n))\) time.
Let \({\mathcal {P}}=\lbrace V_1,\ldots ,V_p\rbrace\) . For a non-empty subset \(S \subseteq [p]\) , let \(G_S\) denote the \(|S|\) -partite induced subgraph of \(G\) with partition \({\mathcal {P}}_S=\lbrace V_i \,|\, i \in S\rbrace\) . Let \(M\) denote the number of homomorphisms that are \({\mathcal {P}}\) -cycle transversals of \(G\) (the number of \({\mathcal {P}}\) -cycle transversals can be derived from the number of such homomorphisms after dividing by \(2p\) ). By the inclusion-exclusion principle we haveSince \({\mathcal {F}}\) is subgraph-closed and since \(G_S\) has at most \(n\) vertices, we can compute \(\hom (C_p,G_S)\) in \(f(n)\) time. Hence, \(M\) can be computed in \(O(2^p f(n))=O(f(n))\) time, as required.□
\begin{equation*} M = \sum _{S \subseteq [p]} (-1)^{p-|S|}\hom (C_p,G_S). \end{equation*}
We assume that there is an algorithm that computes \({\rm\small HOM-CNT}_{C_{2k}}\) in 2-degenerate graphs in \(O(n^\alpha)\) time. Let \(G\) be an arbitrary directed graph with \(m\) edges. Recall that our goal is to decide if \(G\) has a simple \(C_k\) . We first describe a randomized algorithm, based on the color-coding method [3]. Randomly partition the vertices of \(G\) into \(k\) parts \(V_1,\ldots ,V_k\) . Let \(G^{\prime }\) be the subgraph of \(G\) consisting only of the edges \((u,v)\) such that there exists \(1 \le i \le k\) where \(u \in V_i\) and \(v \in V_{i+1}\) (indices taken modulo \(k\) ). Notice that \(G^{\prime }\) has no directed cycles whose length is shorter than \(k\) , and with constant probability (at least \(k^{-k}\) ), \(G^{\prime }\) has a directed \(C_k\) if \(G\) has one.
Next, subdivide each edge \((u,v)\) of \(G^{\prime }\) into two edges \((u,z_{uv})\) and \((z_{uv},v)\) where \(z_{uv}\) is a new vertex, and denote the newly obtained graph by \(G^*\) . Furthermore, ignore edge directions in \(G^*\) and hence \(G^*\) is an undirected 2-degenerate graph with \(O(m)\) vertices. Also, \(G^*\) is \((2k)\) -partite as can be seen from the partition of of its vertex set \({\mathcal {P}}=\lbrace V_1,V_{1,2},V_2,V_{2,3},\ldots ,V_k,V_{k,1}\rbrace\) where \(V_{i,i+1} = \lbrace z_{uv}\,|\, u \in V_i,\, v \in V_{i+1}\,, (u,v) \in E(G^{\prime })\rbrace\) . The simple but crucial point now is that \(G^{\prime }\) has a directed \(C_k\) if and only if \(G^*\) has a \({\mathcal {P}}\) -cycle transversal. Indeed, every \({\mathcal {P}}\) -cycle transversal must be of the form \((u_1,z_{u_1u_2},u_2,z_{u_2u_3},\ldots ,u_k,z_{u_k u_1})\) where \((u_1,\ldots ,u_k)\) is a directed \(C_k\) in \(G\) . Now, by Lemma 6.2, we can decide if \(G^*\) has a \({\mathcal {P}}\) -cycle transversal in \(O(|v(G^*)|^\alpha)=O(m^\alpha)\) time, implying that we can decide if \(G^{\prime }\) has a \(C_k\) in the same time.
To make the algorithm deterministic we recall that the color-coding method can be derandomized. In particular, it is shown in [3] that one can deterministically compute \(O(\log m)\) partitions of the vertices of \(G\) (the partitions can be computed in \(O(m \log m)\) time), such that if \(G\) has a \(C_k\) , then for at least one of the partitions, the corresponding \(G^{\prime }\) has a \(C_k\) . Hence, the (now deterministic) running time to decide if \(G\) has a \(C_k\) is \(O(m\log m + m^\alpha \log m)=O(m^\alpha \log m)\) as clearly we can assume that \(\alpha \ge 1\) .
Observe that in the statement of Theorem 2 we also claim a similar result for \(C_{2k+1}\) , not just \(C_{2k}\) as we have just proved. Indeed, it is straightforward to modify the proof of Theorem 2 to obtain the following slightly more general statement: Let \(k \ge 3\) and let \(p \ge 2k\) . If there is an algorithm that computes \({\rm\small HOM-CNT}_{C_p}\) in 2-degenerate graphs in \(O(n^\alpha)\) time, then there is an algorithm that decides if an arbitrary directed \(m\) -edge graph has a \(C_k\) in time \(O(m^\alpha)\) (randomized) and \(O(m^\alpha \log m)\) (deterministic). One simple way to achieve this is to subdivide each edge \((u,v)\) in \(G^{\prime }\) into a path of length 2 as in the proof of Theorem 2, except for edges of the form \((u,v)\) where \(u \in V_1\) and \(v \in V_2\) which are subdivided into a path of length \(p+2-2k\) .□
We prove for undirected degenerate graphs; the proof for directed degenerate graphs is similar. Let \(k \ge 6\) . Let \(G\) be an undirected degenerate graph with \(n\) vertices in which we wish to detect a \(C_k\) . As in the proof of Theorem 2 we use color-coding. Randomly partition the vertices of \(G\) into \(k\) parts \(V_1,\ldots ,V_k\) . Let \(G^{\prime }\) be the subgraph of \(G\) consisting only of the edges \((u,v)\) such that there exists \(1 \le i \le k\) where \(u \in V_i\) and \(v \in V_{i+1}\) (indices taken modulo \(k\) ). Notice that \(G^{\prime }\) has no cycle transversal, unless \(G\) has a \(C_k\) , and conversely, if \(G\) has a \(C_k\) then \(G^{\prime }\) has a cycle transversal with constant positive probability. By Lemma 6.2 and by Theorem 1, we can determine if \(G^{\prime }\) has a cycle transversal in \(\tilde{O}(n^{d_{\lfloor k/2 \rfloor }})\) time. Again, as color-coding can be derandomized, we can also obtain a deterministic algorithm in \(\tilde{O}(n^{d_{\lfloor k/2 \rfloor }})\) time.□
7 A Combinatorial Algorithm for Counting Cycle Homomorphisms in General Graphs
As our final result, we use our methods to obtain a combinatorial algorithm for counting the number of \(C_k\) -homomorphisms in a (general) directed or undirected graph with \(m\) edges in \(\tilde{O}(m^{2-1/\lceil k/2 \rceil })\) time:
For every \(k \ge 3\) , there is an algorithm which, given an input (di)graph \(G\) with \(m\) edges, computes the number of homomorphisms from \(C_k\) to \(G\) in time \(\tilde{O}(m^{2 - 1/\lceil k/2 \rceil })\) .
In the directed case, the \(C_k\) above denotes the directed \(k\) -cycle.
It should be pointed out that, as in the proof of Theorem 4, we can use Theorem 8 to obtain an algorithm which detects if a directed or undirected graph has a \(C_k\) in \(\tilde{O}(m^{2-1/\lceil k/2 \rceil })\) time. The proof in the directed setting is particularly simple: given a digraph \(\vec{G}\) , we randomly partition its vertices into sets \(V_1,\dots ,V_k\) and only keep the edges going from \(V_i\) to \(V_{i+1}\) (for some \(1 \le i \le k)\) , denoting the resulting subdigraph by \(\vec{G}^{\prime }\) . If \(\vec{G}\) contains a \(C_k\) then with constant positive probability so does \(\vec{G}^{\prime }\) . Moreover, every \(C_k\) -homomorphism in \(\vec{G}^{\prime }\) corresponds to a proper copy of \(C_k\) , so computing \(\hom (C_k,\vec{G}^{\prime })\) suffices in order to decide if \(\vec{G}^{\prime }\) contains a \(C_k\) . Again, this can be derandomized at the cost of increasing the runtime by a logarithmic factor.
The proof of Theorem 8 is similar to that of Theorem 6. To keep the presentation simple, we focus on undirected graphs; the proof for digraphs is similar. Let \(P_r\) denote the path with \(r+1\) vertices \(1,\dots ,r+1\) (so \(P_r\) has \(r\) edges).
There is an algorithm which, given integers \(r,\Delta \ge 1\) and an input graph \(G\) with \(m\) edges, computes the following:
(1)
For every \(x,y \in V(G)\) , the number \(N_{r,\Delta }(x,y)\) of homomorphisms \(\varphi : P_r \rightarrow G\) such that \(\varphi (1) = x\) , \(\varphi (r+1) = y\) , and \(d_G(\varphi (t)) \le \Delta\) for every \(2 \le t \le r\) .
(2)
For every \(x,y \in V(G)\) with \(d_G(x) \gt \Delta\) and for every function \(f : \lbrace 2,\dots ,r+1\rbrace \rightarrow \lbrace \mbox{low, high}\rbrace\) , the number \(M_{r,\Delta ,f}(x,y)\) of homomorphisms \(\varphi : P_r \rightarrow G\) such that \(\varphi (1) = x\) and \(\varphi (r+1) = y\) , and such that for every \(t \in \lbrace 2,\dots ,r+1\rbrace\) it holds that \(d_G(\varphi (t)) \le \Delta\) if \(f(t) = \mbox{low}\) and \(d_G(\varphi (t)) \gt \Delta\) if \(f(t) = \mbox{high}\) .
The computation for Item 1 takes time \(\tilde{O}(m\Delta ^{r-1})\) and the computation for Item 2 takes time \(\tilde{O}(m^2/\Delta)\) . Furthermore, the number of pairs \(x,y\) with \(N_{r,\Delta }(x,y) \gt 0\) is \(O(m\Delta ^{r-1})\) .
As in Section 4, we save all computed information in a hash map. We start by proving Item 1. Here we simply enumerate all homomorphisms \(\varphi : P_r \rightarrow G\) such that \(d_G(\varphi (t)) \le \Delta\) for every \(2 \le t \le r\) . Enumerating all such homomorphisms is clearly sufficient to produce the desired counts. To choose such a homomorphism \(\varphi\) , we first choose the pair \((\varphi (1),\varphi (2))\) , for which there are at most \(2m\) choices, as this pair must be an edge. We only go over choices for which \(d_G(\varphi (2)) \le \Delta\) . Having chosen \(\varphi (2)\) , we have at most \(\Delta\) choices for \(\varphi (3)\) , where again we only consider choices which satisfy \(d_G(\varphi (3)) \le \Delta\) . Having chosen \(\varphi (3)\) , there are at most \(\Delta\) choices for \(\varphi (4)\) , and so on. Continuing in this fashion, we see that there are at most \(\Delta\) choices for each of the vertices \(\varphi (3),\dots ,\varphi (r+1)\) . Hence, the total number of choices is \(O(m\Delta ^{r-1})\) . In particular, the number of pairs \(x,y\) with \(N_{r,\Delta }(x,y) \gt 0\) (namely, which are the endpoints in such a homomorphism) is \(O(m\Delta ^{r-1})\) .
We now establish Item 2 by induction on \(r\) . The base case \(r = 1\) is trivial, since \(P_1\) is simply an edge, and we can enumerate all edges in time \(m \le m^2/\Delta\) . (We may assume that \(\Delta \le m\) , because otherwise there are no vertices of degree larger than \(\Delta\) .)
We now proceed to the induction step. Assume, by the induction hypothesis, that we have already computed the desired counts for \(P_{r-1}\) . To achieve this for \(P_r\) , go over all choices for a vertex \(x \in V(G)\) such that \(d_G(x) \gt \Delta\) and a pair of vertices \((u,y)\) such that \(\lbrace u,y\rbrace \in E(G)\) . The number of such choices is at most \(O(m^2/\Delta)\) , since there are \(2m\) choices for \((u,y)\) and \(O(m/\Delta)\) choices for \(x\) . For each function \(g : \lbrace 2,\dots ,r\rbrace \rightarrow \lbrace \mbox{low, high}\rbrace\) , we have already computed the number \(M_{r-1,\Delta ,g}(x,u)\) of homomorphisms \(\psi : P_{r-1} \rightarrow G\) such that \(\psi (1) = x\) and \(\psi (r) = u\) , and such that for every \(t \in \lbrace 2,\dots ,r\rbrace\) it holds that \(d_G(\varphi (t)) \le \Delta\) if \(g(t) = \mbox{low}\) and \(d_G(\varphi (t)) \gt \Delta\) if \(g(t) = \mbox{high}\) . Now, for each such \(\psi\) and \(g\) , the map \(\varphi : V(P_r) \rightarrow V(G)\) which agrees with \(\psi\) on \(P_r[\lbrace 1,\dots ,r\rbrace ] = P_{r-1}\) and satisfies \(\varphi (r+1) = y\) , is a homomorphism from \(P_r\) to \(G\) satisfying \(\varphi (1) = x\) and \(\varphi (r+1) = y\) . Furthermore, the function \(f : \lbrace 2,\dots ,r+1\rbrace \rightarrow \lbrace \mbox{low, high}\rbrace\) corresponding to \(\varphi\) is simply the function which agrees with \(g\) on \(\lbrace 2,3,\dots ,r\rbrace\) and satisfies \(f(r+1) = \mbox{low}\) if \(d_G(y) \le \Delta\) and \(f(r+1) = \mbox{high}\) if \(d_G(y) \gt \Delta\) . It is now easy to see that in this manner we obtain the desired count for the pair \(x,y\) .□
We may assume that \(G\) is connected, and hence \(m \ge n - 1\) , where \(n = |V(G)|\) . Set \(\Delta := m^{1/\lceil k/2 \rceil }\) . Denote the vertices of \(C_k\) by \(v_1,\dots ,v_k\) . In order to compute \(\hom (C_k,G)\) , we will compute, for every function \(g : \lbrace v_1,\dots ,v_k\rbrace \rightarrow \lbrace \mbox{low, high}\rbrace\) , the number \(\hom _g\) of homomorphisms \(\varphi : C_k \rightarrow G\) such that \(d_G(\varphi (v_i)) \le \Delta\) if \(g(v_i) = \mbox{low}\) and \(d_G(\varphi (v_i)) \gt \Delta\) if \(g(v_i) = \mbox{high}\) (for every \(1 \le i \le k\) ). Clearly, \(\hom (C_k,G) = \sum _{g}{\hom _g}\) . We consider two cases. Suppose first that \(g(v_i) = \mbox{low}\) for every \(1 \le i \le k\) . It is easy to see that \(C_k\) consists of a copy of \(P_{\lfloor k/2 \rfloor }\) and a copy of \(P_{\lceil k/2 \rceil }\) , glued together at their endpoints. It is now easy to see that for this particular \(g\) , one haswhere \(N_{r,\Delta }(x,y)\) is as defined in Item 1 of Lemma 7.1. Since we can compute the counts \(N_{\lfloor k/2 \rfloor ,\Delta }(x,y), N_{\lceil k/2 \rceil ,\Delta }(x,y)\) for all pairs of vertices \(x,y \in V(G)\) (simultaneously) in time \(\tilde{O}(m \Delta ^{\lceil k/2 \rceil -1})\) , and since the total number of pairs for which these counts are non-zero is \(O(m \Delta ^{\lceil k/2 \rceil -1})\) , the above sum can be computed in time \(\tilde{O}(m \Delta ^{\lceil k/2 \rceil -1}) = \tilde{O}(m^{2 - 1/\lceil k/2 \rceil })\) , as required.
\begin{equation*} \hom _g = \sum _{{c}x,y \in V(\vec{G}): \\ d_G(x), d_G(y) \le \Delta } {N_{\lfloor k/2 \rfloor ,\Delta }(x,y) \cdot N_{\lceil k/2 \rceil ,\Delta }(x,y)}, \end{equation*}
Suppose now that \(g(v_i) = \mbox{high}\) for some \(1 \le i \le k\) . We proceed similarly to the previous case. Decompose \(C_k\) into a copy \(P\) of \(P_{\lfloor k/2 \rfloor }\) and a copy \(P^{\prime }\) of \(P_{\lceil k/2 \rceil }\) , such that \(v_i\) is an endpoint of both of these paths. Let \(f,f^{\prime }\) be the “low/high signatures” corresponding the paths \(P,P^{\prime }\) , respectively. Again, it is not hard to see thatBy Item 2 of Lemma 4.1, one can compute \(M_{\lfloor k/2 \rfloor ,\Delta ,f}(x,y)\) and \(M_{\lceil k/2 \rceil ,\Delta ,f^{\prime }}(x,y)\) for all pairs \(x,y \in V(G)\) with \(d_G(x) \gt \Delta\) in time \(\tilde{O}(m^2/\Delta)\) . Furthermore, the number of such pairs \(x,y\) is \(O(m^2/\Delta)\) , because there are \(O(m/\Delta)\) choices for \(x\) and \(n = O(m)\) choices for \(y\) . We conclude that the above sum can be computed in time \(\tilde{O}(m^2/\Delta) = \tilde{O}(m^{2 - 1/\lceil k/2 \rceil })\) , as required. This completes the proof of the theorem.□
\begin{equation*} \hom _g = \sum _\begin{array}{c}x,y \in V(G) \; : \; d_G(x) \gt \Delta \end{array} {M_{\lfloor k/2 \rfloor ,\Delta ,f}(x,y) \cdot M_{\lceil k/2 \rceil ,\Delta ,f^{\prime }}(x,y) }. \end{equation*}
Footnotes
1
In fact, they only conjectured the value of \(c_k\) when \(k\) is odd; for even \(k\) it was not even clear what the “right” conjecture should be.
2
As in [14], the value of \(c_k\) in (2) assumes, for simplicity, that rectangular matrix multiplication is simulated by square matrix multiplication; the exact definition of \(c_k\) is given in (9). If \(\omega \gt 2\) and the fastest known rectangular matrix multiplication algorithms are used, \(c_k\) results in a marginal improvement over the value in (2).
3
When \(k\) is odd and \(\omega \gt \frac{2k}{k-1}\) , one can prove that \(c_k \le 2-\frac{2}{k+1} \lt \frac{(k+1)\omega }{2\omega + k-1}\) , which matches the runtime of the fastest combinatorial algorithm.
4
We note that counting copies of cycles remains \(\#W[1]\) -hard even in bounded-degeneracy graphs. This follows from the fact that counting \(k\) -cycles in general graphs can be reduced to counting \(2k\) -cycles in 2-degenerate ones via the reduction which replaces each edge of the input graph by a path of length 2 (thus producing a 2-degenerate graph).
5
We note that degeneracy is closely related to another well-studied graph parameter, namely arboricity, which is the minimum number of forests into which the edge-set of a graph can be partitioned. It is well-known that the arboricity of a \(d\) -degenerate graph is between \((d+1)/2\) and \(d\) .
6
Bressan’s result in its full generality states that for every graph \(H\) , one can count \(H\) -homomorphisms in bounded-degeneracy graphs in time \(\tilde{O}(n^{\tau (H)})\) , where \(\tau (H)\) is a suitable width parameter called DAG treewidth.
7
The “only if” direction of this result is under a certain standard hardness assumption from fine-grained complexity [1]. The proof of this direction actually shows that if \(H\) contains an induced \(\ell\) -cycle for some \(\ell \ge 6\) , then one cannot count \(H\) -homomorphisms in bounded-degeneracy graphs in time \(O(n^{1+\gamma })\) , where \(\gamma \gt 0\) is some fixed constant.
8
A degeneracy ordering of a graph can be found in time linear in its number of edges [26]. In particular, since a bounded-degeneracy graph has \(O(n)\) edges, a degeneracy ordering of such a graph can be found in time \(O(n)\) .
9
Indeed, one can observe that if the number of sources in \(\vec{H}\) is \(p \gt 1\) , then \(\vec{H}\) is a directed subdivision of the alternating orientation of \(C_{2p}\) . If \(p = 1,\) then we can think of \(C_{\ell }\) as the subdivision of the 2-vertex alternating cycle \(C_2\) , which is the multigraph with two vertices \(x,y\) and two parallel edges from \(x\) to \(y\) . Theorem 5 applies to \(\vec{H} = C_2\) as well. A different way to handle the case \(p = 1\) is to observe that in this case one can easily count homomorphisms of \(\vec{H}\) in linear time [10].
10
Here, and in what follows, by degenerate digraphs we mean digraphs where all out-degrees are bounded.
11
This is because after choosing the image of the unique source of \(\vec{H}\) (under a homomorphism from \(\vec{H}\) to \(\vec{G}\) ), there are \(O(1)\) choices for every other vertex of \(\vec{H}\) , as all vertices of \(\vec{H}\) are reachable from the source and \(\vec{G}\) has bounded out-degrees.
12
One way to do it is as follows. For every entry \((y,x)\) in the sparse representation of \(B^d_{j,i}\) , store its value in a hash table, with \((y,x)\) being the key. Then, go over all entries \((x,y)\) in the sparse representation of \(B^d_{i,j}\) , and check whether the key \((y,x)\) is in the hash table. If so, accumulate the product of the two entries.
13
The definition of \(c_k\) in [14] (which corresponds to the one of Yuster and Zwick) has an additional component (which comes from a certain combinatorial procedure, that is not applicable to our algorithm). More specifically, it is defined as \(c_k = \max _{d=(d_0, \dots , d_{k-1})} \min \left\lbrace \min _{0 \le i \le k-1} (2-d_i), C_k(d_0, \dots , d_{k-1}) \right\rbrace\) . Seemingly, this definition is not equivalent to ours, and (possibly) gives a better running time. However, this is not the case. In particular, the upper bounds on \(c_k\) (as defined in [14]) are obtained by attaining upper bounds on \(C_k\) . Specifically, it is shown in [14], that for odd \(k\) and arbitrary \(d_0, \dots , d_{k-1}\) , \(C_k(d_0, \dots , d_{k-1}) \le \frac{(k+1)\omega }{2\omega +k-1}\) , and, for \(\omega \le \frac{2k}{k-1}\) , a specific sequence \(d=(d_0, \dots , d_{k-1})\) is presented such that \(\min _{0 \le i \le k-1} (2-d_i) \ge C_k(d_0, \dots , d_{k-1}) = \frac{(k+1)\omega }{2\omega +k-1}\) (see Section 5.4 in [14]); and for even \(k\) and arbitrary \(d_0, \dots , d_{k-1}\) , \(C_k(d_0, \dots , d_{k-1}) \le \frac{k\omega - \frac{4}{k}}{2\omega + k-2-\frac{4}{k}}\) , and, for \(\omega = 2\) , a specific sequence \(d=(d_0, \dots , d_{k-1})\) is presented such that \(\min _{0 \le i \le k-1} (2-d_i) \ge C_k(d_0, \dots , d_{k-1}) = \frac{k\omega - \frac{4}{k}}{2\omega + k-2-\frac{4}{k}}\) (see Section 5.6 in [14]). Therefore, as the minimum between \(\min _{0 \le i \le k-1} (2-d_i)\) and \(C_k(d_0, \dots , d_{k-1})\) is chosen, we conclude that the expression in our definition of \(c_k\) is, in fact, equal to the one presented in [14].
14
A similar lemma appears in [13].
A Proof of Lemma 3.1
The proof of Lemma 3.1 uses the notion of tensor product of digraphs, which we now recall.
Let \(G_1\) and \(G_2\) be directed graphs. The tensor product of \(G_1\) and \(G_2\) , denoted \(G_1 \times G_2\) , is a directed graph with vertex set \(V(G_1 \times G_2) = V(G_1) \times V(G_2)\) , and edge set
\begin{equation*} E(G_1 \times G_2) = \lbrace ((x_1,x_2), (y_1,y_2)) \, | \, (x_1,y_1) \in E(G_1) \mbox{ and } (x_2,y_2) \in E(G_2)\rbrace . \end{equation*}
A key property of the directed tensor product is that the parameter \(\hom (\vec{H},\cdot)\) is multiplicative with respect to it (for any digraph \(\vec{H}\) ). That is, for every pair of directed graphs \(\vec{G_1}, \vec{G_2}\) , it holds thatTo see that (10) holds, simply observe that for functions \(\varphi _i : V(\vec{H}) \rightarrow V(\vec{G_i})\) (where \(i \in \lbrace 1,2\rbrace\) ), the function \(v \mapsto (\varphi _1(v),\varphi _2(v))\) is a homomorphism from \(\vec{H}\) to \(\vec{G_1} \times \vec{G_2}\) if and only if \(\varphi _i\) is a homomorphism from \(\vec{H}\) to \(\vec{G_i}\) for each \(i \in \lbrace 1,2\rbrace\) .
\begin{equation} \hom (\vec{H}, \vec{G_1} \times \vec{G_2}) = \hom (\vec{H}, \vec{G_1}) \cdot \hom (\vec{H}, \vec{G_2}). \end{equation}
(10)
We will also need the following (trivial) observation regarding tensor products and degeneracy.
Let \(\vec{F},\vec{G}\) be directed graphs. If the out-degree of every vertex in \(G\) is at most \(d\) , then the out-degree of every vertex in \(\vec{F} \times \vec{G}\) is at most \(v(\vec{F}) \cdot d\) .
For each \(x \in V(\vec{F})\) and \(y \in V(\vec{G})\) , the out-degree of \((x,y)\) in \(\vec{F} \times \vec{G}\) is \(\text{out-deg}_{\vec{F} \times \vec{G}}((x,y)) = \text{out-deg}_{\vec{F}}(x) \cdot \text{out-deg}_{\vec{G}}(y) \lt v(\vec{F}) \cdot d\) .□
The last ingredient in the proof of Lemma 3.1 is the following directed version of a lemma of Erdős, Lovász, and Spencer [17] (see also Proposition 5.44(b) in [24]). For completeness, we give its proof at the end of this appendix (this proof is essentially identical to the undirected case).
Let \(\vec{H_1}, \dots , \vec{H_k}\) be pairwise non-isomorphic directed graphs, and let \(c_1, \dots , c_k\) be non-zero constants. Then, there exist directed graphs \(\vec{F_1}, \dots , \vec{F_k}\) such that the \(k \times k\) matrix \(M_{i,j} = c_j \cdot \hom (\vec{H_j}, \vec{F_i})\) , \(1 \le i,j \le k\) , is invertible.
The “if” part of the lemma is immediate. Let us prove the “only if” part. So assume that \({\rm\small HOM-CNT}_{c_1 \vec{H_1} + \dots + c_k \vec{H_k}}\) can be solved in time \(O(n^\alpha)\) in \(n\) -vertex degenerate digraphs. Our goal is to show that \({\rm\small HOM-CNT}_{\vec{H_i}}\) can be solved in time \(O(n^\alpha)\) for all \(1 \le i \le k\) . Let \(\vec{G}\) be an \(n\) -vertex degenerate digraph for which we would like to compute \(\hom (\vec{H_i},\vec{G})\) for all \(1 \le i \le k\) . By Lemma A.3, there are digraphs \(\vec{F_1}, \dots , \vec{F_k}\) such that the \(k \times k\) matrix \(M_{i,j} := c_j \cdot \hom (\vec{H_j},\vec{F_i})\) (for \(1 \le i,j \le k\) ) is invertible. For each \(1 \le i \le k\) , we set \(b_i := c_1 \cdot \hom (\vec{H_1}, \vec{F_i} \times \vec{G}) + \dots + c_k \cdot \hom (\vec{H_k}, \vec{F_i} \times \vec{G})\) and observe thatwhere we have used (10). We will treat (11) (for \(1 \le i \le k\) ) as a system of linear equations, where \(\hom (\vec{H_1},\vec{G}),\dots ,\hom (\vec{H_k},\vec{G})\) are the variables, \(M\) is the matrix of the system, and \(b_1,\dots ,b_k\) are the constant terms. Since \(M\) is invertible (as guaranteed by our choice of \(\vec{F_1},\dots ,\vec{F_k}\) ), knowing \(b_1,\dots ,b_k\) would enable us to find \(\hom (\vec{H_1},\vec{G}),\dots ,\hom (\vec{H_k},\vec{G})\) .
\begin{equation} b_i = \sum _{j = 1}^{k}{c_j \cdot \hom (\vec{H_j},\vec{F_i} \times \vec{G})} = \sum _{j = 1}^{k}{c_j \cdot \hom (\vec{H_j},\vec{F_i}) \cdot \hom (\vec{H_j},\vec{G})} = \sum _{j = 1}^{k}{M_{i,j} \cdot \hom (\vec{H_j},\vec{G})} \end{equation}
(11)
Note that for each \(1 \le i \le k\) , the digraph \(\vec{F_i} \times \vec{G}\) can be constructed in time \(O(n)\) , is \(O(1)\) -degenerate (see Observation A.2), and has \(v(\vec{F_i}) \cdot n = O(n)\) vertices. Hence, since by our assumption \({\rm\small HOM-CNT}_{c_1 \vec{H_1} + \cdots + c_k \vec{H_k}}\) can be solved in time \(O(n^\alpha)\) , we can compute \(b_1, \dots , b_k\) in time \(O(n^\alpha)\) by feeding the graphs \(\vec{F_1} \times \vec{G}, \ldots , \vec{F_k} \times \vec{G}\) to an algorithm which solves \({\rm\small HOM-CNT}_{c_1 H_1 + \cdots + c_k H_k}\) in time \(O(n^\alpha)\) in degenerate digraphs. This in turn enables us to compute \(\hom (\vec{H_1},\vec{G}), \ldots , \hom (\vec{H_k},\vec{G})\) , as required.□
Since multiplying the rows of an invertible matrix by non-zero scalars leaves it invertible, we may assume, without loss of generality, that \(c_1 = \dots = c_k = 1\) . We will also assume thatwhere, as always, \(v(G), e(G)\) denote the number of vertices and the number of edges in \(G\) , respectively. For every \(1 \le i \le k\) , we define a suitable blowup of \(H_i\) , denoted \(F_i\) , as follows. Every vertex \(v \in V(H_i)\) is replaced by an independent set \(I_{i,v}\) of size \(x_{i,v} \ge 1\) , and every edge \((u,v) \in E(H_i)\) is replaced by a directed complete bipartite graph, connecting \(I_{i,u}\) to \(I_{i,v}\) . The resulting graph is \(F_i\) . We will consider the values \(\lbrace x_{i,v} \, | \, i \in [k], v \in V(H_i)\rbrace\) as variables taking positive integer values, and show that there is an assignment to these variables for which the matrix \(M_{i,j} = \mbox{hom}(H_i, F_j)\) is invertible. (This matrix is the transpose of the matrix appearing in the statement of the lemma, so this will be sufficient.)
\begin{equation} v(H_1)+e(H_1) \le v(H_2)+e(H_2) \le \dots \le v(H_k)+e(H_k), \end{equation}
(12)
We claim that \(D := \det (M)\) is a non-zero polynomial in the variables \(\lbrace x_{i,v} \, | \, i \in [k], v \in V(H_i)\rbrace\) . In what follows, it will be convenient to use the following notation: for graphs \(H,G\) , \(\text{Hom}(H,G)\) denotes the set of all homomorphisms from \(H\) to \(G\) , and \(\text{Inj}(H,G)\) denotes the set of all injective homomorphisms from \(H\) to \(G\) (so \(\hom (H,G) = |\text{Hom}(H,G)|\) and \(\mathrm{inj}(H,G) = |\text{Inj}(H,G)|\) ). We start by observing that for all \(i,j \in [k]\) ,
\begin{equation} \hom (H_i, F_j) = \sum _{\varphi \in \text{Hom}(H_i,H_j)} \, \prod _{v \in V(H_j)} x_{j,v}^{|\varphi ^{-1}(v)|} \,. \end{equation}
(13)
Indeed, it is easy to see that every homomorphism \(\psi : H_i \rightarrow F_j\) corresponds to some homomorphism \(\varphi : H_i \rightarrow H_j\) (if \(\alpha _j: F_j \rightarrow H_j\) denotes the “natural map” mapping \(I_{j,v}\) to \(v\) for all \(v \in V(H_j)\) , then \(\varphi\) can be expressed as \(\varphi = \alpha _j \circ \psi\) ). Moreover, the number of homomorphisms \(\psi : H_i \rightarrow F_j\) which correspond to a given homomorphism \(\varphi : H_i \rightarrow H_j\) is exactly the number of ways to choose a vertex from \(I_{j,\varphi (u)}\) for each \(u \in V(H_i)\) ; this number is exactly the product on the right-hand side of (13).
Since every entry of \(M\) is a polynomial in \(\lbrace x_{i,v} \, | \, i \in [k], v \in V(H_i)\rbrace\) , so is \(D = \det (M)\) . Our goal is to prove that \(D\) is not the zero polynomial. To this end, we will show that the multilinear part of \(D\) is non-zero (which clearly implies that \(D\) is non-zero). For convenience, let us write \(ML(p)\) for the multilinear part of a polynomial \(p\) (i.e., the sum of all multilinear monomials of \(p\) ). Observe that for every pair \(i,j \in [k]\) and for every homomorphism \(\varphi : V(H_i) \rightarrow V(H_j)\) , the monomialis multilinear if and only if \(|\varphi ^{-1}(v)| \le 1\) for all \(v\) , which is equivalent to \(\varphi\) being injective. Thus, using (13), we conclude that the multilinear part of \(\hom (H_i,F_j)\) is
\begin{equation*} \prod _{v \in V(H_j)} x_{j,v}^{|\varphi ^{-1}(v)|} \end{equation*}
\begin{equation} L_{i,j} := ML(\hom (H_i,F_j)) = \sum _{\varphi \in \text{Inj}(H_i,H_j)} \, \prod _{v \in V(H_j)} x_{j,v}^{|\varphi ^{-1}(v)|} \,. \end{equation}
(14)
Observe that for each \(1 \le i \le k\) , \(L_{i,i} \ne 0\) (as a polynomial). Indeed, injective homomorphisms from \(H_i\) to itself are simply automorphisms of \(H_i\) , so (14) becomesWe now claim that for every pair \(1 \le j \lt i \le k\) , one has \(\text{Inj}(H_i,H_j) = \emptyset\) , and hence \(L_{i,j} \equiv 0\) . Fix any \(1 \le j \lt i \le k\) . If there exists an injective homomorphism from \(H_i\) to \(H_j\) , then we must have \(v(H_i) \le v(H_j)\) and \(e(H_i) \le e(H_j)\) . On the other hand, we have assumed in (12) that \(v(H_j)+e(H_j) \le v(H_i)+e(H_i)\) , as \(j \lt i\) . It follows that \(v(H_i) = v(H_j)\) and \(e(H_i) = e(H_j)\) , which implies that \(H_i\) and \(H_j\) are isomorphic, contradicting our assumption that \(H_1, \dots , H_k\) are pairwise non-isomorphic. Therefore, \(\text{Inj}(H_i,H_j) = \emptyset\) , which immediately implies that \(L_{i,j} \equiv 0\) .
\begin{equation*} L_{i,i} = \mathrm{aut}(H_i) \cdot \prod _{v \in V(H_i)}{x_{i,v}}. \end{equation*}
Now consider the \(k \times k\) matrix \(L\) whose entries are \(L_{i,j}\) ( \(1 \le i,j \le k\) ). In the previous paragraph we established that \(L\) is upper-triangular, and that its diagonal entries are non-zero (as polynomials). It follows that \(\det (L)\) is a non-zero polynomial. Finally, we show that the multilinear part of \(D = \det (M)\) is \(ML(D) = \det (L)\) . To this end, we recall that
\begin{equation} D = \sum _{\sigma \in S_k} \text{sgn}(\sigma) \cdot \prod _{i=1}^k M_{i,\sigma (i)} = \sum _{\sigma \in S_k} \text{sgn}(\sigma) \cdot \prod _{i=1}^k \hom (H_{i}, F_{\sigma (i)}). \end{equation}
(15)
Now, since the sets of variables of \(\hom (H_1,F_{\sigma (1)}), \dots , \hom (H_k,F_{\sigma (k)})\) are pairwise-disjoint (recall that the variables of \(\hom (H_i,F_j)\) are \(x_{j,v}\) , \(v \in V(H_j)\) ), we have
\begin{equation} ML\left(\prod _{i=1}^k \hom (H_{i}, F_{\sigma (i)}) \right) = \prod _{i=1}^k ML(\hom (H_{i}, F_{\sigma (i)})) = \prod _{i=1}^k L_{i,\sigma (i)}. \end{equation}
(16)
By combining (15) and (16), we getas required. As \(\det (L)\) is a non-zero polynomial, \(D\) is a non-zero polynomial as well. It follows that there is an assignment of positive natural numbers to the variables \(\lbrace x_{i,v} \, | \, i \in [k], v \in V(H_i)\rbrace\) for which \(D \ne 0\) . Evidently, for this assignment, the matrix \(M\) is invertible (as \(D = \det (M)\) ). This completes the proof.□
\begin{equation*} ML(D) = \sum _{\sigma \in S_k} \text{sgn}(\sigma) \cdot \prod _{i=1}^k L_{i,\sigma (i)} = \det (L), \end{equation*}
References
[1]
A. Abboud and V. Vassilevska Williams. 2014. Popular conjectures imply strong lower bounds for dynamic problems. In Proc. 55th Annual IEEE Symposium on Foundations of Computer Science.
[2]
J. Alman and V. Vassilevska Williams. A refined laser method and faster matrix multiplication. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA). Society for Industrial and Applied Mathematics, 522–539.
[3]
N. Alon, R. Yuster, and U. Zwick. 1995. Color-coding. Journal of the ACM (JACM) 42, 4 (1995), 844–856.
[4]
N. Alon, R. Yuster, and U. Zwick. 1997. Finding and counting given length cycles. Algorithmica 17, 3 (1997), 209–223.
[5]
A. L. Barabási and R. Albert. 1999. Emergence of scaling in random networks. Science. 286, 5439 (1999), 509–512.
[6]
S. K. Bera, L. Gishboliner, Y. Levanzov, C. Seshadhri, and A. Shapira. 2022. Counting subgraphs in degenerate graphs. ACM Journal of the ACM (JACM) 69, 3 (2022), 1–21.
[7]
S. K. Bera, N. Pashanasangi, and C. Seshadhri. Linear time subgraph counting, graph degeneracy, and the chasm at size six. In Proceedings of the 11th Innovations in Theoretical Computer Science Conference (ITCS’20). 38:1–38:20.
[8]
S. K. Bera, N. Pashanasangi, and C. Seshadhri. Near-linear time homomorphism counting in bounded degeneracy graphs: the barrier of long induced cycles. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA). Society for Industrial and Applied Mathematics, 2315–2332.
[9]
B. Bollobás. 1965. On generalized graphs. Acta Mathematica Academiae Scientarium Hungaricae 16, 447–452.
[10]
M. Bressan. 2021. Faster algorithms for counting subgraphs in sparse graphs. Algorithmica. 1–28.
[11]
N. Chiba and T. Nishizeki. 1985. Arboricity and subgraph listing algorithms. SIAM Journal on Computing 14, 1, (1985), 210–223.
[12]
R. Curticapean, H. Dell, and D. Marx. 2017. Homomorphisms are a good basis for counting small subgraphs. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing. 210–223.
[13]
R. Curticapean and D. Marx. 2014. Complexity of counting subgraphs: Only the boundedness of the vertex-cover number counts. In Proc. 55th Annual IEEE Symposium on Foundations of Computer Science. 130–139.
[14]
M. Dalirrooyfard, T. D. Vuong, and V. Vassilevska Williams. 2019. Graph pattern detection: Hardness for all induced patterns and faster non-induced cycles. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. 1167–1178.
[15]
V. Dalmau and P. Jonsson. 2004. The complexity of counting homomorphisms seen from the other side. Theoretical Computer Science 329, 1–3 (2004), 315–323.
[16]
F. Eisenbrand and F. Grandoni. 2003. Detecting directed 4-cycles still faster. Information Processing Letters 87, 1, (2003), 13–15.
[17]
P. Erdős, L. Lovász, and J. Spencer. 1979. Strong independence of graphcopy functions. Graph Theory and Related Topics. 165–172.
[18]
J. Flum and M. Grohe. 2002. The parameterized complexity of counting problems. In Proc. 43rd IEEE Symposium on Foundations of Computer Science. 538–547.
[19]
M. Grohe. 2007. The complexity of homomorphism and constraint satisfaction problems seen from the other side. Journal of the ACM (JACM) 54, 1 (2007), 1–24.
[20]
X. Huang and V. Y. Pan. 1998. Fast rectangular matrix multiplication and applications. Journal of Complexity 14, 2 (1998), 257–299.
[21]
A. Itai and M. Rodeh. 1978. Finding a minimum circuit in a graph. SIAM Journal on Computing 7, 4 (1978), 413–423.
[22]
A. Lincoln, V. Vassilevska Williams, and R. Williams. 2018. Tight hardness for shortest cycles and paths in sparse graphs. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms. 1236–1252
[23]
F. Le Gall. 2014. Powers of tensors and fast matrix multiplication. In International Symposium on Symbolic and Algebraic Computation (ISSAC’14). 296–303
[24]
L. Lovász. 2012. Large networks and graph limits. Providence: American Mathematical Society.
[25]
D. Marx. 2007. Can you beat treewidth?. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS’07). 169–179
[26]
D. W. Matula and L. L. Beck. 1983. Smallest-last ordering and clustering and graph coloring algorithms. Journal of the ACM (JACM) 30, 3 (1983), 417–427.
[27]
K. Meeks. 2016. The challenges of unbounded treewidth in parameterised subgraph counting problems. Discrete Applied Mathematics 198, 170–194.
[28]
R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii, and U. Alon. 2002. Network motifs: Simple building blocks of complex networks. Science 298, 5594 (2002), 824–827.
[29]
B. Monien. 1985. How to find long paths efficiently. Annals of Discrete Mathematics 25, 239–254.
[30]
J. Nešetřil and P. O. De Mendez. 2012. In Sparsity: Graphs, Structures, and Algorithms, Vol. 28. Springer Science & Business Media.
[31]
J. Nešetřil and S. Poljak. 1985. On the complexity of the subgraph problem. Commentationes Mathematicae Universitatis Carolinae 26, 2 (1985), 415–419.
[32]
N. Przulj. 2007. Biological network comparison using graphlet degree distribution. Bioinformatics 23, 2 (2007), 177–183.
[33]
S. Rudich and A. Wigderson. 2004. Computational Complexity Theory, Vol. 10. American Mathematical Soc.
[34]
V. Vassilevska Williams. 2009. Efficient algorithms for clique problems. Information Processing Letters 109, 4 (2009), 254–257.
[35]
V. Vassilevska Williams. 2012. Multiplying matrices faster than Coppersmith-Winograd. In Proceedings of the 44th Symposium on Theory of Computing Conference (STOC). 887–898.
[36]
V. Vassilevska Williams and R. Williams. 2009. Finding, minimizing, and counting weighted subgraphs. In Proc. 41st Annual ACM Symposium on the Theory of Computing. 455–464.
[37]
V. Vassilevska Williams, R. Williams, and R. Yuster. 2010. Finding heaviest \(H\) -subgraphs in real weighted graphs, with applications. ACM Transactions on Algorithms (TALG) 6, 3 (2010), 1–23.
[38]
R. Yuster and U. Zwick. 2004. Detecting short directed cycles using rectangular matrix multiplication and dynamic programming. In SODA, vol. 4. 254–260.
[39]
R. Yuster and U. Zwick. 1997. Finding even cycles even faster. SIAM Journal on Discrete Mathematics 10, 2 (1997), 209–222.
Index Terms
- Counting Homomorphic Cycles in Degenerate Graphs
Index terms have been assigned to the content through auto-classification.
Recommendations
Counting Subgraphs in Degenerate Graphs
We consider the problem of counting the number of copies of a fixed graph H within an input graph G. This is one of the most well-studied algorithmic graph problems, with many theoretical and practical applications. We focus on solving this problem when ...
Sufficient conditions for planar graphs without 4-cycles and 5-cycles to be 2-degenerate
AbstractA graph G is k-degenerate if every subgraph of G has a vertex of degree at most k. It is known that every planar graph of girth 6 (equivalently, without 3-, 4-, and 5-cycles) is 2-degenerate. On the other hand, there exist planar ...
Equimatchable Graphs on Surfaces
A graph G is equimatchable if each matching in G is a subset of a maximum-size matching and it is factor critical if G-v has a perfect matching for each vertex v of G. It is known that any 2-connected equimatchable graph is either bipartite or factor ...
Comments
Information & Contributors
Information
Published In
January 2023
254 pages
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 20 February 2023
Online AM: 06 September 2022
Accepted: 19 August 2022
Received: 28 October 2021
Published in TALG Volume 19, Issue 1
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
- ERC Consolidator
- NSF-BSF
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 488Total Downloads
- Downloads (Last 12 months)388
- Downloads (Last 6 weeks)56
Reflects downloads up to 15 Sep 2024
Other Metrics
Citations
View Options
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderHTML Format
View this article in HTML Format.
HTML FormatGet Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in