Source author record

Raphael Yuster

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Data Structures and Algorithms Computational Complexity

Catalog footprint

Research overview

19works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Counting Homomorphic Cycles in Degenerate Graphs

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: 1. One can compute the number of homomorphic copies of $C_{2k}$ and $C_{2k+1}$ in $n$ -vertex 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}})$ . 2. 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 $\tilde{O}(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.

preprint2022arXiv

Hamiltonian cycles above expectation in r-graphs and quasi-random r-graphs

Let $H_r(n,p)$ denote the maximum number of Hamiltonian cycles in an $n$ -vertex $r$ -graph with density $p \in (0,1)$ . The expected number of Hamiltonian cycles in the random $r$ -graph model $G_r(n,p)$ is $E(n,p)=p^n(n-1)!/2$ and in the random graph model $G_r(n,m)$ with $m=p\binom{n}{r}$ it is, in fact, slightly smaller than $E(n,p)$ . For graphs, $H_2(n,p)$ is proved to be only larger than $E(n,p)$ by a polynomial factor and it is an open problem whether a quasi-random graph with density $p$ can be larger than $E(n,p)$ by a polynomial factor. For hypergraphs (i.e. $r \ge 3$ ) the situation is drastically different. For all $r \ge 3$ it is proved that $H_r(n,p)$ is larger than $E(n,p)$ by an {\em exponential} factor and, moreover, there are quasi-random $r$ -graphs with density $p$ whose number of Hamiltonian cycles is larger than $E(n,p)$ by an exponential factor.

preprint2022arXiv

The covering threshold of a directed acyclic graph by directed acyclic subgraphs

Let $H$ be a directed acyclic graph other than a rooted star. It is known that there are constants $c(H)$ and $C(H)$ such that the following holds for the complete directed graph $D_n$ . There are at most $C\log n$ directed acyclic subgraphs of $D_n$ that cover every $H$ -copy of $D_n$ , while fewer than $c\log n$ directed acyclic subgraphs of $D_n$ do not cover all $H$ -copies. Here this dichotomy is considerably strengthened. Let ${\vec G}(n,p)$ denote the random directed graph. The {\em fractional arboricity} of $H$ is $a(H) = max \{\frac{|E(H')|}{|V(H')|-1}\}$ , where the maximum is over all non-singleton subgraphs of $H$ . If $a(H) = \frac{|E(H)|}{|V(H)|-1}$ then $H$ is {\em totally balanced}. Complete graphs, complete multipartite graphs, cycles, trees, and, in fact, almost all graphs, are totally balanced. It is proved: 1) Let $H$ be a dag with $h$ vertices and $m$ edges other than a rooted star. For every $a^* > a(H)$ there exists $c^* = c^*(a^*,H) > 0$ such that almost surely $G \sim {\vec G}(n,n^{-1/a^*})$ has the property that every set $X$ of at most $c^*\log n$ directed acyclic subgraphs of $G$ does not cover all $H$ -copies of $G$ . Moreover, there exists $s(H) = m/2 + O(m^{4/5}h^{1/5})$ such that the following stronger assertion holds for any such $X$ : There is an $H$ -copy in $G$ that has no more than $s(H)$ of its edges covered by each element of $X$ . 2) If $H$ is totally balanced then for every $0 < a^* < a(H)$ , almost surely $G \sim {\vec G}(n,n^{-1/a^*})$ has a single directed acyclic subgraph that covers all its $H$ -copies. As for the first result, note that if $h=o(m)$ then $s(H)=(1+o_m(1))m/2$ is about half of the edges of $H$ . In fact, for infinitely many $H$ it holds that $s(H)=m/2$ , optimally. As for the second result, the requirement that $H$ is totally balanced cannot, generally, be relaxed.

preprint2022arXiv

The number of bounded-degree spanning trees

For a graph $G$ , let $c_k(G)$ be the number of spanning trees of $G$ with maximum degree at most $k$ . For $k \ge 3$ , it is proved that every connected $n$ -vertex $r$ -regular graph $G$ with $r \ge \frac{n}{k+1}$ satisfies $c_k(G)^{1/n} \ge (1-o_n(1)) r \cdot z_k$ where $z_k > 0$ approaches $1$ extremely fast (e.g. $z_{10}=0.999971$ ). The minimum degree requirement is essentially tight as for every $k \ge 2$ there are connected $n$ -vertex $r$ -regular graphs $G$ with $r=\lfloor n/(k+1) \rfloor -2$ for which $c_k(G)=0$ . Regularity may be relaxed, replacing $r$ with the geometric mean of the degree sequence and replacing $z_k$ with $z_k^* > 0$ that also approaches $1$ , as long as the maximum degree is at most $n(1-(3+o_k(1))\sqrt{\ln k/k})$ . The same holds with no restriction on the maximum degree as long as the minimum degree is at least $\frac{n}{k}(1+o_k(1))$ .

preprint2021arXiv

Sum-distinguishing number of sparse hypergraphs

A vertex labeling of a hypergraph is sum distinguishing if it uses positive integers and the sums of labels taken over the distinct hyperedges are distinct. Let s(H) be the smallest integer N such that there is a sum-distinguishing labeling of H with each label at most N. The largest value of s(H) over all hypergraphs on n vertices and m hyperedges is denoted s(n,m). We prove that s(n,m) is almost-quadratic in m as long as m is not too large. More precisely, the following holds: If n < m < n^{O(1)} then s(n,m)= m^2/w(m), where w(m) is a function that goes to infinity and is smaller than any polynomial in m. The parameter s(n,m) has close connections to several other graph and hypergraph functions, such as the irregularity strength of hypergraphs. Our result has several applications, notably: 1. We answer a question of Gyarfas et al. whether there are n-vertex hypergraphs with irregularity strength greater than 2n. In fact we show that there are n-vertex hypergraphs with irregularity strength at least n^{2-o(1)}. 2. Our results imply that s*(n)=n^2/w(n) where s*(n) is the distinguishing closed-neighborhood number, i.e., the smallest integer N such that any n-vertex graph allows for a vertex labeling with positive integers at most N so that the sums of labels on distinct closed neighborhoods of vertices are distinct.

preprint2020arXiv

A $2^{O(k)}n$ algorithm for $k$ -cycle in minor-closed graph families

Let ${\mathcal C}$ be a proper minor-closed family of graphs. We present a randomized algorithm that given a graph $G \in {\mathcal C}$ with $n$ vertices, finds a simple cycle of size $k$ in $G$ (if exists) in $2^{O(k)}n$ time. The algorithm applies to both directed and undirected graphs. In previous linear time algorithms for this problem, the runtime dependence on $k$ is super-exponential. The algorithm can be derandomized yielding a $2^{O(k)}n\log n$ time algorithm.

preprint2020arXiv

Dominant tournament families

For a tournament $H$ with $h$ vertices, its typical density is $h!2^{-\binom{h}{2}}/aut(H)$ , i.e. this is the expected density of $H$ in a random tournament. A family ${\mathcal F}$ of $h$ -vertex tournaments is {\em dominant} if for all sufficiently large $n$ , there exists an $n$ -vertex tournament $G$ such that the density of each element of ${\mathcal F}$ in $G$ is larger than its typical density by a constant factor. Characterizing all dominant families is challenging already for small $h$ . Here we characterize several large dominant families for every $h$ . In particular, we prove the following for all $h$ sufficiently large: (i) For all tournaments $H^*$ with at least $5\log h$ vertices, the family of all $h$ -vertex tournaments that contain $H^*$ as a subgraph is dominant. (ii) The family of all $h$ -vertex tournaments whose minimum feedback arc set size is at most $\frac{1}{2}\binom{h}{2}-h^{3/2}\sqrt{\ln h}$ is dominant. For small $h$ , we construct a dominant family of $6$ (i.e. $50\%$ of the) tournaments on $5$ vertices and dominant families of size larger than $40\%$ for $h=6,7,8,9$ . For all $h$ , we provide an explicit construction of a dominant family which is conjectured to obtain an absolute constant fraction of the tournaments on $h$ vertices. Some additional intriguing open problems are presented.

preprint2020arXiv

Perfect sequence covering arrays

An $(n,k)$ sequence covering array is a set of permutations of $[n]$ such that each sequence of $k$ distinct elements of $[n]$ is a subsequence of at least one of the permutations. An $(n,k)$ sequence covering array is perfect if there is a positive integer $λ$ such that each sequence of $k$ distinct elements of $[n]$ is a subsequence of precisely $λ$ of the permutations. While relatively close upper and lower bounds for the minimum size of a sequence covering array are known, this is not the case for perfect sequence covering arrays. Here we present new nontrivial bounds for the latter. In particular, for $k=3$ we obtain a linear lower bound and an almost linear upper bound.

preprint2015arXiv

On the maximum number of spanning copies of an orientation in a tournament

For an orientation $H$ with $n$ vertices, let $T(H)$ denote the maximum possible number of labeled copies of $H$ in an $n$ -vertex tournament. It is easily seen that $T(H) \ge n!/2^{e(H)}$ as the latter is the expected number of such copies in a random tournament. For $n$ odd, let $R(H)$ denote the maximum possible number of labeled copies of $H$ in an $n$ -vertex regular tournament. Adler et al. proved that, in fact, for $H=C_n$ the directed Hamilton cycle, $T(C_n) \ge (e-o(1))n!/2^{n}$ and it was observed by Alon that already $R(C_n) \ge (e-o(1))n!/2^{n}$ . Similar results hold for the directed Hamilton path $P_n$ . In other words, for the Hamilton path and cycle, the lower bound derived from the expectation argument can be improved by a constant factor. In this paper we significantly extend these results and prove that they hold for a larger family of orientations $H$ which includes all bounded degree Eulerian orientations and all bounded degree balanced orientations, as well as many others. One corollary of our method is that for any $k$ -regular orientation $H$ with $n$ vertices, $T(H) \ge (e^k-o(1))n!/2^{e(H)}$ and in fact, for $n$ odd, $R(H) \ge (e^k-o(1))n!/2^{e(H)}$ .

preprint2015arXiv

Ramsey numbers for degree monotone paths

A path $v_1,v_2,\ldots,v_m$ in a graph $G$ is $degree$ - $monotone$ if $deg(v_1) \leq deg(v_2) \leq \cdots \leq deg(v_m)$ where $deg(v_i)$ is the degree of $v_i$ in $G$ . Longest degree-monotone paths have been studied in several recent papers. Here we consider the Ramsey type problem for degree monotone paths. Denote by $M_k(m)$ the minimum number $M$ such that for all $n \geq M$ , in any $k$ -edge coloring of $K_n$ there is some $1\leq j \leq k$ such that the graph formed by the edges colored $j$ has a degree-monotone path of order $m$ . We prove several nontrivial upper and lower bounds for $M_k(m)$ .

preprint2014arXiv

The Turán number of sparse spanning graphs

For a graph $H$ , the {\em extremal number} $ex(n,H)$ is the maximum number of edges in a graph of order $n$ not containing a subgraph isomorphic to $H$ . Let $δ(H)>0$ and $Δ(H)$ denote the minimum degree and maximum degree of $H$ , respectively. We prove that for all $n$ sufficiently large, if $H$ is any graph of order $n$ with $Δ(H) \le \sqrt{n}/200$ , then $ex(n,H)={{n-1} \choose 2}+δ(H)-1$ . The condition on the maximum degree is tight up to a constant factor. This generalizes a classical result of Ore for the case $H=C_n$ , and resolves, in a strong form, a conjecture of Glebov, Person, and Weps for the case of graphs. A counter-example to their more general conjecture concerning the extremal number of bounded degree spanning hypergraphs is also given.

preprint2013arXiv

Approximating the Diameter of Planar Graphs in Near Linear Time

We present a $(1+ε)$ -approximation algorithm running in $O(f(ε)\cdot n \log^4 n)$ time for finding the diameter of an undirected planar graph with non-negative edge lengths.

preprint2013arXiv

Forcing $k$ -repetitions in degree sequences

One of the most basic results in graph theory states that every graph with at least two vertices has two vertices with the same degree. Since there are graphs without $3$ vertices of the same degree, it is natural to ask if for any fixed $k$ , every graph $G$ is ``close'' to a graph $G'$ with $k$ vertices of the same degree. Our main result in this paper is that this is indeed the case. Specifically, we show that for any positive integer $k$ , there is a constant $C=C(k)$ , so that given any graph $G$ , one can remove from $G$ at most $C$ vertices and thus obtain a new graph $G'$ that contains at least $\min\{k,|G|-C\}$ vertices of the same degree. Our main tool is a multidimensional zero-sum theorem for integer sequences, which we prove using an old geometric approach of Alon and Berman.

preprint2012arXiv

Large feedback arc sets, high minimum degree subgraphs, and long cycles in Eulerian digraphs

A minimum feedback arc set of a directed graph $G$ is a smallest set of arcs whose removal makes $G$ acyclic. Its cardinality is denoted by $β(G)$ . We show that an Eulerian digraph with $n$ vertices and $m$ arcs has $β(G) \ge m^2/2n^2+m/2n$ , and this bound is optimal for infinitely many $m, n$ . Using this result we prove that an Eulerian digraph contains a cycle of length at most $6n^2/m$ , and has an Eulerian subgraph with minimum degree at least $m^2/24n^3$ . Both estimates are tight up to a constant factor. Finally, motivated by a conjecture of Bollobás and Scott, we also show how to find long cycles in Eulerian digraphs.

preprint2011arXiv

Computing the diameter polynomially faster than APSP

We present a new randomized algorithm for computing the diameter of a weighted directed graph. The algorithm runs in $\Ot(M^{\w/(\w+1)}n^{(\w^2+3)/(\w+1)})$ time, where $\w < 2.376$ is the exponent of fast matrix multiplication, $n$ is the number of vertices of the graph, and the edge weights are integers in $\{-M,...,0,...,M\}$ . For bounded integer weights the running time is $O(n^{2.561})$ and if $\w=2+o(1)$ it is $\Ot(n^{7/3})$. This is the first algorithm that computes the diameter of an integer weighted directed graph polynomially faster than any known All-Pairs Shortest Paths (APSP) algorithm. For bounded integer weights, the fastest algorithm for APSP runs in $O(n^{2.575})$ time for the present value of $\w$ and runs in $\Ot(n^{2.5})$ time if $\w=2+o(1)$. For directed graphs with {\em positive} integer weights in $\{1,...,M\}$ we obtain a deterministic algorithm that computes the diameter in $\Ot(Mn^\w)$ time. This extends a simple $\Ot(n^\w)$ algorithm for computing the diameter of an {\em unweighted} directed graph to the positive integer weighted setting and is the first algorithm in this setting whose time complexity matches that of the fastest known Diameter algorithm for {\em undirected} graphs. The diameter algorithms are consequences of a more general result. We construct algorithms that for any given integer $d$ , report all ordered pairs of vertices having distance {\em at most} $d$ . The diameter can therefore be computed using binary search for the smallest $d$ for which all pairs are reported.

preprint2010arXiv

Dense graphs with a large triangle cover have a large triangle packing

It is well known that a graph with $m$ edges can be made triangle-free by removing (slightly less than) $m/2$ edges. On the other hand, there are many classes of graphs which are hard to make triangle-free in the sense that it is necessary to remove roughly $m/2$ edges in order to eliminate all triangles. It is proved that dense graphs that are hard to make triangle-free, have a large packing of pairwise edge-disjoint triangles. In particular, they have more than $m(1/4+cβ^2)$ pairwise edge-disjoint triangles where $β$ is the density of the graph and $c$ is an absolute constant. This improves upon a previous $m(1/4-o(1))$ bound which follows from the asymptotic validity of Tuza's conjecture for dense graphs. It is conjectured that such graphs have an asymptotically optimal triangle packing of size $m(1/3-o(1))$ . The result is extended to larger cliques and odd cycles.

preprint2010arXiv

On the size of dissociated bases

We prove that the sizes of the maximal dissociated subsets of a given finite subset of an abelian group differ by a logarithmic factor at most. On the other hand, we show that the set $\{0,1\}^n\seq\Z^n$ possesses a dissociated subset of size $\Ome(n\log n)$; since the standard basis of $\Z^n$ is a maximal dissociated subset of $\{0,1\}^n$ of size $n$ , the result just mentioned is essentially sharp.

preprint2010arXiv

The Quasi-Randomness of Hypergraph Cut Properties

Let a_1,...,a_k satisfy a_1+...+a_k=1 and suppose a k-uniform hypergraph on n vertices satisfies the following property; in any partition of its vertices into k sets A_1,...,A_k of sizes a_1*n,...,a_k*n, the number of edges intersecting A_1,...,A_k is the number one would expect to find in a random k-uniform hypergraph. Can we then infer that H is quasi-random? We show that the answer is negative if and only if a_1=...=a_k=1/k. This resolves an open problem raised in 1991 by Chung and Graham [J. AMS '91]. While hypergraphs satisfying the property corresponding to a_1=...=a_k=1/k are not necessarily quasi-random, we manage to find a characterization of the hypergraphs satisfying this property. Somewhat surprisingly, it turns out that (essentially) there is a unique non quasi-random hypergraph satisfying this property. The proofs combine probabilistic and algebraic arguments with results from the theory of association schemes.

preprint2010arXiv

Two-phase algorithms for the parametric shortest path problem

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.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Raphael Yuster

Research overview

Is this your work?

19 publications

Counting Homomorphic Cycles in Degenerate Graphs

Hamiltonian cycles above expectation in r-graphs and quasi-random r-graphs

The covering threshold of a directed acyclic graph by directed acyclic subgraphs

The number of bounded-degree spanning trees

Sum-distinguishing number of sparse hypergraphs

A $2^{O(k)}n$ algorithm for $k$ -cycle in minor-closed graph families

Dominant tournament families

Perfect sequence covering arrays

On the maximum number of spanning copies of an orientation in a tournament

Ramsey numbers for degree monotone paths

The Turán number of sparse spanning graphs

Approximating the Diameter of Planar Graphs in Near Linear Time

Forcing $k$ -repetitions in degree sequences

Large feedback arc sets, high minimum degree subgraphs, and long cycles in Eulerian digraphs

Computing the diameter polynomially faster than APSP

Dense graphs with a large triangle cover have a large triangle packing

On the size of dissociated bases

The Quasi-Randomness of Hypergraph Cut Properties

Two-phase algorithms for the parametric shortest path problem

See the researcher in context

Building this map preview

Raphael Yuster

Research overview

Is this your work?

19 publications

Counting Homomorphic Cycles in Degenerate Graphs

Hamiltonian cycles above expectation in r-graphs and quasi-random r-graphs

The covering threshold of a directed acyclic graph by directed acyclic subgraphs

The number of bounded-degree spanning trees

Sum-distinguishing number of sparse hypergraphs

A 2O(k)n2^{O(k)}n2O(k)n algorithm for kkk-cycle in minor-closed graph families

Dominant tournament families

Perfect sequence covering arrays

On the maximum number of spanning copies of an orientation in a tournament

Ramsey numbers for degree monotone paths

The Turán number of sparse spanning graphs

Approximating the Diameter of Planar Graphs in Near Linear Time

Forcing kkk-repetitions in degree sequences

Large feedback arc sets, high minimum degree subgraphs, and long cycles in Eulerian digraphs

Computing the diameter polynomially faster than APSP

Dense graphs with a large triangle cover have a large triangle packing

On the size of dissociated bases

The Quasi-Randomness of Hypergraph Cut Properties

Two-phase algorithms for the parametric shortest path problem

See the researcher in context

Building this map preview

A $2^{O(k)}n$ algorithm for $k$ -cycle in minor-closed graph families

Forcing $k$ -repetitions in degree sequences