Abstract. For every fixed [Formula: see text], it is proved that if an [Formula: see text]-vertex directed graph has at most [Formula: see text] pairwise arc-disjoint directed [Formula: see text]-cycles, then there exists a set of at most [Formula: see text] arcs that meets all directed [Formula: see text]-cycles and that the set of [Formula: see text]-cycles admits a fractional cover of value at most [Formula: see text]. It is also proved that the ratio [Formula: see text] cannot be improved to a constant smaller than [Formula: see text]. For [Formula: see text] the constant [Formula: see text] is improved to [Formula: see text] and for [Formula: see text] it was recently shown by Cooper et al. [ European J. Combin., 101 (2022), 103462] that the constant can be taken to be [Formula: see text]. The result implies a deterministic polynomial time [Formula: see text]-approximation algorithm for the directed [Formula: see text]-cycle cover problem, improving upon a previous [Formula: see text]-approximation algorithm of Kortsarz, Langberg, and Nutov, [ SIAM J. Discrete Math., 24 (2010), pp. 255–269]. More generally, for every directed graph [Formula: see text] we introduce a graph parameter [Formula: see text] for which it is proved that if an [Formula: see text]-vertex directed graph has at most [Formula: see text] pairwise arc-disjoint [Formula: see text]-copies, then there exists a set of at most [Formula: see text] arcs that meets all [Formula: see text]-copies and that the set of [Formula: see text]-copies admits a fractional cover of value at most [Formula: see text]. It is shown that for almost all [Formula: see text] it holds that [Formula: see text] and that for every [Formula: see text]-vertex tournament [Formula: see text] it holds that [Formula: see text].

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.

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 $f_H(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) $f_H(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 $f_k(G)$. Determining $f_k(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 $f_k(G) \le s(G)-k+1$ (assume that $s(G) \ge k-1$). Our main result is that for all sufficiently large $s=s(G)$, there are $k$-partite tournaments for which $f_k(G) = s(G)-k+1$. In fact, much more can be said: A random $k$-partite tournament $G$ satisfies $f_k(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, $f_k(G) = \lfloor n/k\rfloor-k+1$ almost surely, where $G$ is a random orientation of the Turán graph $T(n,k)$.

Let ℱk be the set of all graphs on k vertices. For a graph G, a k-decomposition is a set of induced subgraphs of G, each isomorphic to an element of ℱk, such that each pair of vertices of G is in exactly one element of the set. It is a fundamental result of Wilson that for all n = |V(G)| sufficiently large, G has a k-decomposition if and only if G is k-divisible, namely k – 1 divides n – 1 and (2k) divides (2n). Let v ∊ ℝ|ℱk| be indexed by ℱk. For a k-decomposition L of G, let νv(L) = Σf∊ℱk vfdL,F where dL,F is the fraction of elements of L that are isomorphic to F. Let νv(G) = maxL νv(L) and νv(n) = min{νv (G) : |V(G)| = n} The sequence νv(n) has a limit so let νv = limn→∞ νv (n). Replacing k-decompositions with their fractional relaxations, one obtains the (polynomial time computable) fractional analogue νv*(G) and the corresponding fractional values νv*(n) and νv*. Our first main result is that for each v ∊ ℝ|ℱk| Furthermore, there is a polynomial time algorithm that produces a decomposition L of a k-decomposable graph such that νv(L) ≥ νv – on(1). A similar result holds when ℱk is the family of all tournaments on k vertices or when ℱk is the family of all edge-colorings of Kk. We use these results to obtain new and improved bounds on several decomposition results. For example, we prove that every n-vertex tournament which is 3-divisible (namely n = 1, 3 mod 6) has a triangle decomposition in which the number of directed triangles is less than 0.0222n2(1 + o(1)) and that every 5-decomposable n-vertex graph has a 5-decomposition in which the fraction of cycles of length 5 is on(1).

We present a (1 + ε)-approximation algorithm running in O ( f (ε) · n log 4 n ) time for finding the diameter of an undirected planar graph with n vertices and with nonnegative edge lengths.

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 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 = cn log n in which every subset of cardinality c′n/logn 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. the consistency of any set of 3 quartets implies full consistency, we show that even for there are (very) inconsistent sets for which every subset of large constant cardinality is consistent. 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.

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 ${n \choose 4}$ 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+\epsilon$ of $Q$ is compatible. On the other hand, in contrast to the classical result stating when $Q$ is the densest, i.e., $m={n \choose 4}$ and the compatibility of any set of three quartets implies full compatibility, we show that even for $m=\Theta\big({n \choose 4}\big)$ 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.

For a graph $G$ and a fixed integer $k \ge 3$, let $\nu_k(G)$ denote the maximum number of pairwise edge-disjoint copies of $K_k$ in $G$. For a constant $c$, let $\eta(k,c)$ be the infimum over all constants $\gamma$ such that any graph $G$ of order $n$ and minimum degree at least $cn$ has $\nu_k(G) \ge \gamma n^2(1-o_n(1))$. By Turán's theorem, $\eta(k,c)=0$ if $c \le 1-1/(k-1)$ and by Wilson's theorem, $\eta(k,c) \rightarrow 1/(k^2-k)$ as $c \rightarrow 1$. We prove that for any $1 > c > 1-1/(k-1)$, $\eta(k,c) \ge \frac{c}{2}-\frac{\big(\tbinom{k}{2}-1\big)c^{k-1}}{2\Pi_{i=1}^{k-2}((i+1)c-i)+2\big(\tbinom{k}{2}-1\big)c^{k-2}}$, while it is conjectured that $\eta(k,c) = c/(k^2-k)$ if $c \ge k/(k+1)$ and $\eta(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$, $\eta(3,c) \ge \frac{c}{2}-\frac{c^2}{4c-1}.$ By further analyzing the case $k=3$ we obtain the improved lower bound $\eta(3,c) \ge {\frac{(12\,{c}^{2}-5\,c+2-\sqrt{240\,{c}^{4}-216\,{c}^{3}+73\,{c}^{2}-20\,c+4})(2\,c-1)}{32(1-c)c}}.$ This bound is always at most within a fraction of $(20-\sqrt{238})/ 6 > 0.762$ of the conjectured value, which is $\eta(3,c)=c/6$ for $c \ge 3/4$ and $\eta(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.

The generalized nested dissection method, developed by Lipton et al. [1979], is a seminal method for solving a linear systemAx=bwhereAis a symmetric positive definite matrix. The method runs extremely fast wheneverAis a well-separable matrix (such as matrices whose underlying support is planar or avoids a fixed minor). In this work, we extend the nested dissection method to apply toanynonsingular well-separable matrix overanyfield. The running times we obtain essentially match those of the nested dissection method. An important tool is a novel method for matrix sparsification that preserves determinants and minors, and that guarantees that constant powers of the sparsified matrix remain sparse.

A distance sensitivity oracle of an n -vertex graph G = ( V , E ) is a data structure that can report shortest paths when edges of the graph fail. A query ( u ∈ V , v ∈ V , S ⊆ E ) to this oracle returns a shortest u -to- v path in the graph G ′ = ( V , E ∖ S ). We present randomized (Monte Carlo) algorithms for constructing a distance sensitivity oracle of size Õ ( n 3−α ) for | S | = O (lg n /lg lg n ) and any choice of 0 < α < 1. For real edge-lengths, the oracle is constructed in O ( n 4−α ) time and a query to this oracle takes Õ ( n 2−2(1−α)/|S| ) time. For integral edge-lengths in {− M ,..., M }, using the current ω < 2.376 matrix multiplication exponent, the oracle is constructed in O ( Mn 3.376−α ) time with Õ ( n 2−(1−α)/|S| ) query, or alternatively in O ( M 0.681 n 3.575−α ) time with Õ ( n 2−2(1−α)/|S| ) query. Distance sensitivity oracles generalize the replacement paths problem in which u and v are known in advance and | S | = 1. In other words, if P is a shortest path from u to v in G , then the replacement paths problem asks to compute, for every edge e on P , a shortest u -to- v path that avoids e . Our new technique for constructing distance sensitivity oracles using fast matrix multiplication also yields the first subcubic-time algorithm for the replacement paths problem when the edge-lengths are small integers. In particular, it yields a randomized (Monte Carlo) Õ ( Mn 2.376 + M 2 3 n 2.584 )-time algorithm for the replacement paths problem assuming M ≤ n 0.624 . Finally, we mention that both our replacement paths algorithm and our distance sensitivity oracle can be made to work, in the same time and space bounds, for the case of failed vertices rather than edges, that is, when S is a set of vertices and we seek a shortest u -to- v path in the graph obtained from G by removing all vertices in S and their adjacent edges.

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 \choose 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 \ll {n \choose 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.

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—stands at the heart 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, i.e., all quartets agree with some tree, is NP-hard, and the best approximation ratio known is $1/3$. For a dense input of $\Theta(n^4)$ quartets that are not necessarily consistent, the problem has a polynomial time approximation scheme. When the number of taxa grows, considering such dense inputs is impractical and some sampling approach is imperative. It is known that given a randomly sampled consistent set of quartets from an unknown phylogeny, one can find, in polynomial time and with high probability, a tree satisfying a $0.425$ fraction of them, an improvement over the $1/3$ ratio. In this paper we further show that given a randomly sampled consistent set of quartets from an unknown phylogeny, where the size of the sample is at least $\Theta(n^2 \log n)$, there is a randomized approximation scheme that runs in linear time in the number of quartets. The previously known polynomial approximation scheme for that problem required a very dense sample of size $\Theta(n^4)$. We note that samples of size $\Theta(n^2 \log n)$ are sparse in the full quartet set. The result is obtained by a combinatorial technique that may be of independent interest.

The generalized nested dissection method, developed by Lipton, Rose, and Tarjan, is a seminal method for solving a linear system Ax=b where A is a symmetric positive definite matrix. The method runs extremely fast whenever A is a well-separable matrix (such as matrices whose underlying support is planar or avoids a fixed minor). In this work we extend the nested dissection method to apply to any non-singular well-separable matrix over any field. The running times we obtain essentially match those of the nested dissection method.

Let G be a directed edge-weighted graph and let P be a shortest path from s to t in G. The replacement paths problem asks to compute, for every edge e on P, the shortest s-to-t path that avoids e. Apart from approximation algorithms and algorithms for special graph classes, the naive solution to this problem - removing each edge e on P one at a time and computing the shortest s-to-t path each time - is surprisingly the only known solution for directed weighted graphs, even when the weights are integrals. In particular, although the related shortest paths problem has benefited from fast matrix multiplication, the replacement paths problem has not, and still required cubic time. For an n-vertex graph with integral edge-lengths between -M and M, we give a randomized algorithm that uses fast matrix multiplication and is sub-cubic for appropriate values of M. We also show how to construct a distance sensitivity oracle in the same time bounds. A query (u,v,e) to this oracle requires sub-quadratic time and returns the length of the shortest u-to-v path that avoids the edge e. In fact, for any constant number of edge failures, we construct a data structure in sub-cubic time, that answer queries in sub-quadratic time. Our results also apply for avoiding vertices rather than edges.

The reconstruction of evolutionary trees (also known as phylogenies) is central to many problems in Biology. Accurate phylogenetic reconstruction methods are currently limited to a maximum of few dozens of species. Therefore, in order to construct a tree over larger sets of species, a method capable of inferring accurately trees over small, overlapping sets, and subsequently merging these sets into a tree over the complete set, is required. A quartet tree is the smallest informative piece of information and quartet based methods are based on combining quartet trees into a big tree. However, even this case is NP-hard, and even when the set of quartet trees is compatible (agree on a certain tree). The general problem of approximating quartets, or maximum quartet consistency (MQC), even for compatible inputs, is open for nearly twenty years. Despite its importance, the only rigorous results for approximating quartets are the naive 1/3 approximation that applies to the general case and a PTAS when the input is the complete set of all 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 quartets, and provide this sample as an input. In this work we present the first approximation algorithm whose guaranteed approximation is strictly better than 1/3 when the input is any random sample of m compatible quartets. The approximation ratio we obtain is 0.425 for general m, and 0.468 when . An important ingredient in our algorithm involves solving a weighted Max-Cut in a certain graph induced by the set of input quartets. We also show an extension of the PTAS algorithm to handle dense, rather than complete, inputs.

We present an algorithm for computing a d-dimensional subspace of the row space of a matrix. For an n×n matrix A with m nonzero entries and with rank(A) ≥ d the algorithm generates a d × n matrix with full row rank and which is a subspace of Rows(A). If rank(A) < d the algorithm generates a rank(A) × n row-equivalent matrix. The running time of the algorithm is where ω < 2.376 is the matrix multiplication exponent. An immediate corollary of the algorithm is the construction of a row-reduced equivalent matrix of A, and hence the computation of rank(A), in time We note that the running time is sub-quadratic if d < (n2/m)0.528.

A {\em parametric weighted graph} is a graph whose edges are labeled with continuous real functions of a single common variable. For any instantiation of the variable, one obtains a standard edge-weighted graph. Parametric weighted graph problems are generalizations of weighted graph problems, and arise in various natural scenarios. Parametric weighted graph algorithms consist of two phases. A {\em preprocessing phase} whose input is a parametric weighted graph, and whose output is a data structure, the advice, that is later used by the {\em instantiation phase}, where a specific value for the variable is given. The instantiation phase outputs the solution to the (standard) weighted graph problem that arises from the instantiation. The goal is to have the running time of the instantiation phase supersede the running time of any algorithm that solves the weighted graph problem from scratch, by taking advantage of the advice. In this paper we construct several parametric algorithms for the shortest path problem. For the case of linear function weights we present an algorithm for the single source shortest path problem. Its preprocessing phase runs in $\tilde{O}(V^4)$ time, while its instantiation phase runs in only $O(E+V \log V)$ time. The fastest standard algorithm for single source shortest path runs in $O(VE)$ time. For the case of weight functions defined by degree $d$ polynomials, we present an algorithm with quasi-polynomial preprocessing time $O(V^{(1 + \log f(d))\log V})$ and instantiation time only $\tilde{O}(V)$. In fact, for any pair of vertices $u,v$, the instantiation phase computes the distance from $u$ to $v$ in only $O(\log^2 V)$ time. Finally, for linear function weights, we present a randomized algorithm whose preprocessing time is $\tilde{O (V^{3.5})$ and so that for any pair of vertices $u,v$ and any instantiation variable, the instantiation phase computes, in $O(1)$ time, a length of a path from $u$ to $v$ that is at most (additively) $\epsilon$ larger than the length of a shortest path. In particular, an all-pairs shortest path solution, up to an additive constant error, can be computed in $O(V^2)$ time.

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.

For a graph G with real weights assigned to the vertices (edges), the MAX H -SUBGRAPH problem is to find an H -subgraph of G with maximum total weight, if one exists. Our main results are new strongly polynomial algorithms for the MAX H -SUBGRAPH problem. Some of our algorithms are based, in part, on fast matrix multiplication. For vertex-weighted graphs with n vertices we solve a more general problem: the all pairs MAX H -SUBGRAPH problem, where the task is to find for every pair of vertices u,v, a maximum H -subgraph containing both u and v , if one exists. We obtain an O ( n t (ω, h )) -time algorithm for the all pairs MAX H -SUBGRAPH problem in the case where H is a fixed graph with h vertices and ω < 2.376 is the exponent of matrix multiplication. The value of t (ω, h ) is determined by solving a small integer program. In particular, heaviest triangles for all pairs can be found in O ( n 2+1/(4-ω) ) ≤ o ( n 2.616 )-time. For h =4,5,8 the running time of our algorithm essentially matches that of the (unweighted) H -subgraph detection problem. Using rectangular matrix multiplication, the value of t ( ω,h ) can be improved; for example, the runtime for triangles becomes O ( n 2.575 ). We also present improved algorithms for the MAX H -SUBGRAPH problem in the edge-weighted case. In particular, we obtain an O ( m 2−1/ k log n )-time algorithm for the heaviest cycle of length 2 k or 2 k −1 in a graph with m edges and an O ( n 3 /log n )-time randomized algorithm for finding the heaviest cycle of any fixed length. Our methods also yield efficient algorithms for several related problems that are faster than any previously existing algorithms. For example, we show how to find chromatic H -subgraphs in edge-colored graphs, and how to compute the most significant bits of the distance product of two real matrices, in truly subcubic time.

Sets of permutations play an important role in the design of some efficient algorithms. In this paper we design two algorithms that manipulate sets of permutations. Both algorithms, each solving a different problem, use fast matrix multiplication techniques to achieve a significant improvement in the running time over the naive solutions. For a set of permutations P ⊂ Sn we say that i k-dominates j if the number of permutations π ∊ P for which π(i) < π(j) is k. The dominance matrix of P is the n × n matrix DP where DP(i, j) = k if and only if i k-dominates j. We give an efficient algorithm for computing DP using fast rectangular matrix multiplication. In particular, when |P| = n our algorithm runs in O(n2.684) time. Computing the dominance matrix of permutations is computationally equivalent to the dominance problem in computational geometry. Thus, our algorithm slightly improves upon a well-known O(n2.688) time algorithm of Matousek for the dominance problem. Permutation dominance is used, together with several other ingredients, to obtain a truly sub-cubic algorithm for the All Pairs Shortest Paths (APSP) problem in real-weighted directed graphs, where the number of distinct weights emanating from each vertex is O(n0.338). A special case of this algorithm implies an O(n2.842) time algorithm for real vertex-weighted APSP, which slightly improves a recent result of Chan [STOC-07]. A set of permutations P ⊆ Sn is fully expanding if the product of any two elements of P yields a distinct permutation. Stated otherwise, |P2| = |P|2 where P2 ⊂ Sn is the set of products of two elements of P. We present a randomized algorithm that computes |P2| and hence decides if P is fully expanding. The algorithm also produces a table that, for any σ1, σ2, σ3, σ4 ∊ P, answers the query σ1σ2 = σ3σ4 in time. The algorithm uses, among other ingredients, a combination of fast matrix multiplication and polynomial identity testing. In particular, for |P| = n our algorithm runs in O(nω) time where ω < 2.376 is the matrix multiplication exponent. We note that the naive deterministic solution for this problem requires ⊝(n3) time.

An edge-colored graph $G$ is {\em rainbow connected} if any two vertices are connected by a path whose edges have distinct colors. The {\em rainbow connectivity} of a connected graph $G$, denoted $rc(G)$, is the smallest number of colors that are needed in order to make $G$ rainbow connected. In addition to being a natural combinatorial problem, the rainbow connectivity problem is motivated by applications in cellular networks. In this paper we give the first proof that computing $rc(G)$ is NP-Hard. In fact, we prove that it is already NP-Complete to decide if $rc(G)=2$, and also that it is NP-Complete to decide whether a given edge-colored (with an unbounded number of colors) graph is rainbow connected. On the positive side, we prove that for every $\epsilon >0$, a connected graph with minimum degree at least $\epsilon n$ has bounded rainbow connectivity, where the bound depends only on $\epsilon$, and the corresponding coloring can be constructed in polynomial time. Additional non-trivial upper bounds, as well as open problems and conjectures are also presented.

The nested dissection method developed by Lipton, Rose, and Tarjan is a seminal method for quickly performing Gaussian elimination of symmetric real positive definite matrices whose support structure satisfies good separation properties (e.g. planar). One can use the resulting LU factorization to deduce various parameters of the matrix. The main results of this paper show that we can remove the three restrictions of being "symmetric", being "real", and being "positive definite" and still be able to compute the rank and, when relevant, also the absolute determinant, while keeping the running time of nested dissection. Our results are based, in part, on an algorithm that, given an arbitrary square matrix A of order n having m non-zero entries, creates another square matrix B of order n + 2t = O(m) with the property that each row and each column of B contains at most three nonzero entries, and, furthermore, rank(B) = rank (A) + 2t and det(B) = det(A). The running time of this algorithm is only O(m), which is optimal.

A set of pairwise edge-disjoint triangles of an edge-colored $K_n$ is r-color avoiding if it does not contain r monochromatic triangles, each having a different color. Let $f_r(n)$ be the maximum integer so that in every edge coloring of $K_n$ with r colors, there is a set of $f_r(n)$ pairwise edge-disjoint triangles that is r-color avoiding. We prove that $0.1177n^2(1-o(1))

In the all-pairs bottleneck paths (APBP) problem (a.k.a. all-pairs maximum capacity paths), one is given a directed graph with real non-negative capacities on its edges and is asked to determine, for all pairs of vertices s and t, the capacity of a single path for which a maximum amount of flow can be routed from s to t. The APBP problem was first studied in operations research, shortly after the introduction of maximum flows and all-pairs shortest paths.

The cycle packing number ν e ( G ) of a graph G is the maximum number of pairwise edge-disjoint cycles in G . Computing ν e ( G ) is an NP-hard problem. We present approximation algorithms for computing ν e ( G ) in both undirected and directed graphs. In the undirected case we analyze a variant of the modified greedy algorithm suggested by Caprara et al. [2003] and show that it has approximation ratio Θ(√log n ), where n = | V ( G )|. This improves upon the previous O (log n ) upper bound for the approximation ratio of this algorithm. In the directed case we present a √ n -approximation algorithm. Finally, we give an O ( n 2/3 )-approximation algorithm for the problem of finding a maximum number of edge-disjoint cycles that intersect a specified subset S of vertices. We also study generalizations of these problems. Our approximation ratios are the currently best-known ones and, in addition, provide upper bounds on the integrality gap of standard LP-relaxations of these problems. In addition, we give lower bounds for the integrality gap and approximability of ν e ( G ) in directed graphs. Specifically, we prove a lower bound of Ω(log n /loglog n ) for the integrality gap of edge-disjoint cycle packing. We also show that it is quasi-NP-hard to approximate ν e ( G ) within a factor of O (log 1 − ε n ) for any constant ε > 0. This improves upon the previously known APX-hardness result for this problem.

Let G = (V, E, w) be a weighted directed graph, where w : E /spl rarr/ {-M, ..., 0, ..., M}. We show that G can be preprocessed in O/spl tilde/(Mn/sup /spl omega//) time, where /spl omega/n/sup /spl omega/- 1/2 / /spl sime/ n/sup 1.876/.

Let A and B two n × n matrices over a ring R (e.g., the reals or the integers) each containing at most m nonzero elements. We present a new algorithm that multiplies A and B using O ( m 0.7 n 1.2 + n 2+ o (1) ) algebraic operations (i.e., multiplications, additions and subtractions) over R . The naïve matrix multiplication algorithm, on the other hand, may need to perform Ω( mn ) operations to accomplish the same task. For m ≤ n 1.14 , the new algorithm performs an almost optimal number of only n 2+ o (1) operations. For m ≤ n 1.68 , the new algorithm is also faster than the best known matrix multiplication algorithm for dense matrices which uses O ( n 2.38 ) algebraic operations. The new algorithm is obtained using a surprisingly straightforward combination of a simple combinatorial idea and existing fast rectangular matrix multiplication algorithms. We also obtain improved algorithms for the multiplication of more than two sparse matrices. As the known fast rectangular matrix multiplication algorithms are far from being practical, our result, at least for now, is only of theoretical value.

Let H be a k-uniform hypergraph with n vertices. A strong r-coloring is a partition of the vertices into r parts such that each edge of H intersects each part. A strong r-coloring is called equitable if the size of each part is $\lceil n/r \rceil$ or $\lfloor n/r \rfloor$. We prove that for all $a \geq 1$, if the maximum degree of H satisfies $\Delta(H) \leq k^a$, then H has an equitable coloring with $\frac{k}{a \ln k}(1-o_k(1))$ parts. In particular, every k-uniform hypergraph with maximum degree O(k) has an equitable coloring with $\frac{k}{\ln k}(1-o_k(1))$ parts. The result is asymptotically tight. The proof uses a double application of the nonsymmetric version of the Lovász local lemma.

Let G=(V,E) be a connected graph. A connected dominating set $S \subset V$ is a dominating set that induces a connected subgraph of G. The connected domination number of G, denoted $\gamma_c(G)$, is the minimum cardinality of a connected dominating set. Alternatively, $|V|-\gamma_c(G)$ is the maximum number of leaves in a spanning tree of G. Let $\delta$ denote the minimum degree of G. We prove that $\gamma_c(G) \leq |V| \frac{\ln(\delta+1)}{\delta+1}(1+o_\delta(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.

We describe efficient algorithms for finding even cycles in undirected graphs. Our main results are the following: (i) For every $k \geq 2$, there is an $O(V^2)$ 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^2)$ time algorithm that finds a shortest even cycle in an undirected graph $G=(V,E)$.

We describe a novel randomized method.the method of cobm-coding for finding simple paths and cycles of a specified length k, and other small subgraphs, within a gwen graph G = ( 1', E).The randomized algorithms obtained using this method can be derandomlzcd using kmihes of petfect hash f~wtctmns.Using the color-coding method we obtain.m particular, the following new results:-For every fixed k, if a graph G = (V.E) contains a simple cycle of size exactly k, then such a cycle can be found m either 0( V'") expected time or 0( L'"' log P') worst-case t]mc, where w < ?,376 ]s the exponent of matrrx multiplication.(Here and in what follows we use V and E instead of Ib' and IEI whenever no confusion may arise.)-For every fwed k, if a planar graph G = (P-, E) contains a simple cycle of size e.wrctly k, then such a cycle cmr be found m either 0(V) expected time or 0( V log V ) worst-case time.The same algorithm applies, in fact, not only to planar gmphs, but to any mino~closed family of graphs which is not the f~mily of all graphs, -If a grdph G = (V, E) contains a subgraph isomorphic to a boanded tree-width graph H = ( V~, E~) where IV, I = O(log V), then such a copy of H can be found in polyzonzml tune.This was not prewously known even if H were Just a path of length O(log V).These results improve upon previous results of many authors.The third result resolves in the affirmative a conjecture of Papadimltnou and Yannakakis that the LOG PATH problem is m P. We can show that it is even in NC.

We describe a novel randomized method, the method of color-coding for finding simple paths and cycles of a specified length k, and other small subgraphs, within a given graph G = (V,E). The randomized algorithms obtained using this method can be derandomized using families of perfect hash functions. Using the color-coding method we obtain, among others, the following new results: • For every fixed k, if a graph G = (V,E) contains a simple cycle of size exactly k, then such a cycle can be found in either O(V ω) expected time or O(V ω log V ) worst-case time, where ω < 2.376 is the exponent of matrix multiplication. (Here and in what follows we use V and E instead of |V | and |E| whenever no confusion may arise.) • For every fixed k, if a planar graph G = (V,E) contains a simple cycle of size exactly k, then ∗Work supported in part by The basic research foundation administrated by The Israel academy of sciences and humanities and by grant No. 93-6-6 of the Sloan foundation. †Institute for Advanced study, school of Mathematics, Princeton, NJ 08540, USA. ‡School of Mathematical Sciences, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv 69978, ISRAEL. E-mail addresses of authors: {noga,raphy,zwick}@math.tau.ac.il. such a cycle can be found in either O(V ) expected time or O(V log V ) worst-case time. The same algorithm applies, in fact, not only to planar graphs, but to any minor closed family of graphs which is not the family of all graphs. • If a graph G = (V,E) contains a subgraph isomorphic to a bounded tree-width graph H = (VH , EH) where |VH | = O(log V ), then such a copy of H can be found in polynomial time. This was not previously known even if H were just a path of length O(log V ). These results improve upon previous results of many authors. The third result resolves in the affirmative a conjecture of Papadimitriou and Yannakakis that the LOG PATH problem is in P. We can even show that the LOG PATH problem is in NC.

The regularity lemma of Szemeredi (1978) is a result that asserts that every graph can be partitioned in a certain regular way. This result has numerous applications, but its known proof is not algorithmic. The authors first demonstrate the computational difficulty of finding a regular partition; they show that deciding if a given partition of an input graph satisfies the properties guaranteed by the lemma is co-NP-complete. However, they also prove that despite this difficulty the lemma can be made constructive; they show how to obtain, for any input graph, a partition with the properties guaranteed by the lemma, efficiently. The desired partition, for an n-vertex graph, can be found in time O(M(n)), where M(n)=O(n/sup 2.376/) is the time needed to multiply two n by n matrices with 0,1-entries over the integers. The algorithm can be parallelized and implemented in NC/sup 1/.>