SODA Conference 2015 Conference Paper
Robust hamiltonicity of random directed graphs extended abstract
- Asaf Ferber
- Rajko Nenadov
- Ueli Peter
- Andreas Noever
- Nemanja Skoric
In his seminal paper from 1952 Dirac showed that the complete graph on n ≥ 3 vertices remains Hamiltonian even if we allow an adversary to remove ⌊ n /2⌋ edges touching each vertex. In 1960 Ghouila-Houri obtained an analogue statement for digraphs by showing that every directed graph on n ≥ 3 vertices with minimum in- and out-degree at least n /2 contains a directed Hamilton cycle. Both statements quantify the robustness of complete graphs (digraphs) with respect to the property of containing a Hamilton cycle. A natural way to generalize such results to arbitrary graphs (digraphs) is using the notion of local resilience. The local resilience of a graph (digraph) G with respect to a property is the maximum number r such that G has the property even if we allow an adversary to remove an r -fraction of (in- and out-going) edges touching each vertex. The theorems of Dirac and Ghouila-Houri state that the local resilience of the complete graph and digraph with respect to Hamiltonicity is 1/2. Recently, this statements have been generalized to random settings. Lee and Sudakov (2012) proved that the local resilience of a random graph with edge probability p = ω (log n / n ) with respect to Hamiltonicity is 1/2 ± o (1). For random directed graphs, Hefetz, Steger and Sudakov (2014+) proved an analogue statement, but only for edge probability. In this paper we significantly improve their result to p = ω (log 8 n / n ), which is optimal up to the polylogarithmic factor.