Akrida, E.C. and Gasieniec, L. and Mertzios, G.B. and Spirakis, P.G. (2016) 'On temporally connected graphs of small cost.', in Approximation and online algorithms : 13th International Workshop, WAOA 2015, Patras, Greece, September 17-18, 2015. Revised selected papers. Cham: Springer, pp. 84-96. Lecture notes in computer science. (9499).
We study the design of small cost temporally connected graphs, under various constraints. We mainly consider undirected graphs of n vertices, where each edge has an associated set of discrete availability instances (labels). A journey from vertex u to vertex v is a path from u to v where successive path edges have strictly increasing labels. A graph is temporally connected iff there is a (u, v)-journey for any pair of vertices u,v, u≠v. We first give a simple polynomial-time algorithm to check whether a given temporal graph is temporally connected. We then consider the case in which a designer of temporal graphs can freely choose availability instances for all edges and aims for temporal connectivity with very small cost; the cost is the total number of availability instances used. We achieve this via a simple polynomial-time procedure which derives designs of cost linear in n, and at most the optimal cost plus 2. To show this, we prove a lower bound on the cost for any undirected graph. However, there are pragmatic cases where one is not free to design a temporally connected graph anew, but is instead given a temporal graph design with the claim that it is temporally connected, and wishes to make it more cost-efficient by removing labels without destroying temporal connectivity (redundant labels). Our main technical result is that computing the maximum number of redundant labels is APX-hard, i.e., there is no PTAS unless P=NP. On the positive side, we show that in dense graphs with random edge availabilities, all but Θ(n) labels are redundant whp. A temporal design may, however, be minimal, i.e., no redundant labels exist. We show the existence of minimal temporal designs with at least nlogn labels.
|Item Type:||Book chapter|
|Full text:||(AM) Accepted Manuscript|
Download PDF (239Kb)
|Publisher Web site:||https://doi.org/10.1007%2F978-3-319-28684-6_8|
|Publisher statement:||The final publication is available at Springer via http://dx.doi.org/10.1007%2F978-3-319-28684-6_8|
|Date accepted:||24 July 2015|
|Date deposited:||12 October 2015|
|Date of first online publication:||13 January 2016|
|Date first made open access:||13 January 2017|
Save or Share this output
|Look up in GoogleScholar|