The Diameter of Randomly Perturbed Digraphs and Some Applications TeX Export

@incollection{citeulike:1302296, abstract = {The central observation of this paper is that if ε n random edges are added to any n-node connected graph or digraph then the resulting graph has diameter \$\mathcal{O}(\log n)\$ with high probability. We apply this to smoothed analysis of algorithms and property testing. Smoothed Analysis: Recognizing strongly connected digraphs is a basic computational task in graph theory. Even for graphs with bounded out-degree, it is NL-complete. By XORing an arbitrary bounded out-degree digraph with a sparse random digraph \$R\sim\mathbb{D}\_{n,\epsilon/n}\$ we obtain a ” smoothed” instance. We show that, with high probability, a log-space algorithm will correctly determine if a smoothed instance is strongly connected. We also show that if \${\bf NL}\not\subseteq{\text{almost-{\bf{L}}}}\$ then no heuristic can recognize similarly perturbed instances of ( s, t)-connectivity. Property Testing: A digraph is called k-linked if for every choice of 2 k distinct vertices s 1,..., s k, t 1,..., t k, the graph contains k vertex disjoint paths joining s r to t r for r=1,..., k. Recognizing k-linked digraphs is NP-complete for k≥ 2. We describe a polynomial time algorithm for bounded degree digraphs which accepts k-linked graphs with high probability, and rejects all graphs which are at least ε n edges away from being k-linked.}, author = {Flaxman, Abraham D. and Frieze, Alan M.}, citeulike-article-id = {1302296}, citeulike-linkout-0 = {http://www.springerlink.com/content/ecqj89cmplcjx54j}, comment = {I think both applications of the central observation are great, and I think the theorem is quite interesting in its own right. It provides some theoretical explanation of the ``six degrees of separation'' phenomenon observed experimentally by Stanley Milgram, by showing that any large-enough network which contains a small amount of uniform randomness will have low diameter. }, journal = {Approximation, Randomization, and Combinatorial Optimization}, keywords = {algorithm, analysis, diameter, digraphs, graphs, log, perturbed, randomly, smoothed, space}, pages = {345--356}, posted-at = {2007-05-17 15:37:16}, priority = {0}, title = {The Diameter of Randomly Perturbed Digraphs and Some Applications}, url = {http://www.springerlink.com/content/ecqj89cmplcjx54j}, year = {2004} }

TY - CHAP ID - citeulike:1302296 L3 - citeulike-article-id:1302296 N2 - The central observation of this paper is that if ε n random edges are added to any n-node connected graph or digraph then the resulting graph has diameter $\mathcal{O}(\log n)$ with high probability. We apply this to smoothed analysis of algorithms and property testing. Smoothed Analysis: Recognizing strongly connected digraphs is a basic computational task in graph theory. Even for graphs with bounded out-degree, it is NL-complete. By XORing an arbitrary bounded out-degree digraph with a sparse random digraph $R\sim\mathbb{D}_{n,\epsilon/n}$ we obtain a “smoothed” instance. We show that, with high probability, a log-space algorithm will correctly determine if a smoothed instance is strongly connected. We also show that if ${\bf NL}\not\subseteq{\text{almost-{\bf{L}}}}$ then no heuristic can recognize similarly perturbed instances of ( s, t)-connectivity. Property Testing: A digraph is called k-linked if for every choice of 2 k distinct vertices s 1,..., s k, t 1,..., t k, the graph contains k vertex disjoint paths joining s r to t r for r=1,..., k. Recognizing k-linked digraphs is NP-complete for k≥ 2. We describe a polynomial time algorithm for bounded degree digraphs which accepts k-linked graphs with high probability, and rejects all graphs which are at least ε n edges away from being k-linked. JF - Approximation, Randomization, and Combinatorial Optimization EP - 356 TI - The Diameter of Randomly Perturbed Digraphs and Some Applications SP - 345 KW - algorithm KW - analysis KW - diameter KW - digraphs KW - graphs KW - log KW - perturbed KW - randomly KW - smoothed KW - space N1 - I think both applications of the central observation are great, and I think the theorem is quite interesting in its own right. It provides some theoretical explanation of the ``six degrees of separation'' phenomenon observed experimentally by Stanley Milgram, by showing that any large-enough network which contains a small amount of uniform randomness will have low diameter. AU - Flaxman, Abraham AU - Frieze, Alan PY - 2004/// UR - http://www.springerlink.com/content/ecqj89cmplcjx54j ER -