We consider a variant of vertex cover in temporal graphs recently introduced to summarize timeline activities in social networks. Since the problem is already NP-hard when the time domain considered consists of two timestamps, we analyse the complexity of the problem in other restricted cases. We prove that the problem is NP-hard when (1) there exists exactly one interaction in each timestamp and (2) when each vertex has at most two interactions in each timestamp and the time domain consists of three timestamps. Moreover, we prove that the problem is fixed parameter tractable when the parameter is the size of the time window activity, which bounds the number of vertices with active temporal edges in a timestamp and the length of the interval where a vertex has incident temporal edges.

(2022). Insights into the Complexity of Disentangling Temporal Graphs . Retrieved from https://hdl.handle.net/10446/234192

Insights into the Complexity of Disentangling Temporal Graphs

Dondi, Riccardo
2022-01-01

Abstract

We consider a variant of vertex cover in temporal graphs recently introduced to summarize timeline activities in social networks. Since the problem is already NP-hard when the time domain considered consists of two timestamps, we analyse the complexity of the problem in other restricted cases. We prove that the problem is NP-hard when (1) there exists exactly one interaction in each timestamp and (2) when each vertex has at most two interactions in each timestamp and the time domain consists of three timestamps. Moreover, we prove that the problem is fixed parameter tractable when the parameter is the size of the time window activity, which bounds the number of vertices with active temporal edges in a timestamp and the length of the interval where a vertex has incident temporal edges.
File allegato/i alla scheda:
File Dimensione del file Formato  
ICTCS2022.pdf

accesso aperto

Versione: publisher's version - versione editoriale
Licenza: Creative commons
Dimensione del file 1.29 MB
Formato Adobe PDF
1.29 MB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

Aisberg ©2008 Servizi bibliotecari, Università degli studi di Bergamo | Terms of use/Condizioni di utilizzo

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10446/234192
Citazioni
  • Scopus 1
  • ???jsp.display-item.citation.isi??? ND
social impact