Premium
The diameter of randomly perturbed digraphs and some applications
Author(s) -
Flaxman Abraham D.,
Frieze Alan M.
Publication year - 2007
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20172
Subject(s) - digraph , combinatorics , bounded function , mathematics , degree (music) , vertex (graph theory) , disjoint sets , discrete mathematics , graph , mathematical analysis , physics , acoustics
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