论文标题
计数退化图中的同态循环
Counting Homomorphic Cycles in Degenerate Graphs
论文作者
论文摘要
由于总体图中计数子图是一个计算要求的问题，因此自然而然地尝试为受限制的图形家庭设计快速算法。经过广泛研究的一个家庭是有界变性的图（例如平面图）。这项工作始于80年代初期，最终在Gishboliner等人的最新作品中达到了最终，该作品强调了在有限的变性图中计算周期同态循环（即循环步行）的重要性。 本文我们的主要结果是上述任务与检测（标准）在一般有向图中检测（标准）副本的良好问题之间的紧密关系。更确切地说，我们证明了以下内容： 1。一个人可以计算$ c_ {2k} $和$ c_ {2k+1} $的同构副本数量Digraphs随时间运行$ \ tilde {o}（m^{d_ {k}}）$。 2。相反，一个人可以转换任何$ o（n^{b_ {k}}）$算法用于计算$ c_ {2k} $的同构副本数量或$ c_ {2k+1} $ in $ n $ - n $ - vertex in Bougned degeneracy，$ n $ veneracy in $ c_ {用于检测一般$ m $ m $ - edge digraphs的$ c_k $的定向副本算法。 我们强调的是，我们的第一个结果不使用黑盒减少（与第二个结果相反）。取而代之的是，我们设计了一种用于计算退化图中$ c_k $ - 肌形态的数量的算法，并表明其分析的一部分可以简化为用于检测一般二分记中最快已知算法的分析，该算法是在一般的digraphs中，该算法在近期的Dalirrrooyfard and worlialroyfard and vuse and vusak and vuse and vuyns and vusack and v。
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: 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 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 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.
