Abstract. Graph modification problems ask for the minimal number of vertex/edge additions/deletions needed to make a graph satisfy some predetermined property. A (meta-)problem of this type, which was raised by Yannakakis in 1981, asks to determine for which properties [Formula: see text] it is NP-hard to compute the smallest number of edge deletions needed to make a graph satisfy [Formula: see text]. Despite being extensively studied in the past 40 years, this problem is still wide open. In fact, it is open even when [Formula: see text] is the property of being [Formula: see text]-free, for some fixed graph [Formula: see text]. In this case we use [Formula: see text] to denote the smallest number of edge deletions needed to turn [Formula: see text] into an [Formula: see text]-free graph. Alon, Shapira, and Sudakov proved that if [Formula: see text] is not bipartite, then computing [Formula: see text] is NP-hard. They left open the problem of classifying the bipartite graphs [Formula: see text] for which computing [Formula: see text] is NP-hard. In this paper we resolve this problem when [Formula: see text] is a forest, showing that computing [Formula: see text] is polynomial-time solvable if [Formula: see text] is a star forest and NP-hard otherwise. Our main innovation in this work lies in introducing a new graph-theoretic approach for Yannakakis’s problem, which differs significantly from all prior works on this subject. In particular, we prove new results concerning an old and famous conjecture of Erdős and Sós, which are of independent interest.

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 C 2k and C 2k+1 in n -vertex graphs of bounded degeneracy in time Õ( n d k ), where the fastest known algorithm for detecting directed copies of C k in general m -edge digraphs runs in time Õ( m d k ). 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 Õ( 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. 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.

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 , where the fastest known algorithm for detecting directed copies of Ck in general m-edge digraphs runs in time . Conversely, one can transform any algorithm for computing the number of homomorphic copies of C2k or of C2k+1 in n-vertex graphs of bounded degeneracy, into an 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.

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 the input G has bounded degeneracy . This is a rich family of graphs, containing all graphs without a fixed minor (e.g., planar graphs), as well as graphs generated by various random processes (e.g., preferential attachment graphs). We say that H is easy if there is a linear-time algorithm for counting the number of copies of H in an input G of bounded degeneracy. A seminal result of Chiba and Nishizeki from ’85 states that every H on at most 4 vertices is easy. Bera, Pashanasangi, and Seshadhri recently extended this to all H on 5 vertices and further proved that for every \( k \gt 5 \) there is a k -vertex H which is not easy. They left open the natural problem of characterizing all easy graphs H . Bressan has recently introduced a framework for counting subgraphs in degenerate graphs, from which one can extract a sufficient condition for a graph H to be easy. Here, we show that this sufficient condition is also necessary, thus fully answering the Bera–Pashanasangi–Seshadhri problem. We further resolve two closely related problems; namely characterizing the graphs that are easy with respect to counting induced copies, and with respect to counting homomorphisms.