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]

What must one do in order to make acyclic a given oriented graph? Here we look at the structures that must be removed (or reversed) in order to make acyclic a given oriented graph. For a directed acyclic graph H and an oriented graph G, let fH(G) be the maximum number of pairwise disjoint copies of H that can be found in all feedback arc sets of G. In particular, to make G acyclic, one must at least remove (or reverse) fH(G) pairwise disjoint copies of H. Perhaps most intriguing is the case where H is a k-clique, in which case the parameter is denoted by fk(G). Determining fk(G) for arbitrary G seems challenging. Here we essentially answer the problem, precisely, for the family of k-partite tournaments. Let s(G) denote the size of the smallest vertex class of a k-partite tournament G. It is not difficult to show that fk(G) \leq s(G) k + 1 (assume that s(G) geq k 1). Our main result is that for all sufficiently large s = s(G), there are k-partite tournaments for which fk(G) = s(G) k + 1. In fact, much more can be said: A random k-partite tournament G satisfies fk(G) = s(G) k + 1 almost surely (i.e., with probability tending to 1 as s(G) goes to infinity). In particular, as the title states, fk(G) = lfloor nkrfloor k +1 almost surely, where G is a random orientation of the Tur'an graph T(n, k). [ABSTRACT FROM AUTHOR]

Phylogenetic tree reconstruction is a fundamental biological problem. Quartet trees, trees over four species, are the minimal informational unit for phylogenetic classification. While every phylogenetic tree over n species defines (n4) quartets, not every set of quartets is compatible with some phylogenetic tree. Here we focus on the compatibility of quartet sets. We provide several results addressing the question of what can be inferred about the compatibility of a set from its subsets. Most of our results use probabilistic arguments to prove the sought characteristics. In particular we show that there are quartet sets Q of size m = c'n log n in which every subset of cardinality c'n/log n is compatible, and yet no fraction of more than 1/3 + ε of Q is compatible. On the other hand, in contrast to the classical result stating when Q is the densest, i.e., m = (n4 and the compatibility of any set of three quartets implies full compatibility, we show that even for m = Θn4) there are (very) incompatible sets for which every subset of large constant cardinality is compatible. Our final result relates to the conjecture of Bandelt and Dress regarding the maximum quartet distance between trees. We provide asymptotic upper and lower bounds for this value. [ABSTRACT FROM AUTHOR]

For a graph G and a fixed integer k ≥ 3, let vk(G) denote the maximum number of pairwise edge-disjoint copies of Kk in G. For a constant c, let η(k, c) be the infimum over all constants γ such that any graph G of order n and minimum degree at least cn has vk(G) ≥ γn²(1 - on(1)). By Turán's theorem, η(k, c) = 0 if c ≤ 1 - 1/(k - 1) and by Wilson's theorem, η(k, c) → 1/(k² - k) as c → 1. We prove that for any 1 > c > 1-1/(k-1), η(k, c) ≥ ..., while it is conjectured that η(k, c) = c/(k² - k) if c ≥ k/(k +1) and η(k, c) = c/2 - (k - 2)/(2k - 2) if k/(k + 1) > c > 1 - 1/(k - 1). The case k = 3 is of particular interest. In this case the bound states that for any 1 > c > 1/2, η(3, c) ≥ c/2 - c²/4c-1 . By further analyzing the case k = 3 we obtain the improved lower bound η(3, c) ≥ (12 c²-5c+2-√240 c4-216 c³+73 c²-20 c+4)(2 c-1) 32(1-c)c . This bound is always at most within a fraction of (20 - √238)/6 > 0.762 of the conjectured value, which is η(3, c) = c/6 for c ≥ 3/4 and η(3, c) = c/2 - 1/4 if 3/4 > c > 1/2. Our main tool is an analysis of the value of a natural fractional relaxation of the problem. [ABSTRACT FROM AUTHOR]

Phylogenetic tree reconstruction is a fundamental biological problem. Quartet amalgamation--combining a set of trees over four taxa into a tree over the full set of taxa--stands at the core of many phylogenetic reconstruction methods. This task has attracted many theoretical as well as practical works. However, even reconstruction from a consistent set of quartet trees is NP-hard, and the best approximation ratio known is 1/3. Despite its importance, the only rigorous results for approximating quartets are the naive 1/3 approximation that applies to the general case and a polynomial time approximation scheme (PTAS) when the input is the complete set of all (n 4) possible quartets. Even when it is possible to determine the correct quartet induced by every four taxa, the time needed to generate the complete set of all quartets may be impractical. A faster approach is to sample at random just m « (n 4) quartets and provide this sample as an input. In this work we present the first polynomial time approximation algorithm whose expected guaranteed approximation is strictly better than 1/3 when the input is any random sample of m consistent quartets. The approximation ratio of the algorithm is greater than 0.425. An important ingredient in our algorithm involves solving a weighted maximum cut problem in a certain weighted graph that corresponds to the set of input quartets. Our second main result generalizes the aforementioned PTAS algorithm to handle dense, rather than complete, inputs. [ABSTRACT FROM AUTHOR]

We give an O(n log n) algorithm for computing the girth (shortest cycle) of an undirected n-vertex planar graph. Our solution extends to any graph of bounded genus. This improves upon the best previously known algorithms for this problem. [ABSTRACT FROM AUTHOR]

A set of pairwise edge-disjoint triangles of an edge-colored Kn is r-color avoiding if it does not contain r monochromatic triangles, each having a different color. Let fr(n) be the maximum integer so that in every edge coloring of Kn with r colors, there is a set of fr(n) pairwise edge-disjoint triangles that is r-color avoiding. We prove that 0.1177n2(1 - o(1)) < f2(n) < 0.1424n2(1 + o(1)). The proof of the lower bound uses probabilistic arguments, fractional relaxation and some packing theorems. We also prove that fr(n)/n2 < 1/6 (1 - 0.145r-1) + o(1). In particular, for every r, if n is sufficiently large, there are edge colorings of Kn with r colors so that the removal of any o(n2) members from any Steiner triple system does not turn it r-color avoiding. [ABSTRACT FROM AUTHOR]

Studies the equitable coloring of k-uniform hypergraphs. Characteristics of a strong r-coloring; Double application of the nonsymmetric version of the Lovasz local lemma.

Let G = (V,E) be a connected graph. A connected dominating set S ⊂ V is a dominating set that induces a connected subgraph of G. The connected domination number of G, denoted γc(G), is the minimum cardinality of a connected dominating set. Alternatively, ∣V∣ - γc(G) is the maximum number of leaves in a spanning tree of G. Let δ denote the minimum degree of G. We prove that γc(G) ≤ ∣V∣ ln(δ+1) / δ+1 (1 + oδ(1)). Two algorithms that construct a set this good are presented. One is a sequential polynomial time algorithm, while the other is a randomized parallel algorithm in RNC. [ABSTRACT FROM AUTHOR]

We describe efficient algorithms for finding even cycles in undirected graphs. Our main results are the following: (i) For every k ≥ 2, there is an O(V²) time algorithm that decides whether an undirected graph G = (V,E) contains a simple cycle of length 2k, and finds one if it does. (ii) There is an O(V²) time algorithm that finds a shortest even cycle in an undirected graph G = (V, E). [ABSTRACT FROM AUTHOR]