Arrow Research search

Author name cluster

Michael Krivelevich

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.

17 papers
1 author row

Possible papers

17

STOC Conference 2025 Conference Paper

Disjoint Connected Dominating Sets in Pseudorandom Graphs

  • Nemanja Draganic
  • Michael Krivelevich

A connected dominating set (CDS) in a graph is a dominating set of vertices that induces a connected subgraph. Having many disjoint CDSs in a graph can be considered as a measure of its connectivity, and has various graph-theoretic and algorithmic implications. We show that d -regular (weakly) pseudoreandom graphs contain (1+ o (1)) d /ln d disjoint CDSs, which is asymptotically best possible. In particular, this implies that random d -regular graphs typically contain (1+ o (1)) d /ln d disjoint CDSs.

Details

SODA Conference 2021 Conference Paper

Rolling backwards can move you forward: on embedding problems in sparse expanders

  • Nemanja Draganic
  • Michael Krivelevich
  • Rajko Nenadov

We develop a general embedding method based on the Friedman-Pippenger tree embedding technique (1987) and its algorithmic version, essentially due to Aggarwal et al. (1996), enhanced with a roll-back idea allowing to sequentially retrace previously performed embedding steps. This proves to be a powerful tool for embedding graphs of large girth into expander graphs. As an application of this method, we settle two problems: • For a graph H, we denote by H q the graph obtained from H by subdividing its edges with q –1 vertices each. We show that the k -size-Ramsey number Ŗ k ( H q ) satisfies Ŗ k ( H q ) = O ( qn ) for every bounded degree graph H on n vertices and for q = Ω(log n ), which is optimal up to a constant factor. This settles a conjecture of Pak (2002). • We give a deterministic, polynomial time algorithm for finding vertex-disjoint paths between given pairs of vertices in a strong expander graph. More precisely, let G be an ( n, d, λ )-graph with λ = O ( d 1 – ∊ ), and let be any collection of at most disjoint pairs of vertices in G for some small constant c, such that in the neighborhood of every vertex in G there are at most d/ 4 vertices from. Then there exists a polynomial time algorithm which finds vertex-disjoint paths between every pair in, and each path is of the same length. Both the number of pairs and the length of the paths are optimal up to a constant factor; the result answers the offline version of a question of Alon and Capalbo (2007).

Details

SODA Conference 2015 Conference Paper

Contagious Sets in Expanders

  • Amin Coja-Oghlan
  • Uriel Feige
  • Michael Krivelevich
  • Daniel Reichman 0001

We consider the following activation process in undirected graphs: a vertex is active either if it belongs to a set of initially activated vertices or if at some point it has at least r active neighbors, where r > 1 is the activation threshold. A contagious set is a set whose activation results with the entire graph being active. Given a graph G, let m ( G, r ) be the minimal size of a contagious set. It is known that for every d -regular or nearly d -regular graph on n vertices, . We consider such graphs that additionally have expansion properties, parameterized by the spectral gap and/or the girth of the graphs. The general flavor of our results is that sufficiently strong expansion properties imply that (and more generally, . In addition, we demonstrate that rather weak assumptions on the girth and/or the spectral gap suffice in order to imply that. For example, we show this for graphs of girth at least 7, and for graphs with λ( G ) < (1 − ε ) d, provided the graph has no 4-cycles. Our results are algorithmic, entailing simple and effcient algorithms for selecting contagious sets.

Details

SODA Conference 2009 Conference Paper

On smoothed k -CNF formulas and the Walksat algorithm

  • Amin Coja-Oghlan
  • Uriel Feige
  • Alan M. Frieze
  • Michael Krivelevich
  • Dan Vilenchik

In this paper we study the model of ∊ -smoothed k -CNF formulas. Starting from an arbitrary instance F with n variables and m = dn clauses, apply the ∊ -smoothing operation of flipping the polarity of every literal in every clause independently at random with probability ∊. Keeping ∊ and k fixed, and letting the density d = m / n grow, it is rather easy to see that for d ≥ ∊ −- k ln 2, F becomes whp unsatisfiable after smoothing. We show that a lower density that behaves roughly like ∊ −- k +1 suffices for this purpose. We also show that our bound on d is nearly best possible in the sense that there are k -CNF formulas F of slightly lower density that whp remain satisfiable after smoothing. One consequence of our proof is a new lower bound of Ω(2 k / k 2 ) on the density up to which Walksat solves random k -CNFs in polynomial time whp. We are not aware of any previous rigorous analysis showing that Walksat is successful at densities that are increasing as a function of k.

Details

FOCS Conference 1999 Conference Paper

Efficient Testing of Large Graphs

  • Noga Alon
  • Eldar Fischer
  • Michael Krivelevich
  • Mario Szegedy

Let P be a property of graphs. An /spl epsiv/-test for P is a randomized algorithm which, given the ability to make queries whether a desired pair of vertices of an input graph G with n vertices are adjacent or not, distinguishes, with high probability, between the case of G satisfying P and the case that it has to be modified by adding and removing more than /spl epsiv/n/sup 2/ edges to make it satisfy P. The property P is called testable, if for every /spl epsiv/ there exists an /spl epsiv/-test for P whose total number of queries is independent of the size of the input graph. O. Goldreich et al. (1996) showed that certain graph properties admit an /spl epsiv/-test. In this paper we make a first step towards a logical characterization of all testable graph properties, and show that properties describable by a very general type of coloring problem are testable. We use this theorem to prove that first order graph properties not containing a quantifier alternation of type "/spl forall//spl exist/" are always testable, while we show that some properties containing this alternation are not. Our results are proven using a combinatorial lemma, a special case of which, that may be of independent interest, is the following. A graph H is called /spl epsiv/-unavoidable in G if all graphs that differ from G in no more than /spl epsiv/|G|/sup 2/ places contain an induced copy of H. A graph H is called /spl delta/-abundant in G if G contains at least /spl delta/|G|/sup |H|/ induced copies of H. If H is /spl epsiv/-unavoidable in G then it is also /spl delta/(/spl epsiv/, |H|)-abundant.

Details

FOCS Conference 1999 Conference Paper

Regular Languages Are Testable with a Constant Number of Queries

  • Noga Alon
  • Michael Krivelevich
  • Ilan Newman
  • Mario Szegedy

We continue the study of combinatorial property testing, initiated by Goldreich, Goldwasser and Ron (1996). The subject of this paper is testing regular languages. Our main result is as follows. For a regular language L/spl isin/{0, 1}* and an integer n there exists a randomized algorithm which always accepts a word w of length n if w/spl isin/L, and rejects it with high probability if w has to be modified in at least En positions to create a word in L. The algorithm queries O~(1//spl epsiv/) bits of w. This query complexity is shown to be optimal up to a factor poly-logarithmic in 1//spl epsiv/. We also discuss testability of more complex languages and show, in particular, that the query complexity required for testing context free languages cannot be bounded by any function of /spl epsiv/. The problem of testing regular languages can be viewed as a part of a very general approach, seeking to probe testability of properties defined by logical means.

Details