Exploration of k-Edge-Deficient Temporal Graphs

An always-connected temporal graph G=⟨G1,...,GL⟩ with underlying graph G=(V,E) is a sequence of graphs Gt⊆G such that V(Gt)=V and Gt is connected for all t. This paper considers the property of k-edge-deficiency for temporal graphs; such graphs satisfy Gt=(V,E−Xt) for all t, where Xt⊆E and |Xt|≤k . We study the Temporal Exploration problem (compute a temporal walk that visits all vertices v∈V at least once and finishes as early as possible) restricted to always-connected, k-edge-deficient temporal graphs and give constructive proofs that show that k-edge-deficient and 1-edge-deficient temporal graphs can be explored in O(knlogn) and O(n) timesteps, respectively. We also give a lower-bound construction of an infinite family of always-connected k-edge-deficient temporal graphs for which any exploration schedule requires at least Ω(nlogk) timesteps.