The diameter of randomly perturbed digraphs and some applications

The central observation of this paper is that if ε n random arcs are added to any n ‐node strongly connected digraph with bounded degree then the resulting graph has diameter (ln 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 digraphs with bounded degree, it is NL‐complete. By XORing an arbitrary bounded degree digraph with a sparse random digraph R ∼ 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 ⫅̸ almost‐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 that are at least ε n arcs away from being k ‐linked. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007