A temporal (directed) graph is one where edges are available only at specific times during its lifetime, τ. Paths in these graphs are sequences of adjacent edges whose appearing times are either strictly increasing or non-strictly increasing. Classical concepts of connected and unilateral components can be naturally extended to temporal graphs. We address fundamental questions in temporal graphs. (i) What is the complexity of deciding the existence of a component of size k, parameterized by τ, k, and k+τ? The answer depends on the component definition and whether the graph is directed or undirected. (ii) What is the minimum running time to check if a subset of vertices is pairwise reachable? A quadratic-time algorithm exists, but a faster time is unlikely unless SETH fails. (iii) Can we verify if a subset of vertices forms a component in polynomial time? This is NP -complete depending on the temporal component definition.

On computing large temporal (unilateral) connected components / Costa I.L.; Lopes R.; Marino A.; Silva Ana Shirley. - In: JOURNAL OF COMPUTER AND SYSTEM SCIENCES. - ISSN 0022-0000. - ELETTRONICO. - 144:(2024), pp. 103548.103548-103548.103568. [10.1016/j.jcss.2024.103548]

On computing large temporal (unilateral) connected components

Marino A.;Silva Ana Shirley
2024

Abstract

A temporal (directed) graph is one where edges are available only at specific times during its lifetime, τ. Paths in these graphs are sequences of adjacent edges whose appearing times are either strictly increasing or non-strictly increasing. Classical concepts of connected and unilateral components can be naturally extended to temporal graphs. We address fundamental questions in temporal graphs. (i) What is the complexity of deciding the existence of a component of size k, parameterized by τ, k, and k+τ? The answer depends on the component definition and whether the graph is directed or undirected. (ii) What is the minimum running time to check if a subset of vertices is pairwise reachable? A quadratic-time algorithm exists, but a faster time is unlikely unless SETH fails. (iii) Can we verify if a subset of vertices forms a component in polynomial time? This is NP -complete depending on the temporal component definition.
2024
144
103548
103568
Costa I.L.; Lopes R.; Marino A.; Silva Ana Shirley
File in questo prodotto:
File Dimensione Formato  
temporal_components_JCSS.pdf

Accesso chiuso

Tipologia: Versione finale referata (Postprint, Accepted manuscript)
Licenza: Open Access
Dimensione 649.74 kB
Formato Adobe PDF
649.74 kB Adobe PDF   Richiedi una copia

I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificatore per citare o creare un link a questa risorsa: https://hdl.handle.net/2158/1363212
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact