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 {\em detecting (standard) copies} of directed cycles in {\em general directed} graphs. More precisely, we prove the following: 1. One can compute the number of homomorphic copies of $C_{2k}$ and $C_{2k+1}$ in $n$-vertex graphs of bounded degeneracy in time $\tilde{O}(n^{d_{k}})$, where the fastest {\em known} algorithm for detecting directed copies of $C_k$ in general $m$-edge digraphs runs in time $\tilde{O}(m^{d_{k}})$. 2. Conversely, one can transform any $O(n^{b_{k}})$ algorithm for computing the number of homomorphic copies of $C_{2k}$ or of $C_{2k+1}$ in $n$-vertex graphs of bounded degeneracy, into an $\tilde{O}(m^{b_{k}})$ time algorithm for detecting directed copies of $C_k$ 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 $C_k$-homomorphisms in degenerate graphs and show that one part of its {\em 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.
翻译:由于在一般图形中计分子图是一个计算上要求更高的问题,所以自然会尝试和设计用于限制的图形家庭快速算法。我们本文的主要结果就是上述任务与广泛研究的闭合变异性图表(例如平面图)之间的紧密关系。这行始于80年代初期,最终是Gishboliner 等人最近的工作,这行突出了计算以美元为单位的周期(例如,周期性走法)的同质副本的重要性。 以美元为单位的离合变异性图表(例如,奥氏走法)中,以美元为单位的正价计算。 以美元为单位的平面值计算,以美元为单位的平面数字(c)中,以美元为单位的平面数字(c)中,以美元为单位的平面数字(c)中,以美元为单位的平面数字为单位,以美元为单位的平面数(c)中,以美元为单位的平面数字为单位,以美元为单位的平面图解算数。