Talk information
Date: Sunday, November 21, 2021
Time: 10:10–11:00
Place: Schreiber 309
Speaker: Yevgeny Levanzov (Tel Aviv University)
Title: Counting Homomorphic Cycles in Degenerate Graphs
Abstract:
Since counting subgraphs in general graphs is a computationally demanding problem, it is natural to try and design fast algorithms for restricted families of graphs. One such family is that of graphs of bounded degeneracy. This line of work, which started in the 80’s, culminated in a recent work of Gishboliner et al., which highlighted the importance of the task of counting homomorphic copies of cycles.
Our main result is a surprisingly tight relation between the above task and the problem of detecting copies of directed cycles in general directed graphs. We prove the following:
- One can compute the number of homomorphic copies of $C_{2k}$ and $C_{2k+1}$ in 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}})$.
- 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 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.
Joint work with Lior Gishboliner, Asaf Shapira and Raphael Yuster.