4 Search Results for "Krivelevich, Michael"


Document
RANDOM
Local Treewidth of Random and Noisy Graphs with Applications to Stopping Contagion in Networks

Authors: Hermish Mehta and Daniel Reichman

Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)


Abstract
We study the notion of local treewidth in sparse random graphs: the maximum treewidth over all k-vertex subgraphs of an n-vertex graph. When k is not too large, we give nearly tight bounds for this local treewidth parameter; we also derive nearly tight bounds for the local treewidth of noisy trees, trees where every non-edge is added independently with small probability. We apply our upper bounds on the local treewidth to obtain fixed parameter tractable algorithms (on random graphs and noisy trees) for edge-removal problems centered around containing a contagious process evolving over a network. In these problems, our main parameter of study is k, the number of initially "infected" vertices in the network. For the random graph models we consider and a certain range of parameters the running time of our algorithms on n-vertex graphs is 2^o(k) poly(n), improving upon the 2^Ω(k) poly(n) performance of the best-known algorithms designed for worst-case instances of these edge deletion problems.

Cite as

Hermish Mehta and Daniel Reichman. Local Treewidth of Random and Noisy Graphs with Applications to Stopping Contagion in Networks. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 7:1-7:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{mehta_et_al:LIPIcs.APPROX/RANDOM.2022.7,
  author =	{Mehta, Hermish and Reichman, Daniel},
  title =	{{Local Treewidth of Random and Noisy Graphs with Applications to Stopping Contagion in Networks}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
  pages =	{7:1--7:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-249-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{245},
  editor =	{Chakrabarti, Amit and Swamy, Chaitanya},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.7},
  URN =		{urn:nbn:de:0030-drops-171299},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2022.7},
  annote =	{Keywords: Graph Algorithms, Random Graphs, Data Structures and Algorithms, Discrete Mathematics}
}
Document
Greedy Maximal Independent Sets via Local Limits

Authors: Michael Krivelevich, Tamás Mészáros, Peleg Michaeli, and Clara Shikhelman

Published in: LIPIcs, Volume 159, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)


Abstract
The random greedy algorithm for finding a maximal independent set in a graph has been studied extensively in various settings in combinatorics, probability, computer science - and even in chemistry. The algorithm builds a maximal independent set by inspecting the vertices of the graph one at a time according to a random order, adding the current vertex to the independent set if it is not connected to any previously added vertex by an edge. In this paper we present a natural and general framework for calculating the asymptotics of the proportion of the yielded independent set for sequences of (possibly random) graphs, involving a useful notion of local convergence. We use this framework both to give short and simple proofs for results on previously studied families of graphs, such as paths and binomial random graphs, and to study new ones, such as random trees. We conclude our work by analysing the random greedy algorithm more closely when the base graph is a tree. We show that in expectation, the cardinality of a random greedy independent set in the path is no larger than that in any other tree of the same order.

Cite as

Michael Krivelevich, Tamás Mészáros, Peleg Michaeli, and Clara Shikhelman. Greedy Maximal Independent Sets via Local Limits. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 20:1-20:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{krivelevich_et_al:LIPIcs.AofA.2020.20,
  author =	{Krivelevich, Michael and M\'{e}sz\'{a}ros, Tam\'{a}s and Michaeli, Peleg and Shikhelman, Clara},
  title =	{{Greedy Maximal Independent Sets via Local Limits}},
  booktitle =	{31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)},
  pages =	{20:1--20:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-147-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{159},
  editor =	{Drmota, Michael and Heuberger, Clemens},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.20},
  URN =		{urn:nbn:de:0030-drops-120507},
  doi =		{10.4230/LIPIcs.AofA.2020.20},
  annote =	{Keywords: Greedy maximal independent set, random graph, local limit}
}
Document
The Genus of the Erdös-Rényi Random Graph and the Fragile Genus Property

Authors: Chris Dowden, Mihyun Kang, and Michael Krivelevich

Published in: LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)


Abstract
We investigate the genus g(n,m) of the Erdös-Rényi random graph G(n,m), providing a thorough description of how this relates to the function m=m(n), and finding that there is different behaviour depending on which `region' m falls into. Existing results are known for when m is at most n/(2) + O(n^{2/3}) and when m is at least omega (n^{1+1/(j)}) for j in N, and so we focus on intermediate cases. In particular, we show that g(n,m) = (1+o(1)) m/(2) whp (with high probability) when n << m = n^{1+o(1)}; that g(n,m) = (1+o(1)) mu (lambda) m whp for a given function mu (lambda) when m ~ lambda n for lambda > 1/2; and that g(n,m) = (1+o(1)) (8s^3)/(3n^2) whp when m = n/(2) + s for n^(2/3) << s << n. We then also show that the genus of fixed graphs can increase dramatically if a small number of random edges are added. Given any connected graph with bounded maximum degree, we find that the addition of epsilon n edges will whp result in a graph with genus Omega (n), even when epsilon is an arbitrarily small constant! We thus call this the `fragile genus' property.

Cite as

Chris Dowden, Mihyun Kang, and Michael Krivelevich. The Genus of the Erdös-Rényi Random Graph and the Fragile Genus Property. In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, pp. 17:1-17:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{dowden_et_al:LIPIcs.AofA.2018.17,
  author =	{Dowden, Chris and Kang, Mihyun and Krivelevich, Michael},
  title =	{{The Genus of the Erd\"{o}s-R\'{e}nyi Random Graph and the Fragile Genus Property}},
  booktitle =	{29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
  pages =	{17:1--17:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-078-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{110},
  editor =	{Fill, James Allen and Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.17},
  URN =		{urn:nbn:de:0030-drops-89100},
  doi =		{10.4230/LIPIcs.AofA.2018.17},
  annote =	{Keywords: Random graphs, Genus, Fragile genus}
}
Document
Smoothed Analysis on Connected Graphs

Authors: Michael Krivelevich, Daniel Reichman, and Wojciech Samotij

Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)


Abstract
The main paradigm of smoothed analysis on graphs suggests that for any large graph G in a certain class of graphs, perturbing slightly the edges of G at random (usually adding few random edges to G) typically results in a graph having much "nicer" properties. In this work we study smoothed analysis on trees or, equivalently, on connected graphs. Given an n-vertex connected graph G, form a random supergraph of G* of G by turning every pair of vertices of G into an edge with probability epsilon/n, where epsilon is a small positive constant. This perturbation model has been studied previously in several contexts, including smoothed analysis, small world networks, and combinatorics. Connected graphs can be bad expanders, can have very large diameter, and possibly contain no long paths. In contrast, we show that if G is an n-vertex connected graph then typically G* has edge expansion Omega(1/(log n)), diameter O(log n), vertex expansion Omega(1/(log n)), and contains a path of length Omega(n), where for the last two properties we additionally assume that G has bounded maximum degree. Moreover, we show that if G has bounded degeneracy, then typically the mixing time of the lazy random walk on G* is O(log^2(n)). All these results are asymptotically tight.

Cite as

Michael Krivelevich, Daniel Reichman, and Wojciech Samotij. Smoothed Analysis on Connected Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 810-825, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)


Copy BibTex To Clipboard

@InProceedings{krivelevich_et_al:LIPIcs.APPROX-RANDOM.2014.810,
  author =	{Krivelevich, Michael and Reichman, Daniel and Samotij, Wojciech},
  title =	{{Smoothed Analysis on Connected Graphs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{810--825},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.810},
  URN =		{urn:nbn:de:0030-drops-47407},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.810},
  annote =	{Keywords: Random walks and Markov chains, Random network models}
}
  • Refine by Author
  • 3 Krivelevich, Michael
  • 2 Reichman, Daniel
  • 1 Dowden, Chris
  • 1 Kang, Mihyun
  • 1 Mehta, Hermish
  • Show More...

  • Refine by Classification
  • 2 Mathematics of computing → Random graphs
  • 1 Mathematics of computing → Graph algorithms
  • 1 Mathematics of computing → Graphs and surfaces
  • 1 Mathematics of computing → Probabilistic algorithms
  • 1 Theory of computation → Dynamic graph algorithms

  • Refine by Keyword
  • 1 Data Structures and Algorithms
  • 1 Discrete Mathematics
  • 1 Fragile genus
  • 1 Genus
  • 1 Graph Algorithms
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 1 2014
  • 1 2018
  • 1 2020
  • 1 2022

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail