The Diameter of Randomly Perturbed Digraphs and Some Applications TeX

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 $\mathcalO(\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∼\mathbbD_n,ε/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 $ NL\not⊆\textalmost-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.