Search

For every fixed k ≥ 4, it is proved that if an n-vertex directed graph has at most t pairwise arc-disjoint directed k-cycles, then there exists a set of at most 2/3 kt + o(n²) arcs that meets all directed k-cycles and that the set of k-cycles admits a fractional cover of value at most 2/3 kt. It is also proved that the ratio 2/3 k cannot be improved to a constant smaller than k/2 2. Fork = 5 the constant 2k/3 is improved to 25/8 and for k = 3 it was recently shown by Cooper et al. [European J. Combin., 101 (2022), 103462] that the constant can be taken to be 9/5. The result implies a deterministic polynomial time 2/3k-approximation algorithm for the directed k-cycle cover problem, improving upon a previous (k 1)-approximation algorithm of Kortsarz, Langberg, and Nutov, [SIAM J. Discrete Math., 24 (2010), pp. 255--269]. More generally, for every directed graph H we introduce a graph parameter f(H) for which it is proved that if an n-vertex directed graph has at most t pairwise arc-disjoint H-copies, then there exists a set of at most f(H)t + o(n²) arcs that meets all H-copies and that the set of H-copies admits a fractional cover of value at most f(H)t. It is shown that for almost all H it holds that f(H) \approx | E(H)|/2 and that for every k-vertex tournament H it holds that f(H) ≤ k²/4). [ABSTRACT FROM AUTHOR]

For a graph G$$ G $$, let ck(G)$$ {c}_k(G) $$ be the number of spanning trees of G$$ G $$ with maximum degree at most k$$ k $$. For k≥3$$ k\ge 3 $$, it is proved that every connected n$$ n $$‐vertex r$$ r $$‐regular graph G$$ G $$ with r≥nk+1$$ r\ge \frac{n}{k+1} $$ satisfies ck(G)1/n≥(1−on(1))r·zk,$$ {c}_k{(G)}^{1/n}\ge \left(1-{o}_n(1)\right)r\cdotp {z}_k, $$where zk>0$$ {z}_k>0 $$ approaches 1 extremely fast (e.g., z10=0.999971$$ {z}_{10}=0.999971 $$). The minimum degree requirement is essentially tight as for every k≥2$$ k\ge 2 $$ there are connected n$$ n $$‐vertex r$$ r $$‐regular graphs G$$ G $$ with r=⌊n/(k+1)⌋−2$$ r=\left\lfloor n/\left(k+1\right)\right\rfloor -2 $$ for which ck(G)=0$$ {c}_k(G)=0 $$. Regularity may be relaxed, replacing r$$ r $$ with the geometric mean of the degree sequence and replacing zk$$ {z}_k $$ with zk∗>0$$ {z}_k^{\ast }>0 $$ that also approaches 1, as long as the maximum degree is at most n(1−(3+ok(1))lnk/k)$$ n\left(1-\left(3+{o}_k(1)\right)\sqrt{\ln k/k}\right) $$. The same holds with no restriction on the maximum degree as long as the minimum degree is at least nk(1+ok(1))$$ \frac{n}{k}\left(1+{o}_k(1)\right) $$. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

Let T be an arbitrary phylogenetic tree with n leaves. It is well known that the average quartet distance between two assignments of taxa to the leaves of T is 23n4. However, a longstanding conjecture of Bandelt and Dress asserts that (23+o(1))n4 is also the maximum quartet distance between two assignments. While Alon, Naves, and Sudakov have shown this indeed holds for caterpillar trees, the general case of the conjecture is still unresolved. A natural extension is when partial information is given: the two assignments are known to coincide on a given subset of taxa. The partial information setting is biologically relevant as the location of some taxa (species) in the phylogenetic tree may be known, and for other taxa it might not be known. What can we then say about the average and maximum quartet distance in this more general setting? Surprisingly, even determining the average quartet distance becomes a nontrivial task in the partial information setting and determining the maximum quartet distance is even more challenging, as these turn out to be dependent on the structure of T. In this paper we prove nontrivial asymptotic bounds that are sometimes tight for the average quartet distance in the partial information setting. We also show that the Bandelt and Dress conjecture does not generally hold under the partial information setting. Specifically, we prove that there are cases where the average and maximum quartet distance substantially differ. [ABSTRACT FROM AUTHOR]