On temporally connected graphs of small cost

Eleni C. Akrida, Leszek Gąsieniec, George B. Mertzios, Paul G. Spirakis

Research output: Chapter in Book/Report/Conference proceedingConference contribution

8 Scopus citations


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 n log n labels.

Original languageEnglish (US)
Title of host publicationApproximation and Online Algorithms - 13th International Workshop, WAOA 2015, Revised Selected Papers
EditorsMartin Skutella, Laura Sanità
PublisherSpringer Verlag
Number of pages13
ISBN (Print)9783319286839
StatePublished - 2015
Externally publishedYes
Event13th International Workshop on Approximation and Online Algorithms, WAOA 2015 - Patras, Greece
Duration: Sep 17 2015Sep 18 2015

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference13th International Workshop on Approximation and Online Algorithms, WAOA 2015

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'On temporally connected graphs of small cost'. Together they form a unique fingerprint.

Cite this