Arrow Research search

Author name cluster

Raphael Yuster

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

24 papers
2 author rows

Possible papers

24

TCS Journal 2025 Journal Article

Finding and counting small tournaments in large tournaments

  • Raphael Yuster

We present new algorithms for counting and detecting small tournaments in a given tournament. In particular, we prove that every tournament on four vertices (there are four) can be detected in O ( n 2 ) time and counted in O ( n ω ) time where ω < 2. 372 is the matrix multiplication exponent. We further prove that any tournament on five vertices (there are 12) can be counted in O ( n ω + 1 ) time. As for lower-bounds, we prove that for almost all k-vertex tournaments, the complexity of the detection problem is not easier than the complexity of the corresponding well-studied counting problem for undirected cliques of order k − O ( log ⁡ k ).

Details DOI

SODA Conference 2022 Conference Paper

Counting Homomorphic Cycles in Degenerate Graphs

  • Lior Gishboliner
  • Yevgeny Levanzov
  • Asaf Shapira
  • Raphael Yuster

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

Details

TCS Journal 2020 Journal Article

A 2()n algorithm for k-cycle in minor-closed graph families

  • Raphael Yuster

Let C be a proper minor-closed family of graphs. We present a randomized algorithm that given a graph G ∈ 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.

Details DOI

TCS Journal 2014 Journal Article

Approximating the maximum consecutive subsums of a sequence

  • Ferdinando Cicalese
  • Eduardo Laber
  • Oren Weimann
  • Raphael Yuster

We present a novel approach for computing all maximum consecutive subsums in a sequence of positive integers in near-linear time. Solutions for this problem over binary sequences can be used for reporting existence of Parikh vectors in a bit string. Recently, several attempts have been made to build indexes for all Parikh vectors of a binary string in subquadratic time. However, no algorithm is known to date which can beat by more than a polylogarithmic factor the naive Θ ( n 2 ) procedure. We show how to construct a ( 1 + ϵ ) -approximate index for all Parikh vectors of a binary string in O ( n log 2 n log ( 1 + ϵ ) ) time, for any constant ϵ > 0. Such index is approximate, in the sense that it leaves a small chance for false positives (no false negatives are possible). However, we can tune the parameters of the algorithm so that we can strictly control such a chance of error while still guaranteeing strong subquadratic running time.

Details DOI

FOCS Conference 2010 Conference Paper

Replacement Paths via Fast Matrix Multiplication

  • Oren Weimann
  • Raphael Yuster

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.

Details

TCS Journal 2010 Journal Article

Single source shortest paths in H -minor free graphs

  • Raphael Yuster

We present an algorithm for the Single Source Shortest Paths (SSSP) problem in directed H -minor free graphs. For every fixed H, if G is a graph with n vertices having integer edge lengths and s is a designated source vertex of G, the algorithm runs in O ̃ ( n 11. 5 − 2 log L ) ≤ O ( n 1. 392 log L ) time, where L is the absolute value of the smallest edge length. The algorithm computes the shortest paths and the distances from s to all vertices of the graph, or else provides a certificate that G is not H -minor free. Our result improves an earlier O ( n 1. 5 log L ) time algorithm for this problem, which follows from a general SSSP algorithm of Goldberg.

Details DOI

FOCS Conference 2010 Conference Paper

Solving Linear Systems through Nested Dissection

  • Noga Alon
  • Raphael Yuster

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.

Details

TCS Journal 2008 Journal Article

All-pairs disjoint paths from a common ancestor in O ̃ ( n ω ) time

  • Raphael Yuster

A common ancestor of two vertices u, v in a directed acyclic graph is a vertex w that can reach both. A { u, v } -junction is a common ancestor w so that there are two paths, one from w to u and the other from w to v, that are internally vertex-disjoint. A lowest common ancestor (LCA) of u and v is a common ancestor w so that no other common ancestor of u and v is reachable from w. Every { u, v } -LCA is a { u, v } -junction, but the converse is not true. Similarly, not every common ancestor is a junction. The all-pairs common ancestor (APCA) problem computes (or determines the non-existence of) a common ancestor for all pairs of vertices. Similarly defined are the all-pairs junction (APJ) and the all-pairs LCA (APLCA) problems. The APCA problem also has an existence version. Bender et al. obtained an algorithm for APCA existence by reduction to transitive closure. Their algorithm runs in O ̃ ( n ω ) time where ω < 2. 376 is the exponent of fast Boolean matrix multiplication and n is the number of vertices. Kowaluk and Lingas obtained an algorithm for APLCA whose running time is O ( n 2 + 1 / ( 4 − ω ) ) ≤ o ( n 2. 616 ). Our main result is an O ̃ ( n ω ) time algorithm for APJ. Thus, junctions for all pairs can also be computed in essentially the time needed for transitive closure. For a subset of vertices S, a common ancestor of S is a vertex that can reach each vertex of S. A lowest common ancestor of S is a common ancestor w of S so that no other common ancestor of S is reachable from w. For k ≥ 2, the k -APCA and the k -APLCA problems are to find, respectively, a common ancestor and a lowest common ancestor for each k -set of vertices. We prove that for all fixed k ≥ 8, the k -APCA problem can be solved in O ̃ ( n k ) time, thereby obtaining an essentially optimal algorithm. We also prove that for all k ≥ 4, the k -APLCA problem can be solved in O ̃ ( n k + 1 / 2 ) time.

Details DOI

FOCS Conference 2008 Conference Paper

Matrix Sparsification for Rank and Determinant Computations via Nested Dissection

  • Raphael Yuster

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.

Details

STOC Conference 2007 Conference Paper

All-pairs bottleneck paths for general graphs in truly sub-cubic time

  • Virginia Vassilevska Williams
  • R. Ryan Williams
  • Raphael Yuster

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. We present the first truly sub-cubic algorithm for APBP in general dense graphs. In particular, we give a procedure for computing the (max, min)-product of two arbitrary matrices over R ∪ (∞,-∞) in O(n 2+Ω/3 ) ≤ O(n 2.792 ) time, where n is the number of vertices and Ω is the exponent for matrix multiplication over rings. Using this procedure, an explicit maximum bottleneck path for any pair of nodes can be extracted in time linear in the length of the path.

Details

MFCS Conference 2004 Conference Paper

Packing Directed Cycles Efficiently

  • Zeev Nutov
  • Raphael Yuster

Abstract Let G be a simple digraph. The dicycle packing number of G, denoted ν c ( G ), is the maximum size of a set of arc-disjoint directed cycles in G. Let G be a digraph with a nonnegative arc-weight function w. A function ψ from the set \({\cal C}\) of directed cycles in G to R + is a fractional dicycle packing of G if \(\sum_{e \in C \in {\cal C}} {\psi(C)} \leq w(e)\) for each e ∈ E ( G ). The fractional dicycle packing number, denoted ν \(_{c}^{\rm *}\) ( G, w ), is the maximum value of \(\sum_{C \in {\cal C}} \psi(C)\) taken over all fractional dicycle packings ψ. In case w ≡ 1 we denote the latter parameter by ν \(_{c}^{\rm *}\) ( G ). Our main result is that ν \(_{c}^{\rm *}\) ( G ) – ν c ( G )= o ( n 2 ) where n =| V ( G )|. Our proof is algorithmic and generates a set of arc-disjoint directed cycles whose size is at least ν c ( G )- o ( n 2 ) in randomized polynomial time. Since computing ν c ( G ) is an NP-Hard problem, and since almost all digraphs have ν c ( G )=Θ( n 2 ) our result is a FPTAS for computing ν c ( G ) for almost all digraphs. The latter result uses as its main lemma a much more general result. Let \({\cal F}\) be any fixed family of oriented graphs. For an oriented graph G, let \(\nu_{\cal F}(G)\) denote the maximum number of arc-disjoint copies of elements of \({\cal F}\) that can be found in G, and let \(\nu_{\cal F}^*(G)\) denote the fractional relaxation. Then, \(\nu_{\cal F}^*(G) - \nu_{\cal F}(G)=o(n^2)\). This lemma uses the recently discovered directed regularity lemma as its main tool. It is well known that ν \(_{c}^{\rm *}\) ( G, w ) can be computed in polynomial time by considering the dual problem. However, it was an open problem whether an optimal fractional dicycle packing ψyielding ν \(_{c}^{\rm *}\) ( G, w ) can be generated in polynomial time. We prove that a maximum fractional dicycle packing yielding ν \(_{c}^{\rm *}\) ( G, w ) with at most O ( n 2 ) dicycles receiving nonzero weight can be found in polynomial time.

Details

FOCS Conference 1992 Conference Paper

The Algorithmic Aspects of the Regularity Lemma (Extended Abstract)

  • Noga Alon
  • Richard A. Duke
  • Hanno Lefmann
  • Vojtech Rödl
  • Raphael Yuster

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/. >

Details