In this contribution we consider a variant of the vertex cover problem in temporal graphs that has been recently introduced to summarize timeline activities in social networks. The problem is NP-hard, even when the time domain considered consists of two timestamps. We further analyze the complexity of this problem, focusing on temporal graphs of bounded degree. We prove that the problem is NP-hard when (1) each vertex has degree at most one in each timestamp and (2) each vertex is connected with at most three neighbors, has degree at most two in each timestamp and the time domain consists of three timestamps. On the other hand, we prove that the problem is in P when each vertex is connected with at most two neighbors. Then we present a fixed-parameter algorithm for the restriction where we bound the number of interactions in each timestamp and the length of the interval where a vertex has incident temporal edges.

(2023). Untangling temporal graphs of bounded degree [journal article - articolo]. In THEORETICAL COMPUTER SCIENCE. Retrieved from https://hdl.handle.net/10446/261615

Untangling temporal graphs of bounded degree

Dondi, Riccardo
2023-01-01

Abstract

In this contribution we consider a variant of the vertex cover problem in temporal graphs that has been recently introduced to summarize timeline activities in social networks. The problem is NP-hard, even when the time domain considered consists of two timestamps. We further analyze the complexity of this problem, focusing on temporal graphs of bounded degree. We prove that the problem is NP-hard when (1) each vertex has degree at most one in each timestamp and (2) each vertex is connected with at most three neighbors, has degree at most two in each timestamp and the time domain consists of three timestamps. On the other hand, we prove that the problem is in P when each vertex is connected with at most two neighbors. Then we present a fixed-parameter algorithm for the restriction where we bound the number of interactions in each timestamp and the length of the interval where a vertex has incident temporal edges.
articolo
2023
Dondi, Riccardo
(2023). Untangling temporal graphs of bounded degree [journal article - articolo]. In THEORETICAL COMPUTER SCIENCE. Retrieved from https://hdl.handle.net/10446/261615
File allegato/i alla scheda:
File Dimensione del file Formato  
TCS2023.pdf

accesso aperto

Versione: publisher's version - versione editoriale
Licenza: Creative commons
Dimensione del file 460.04 kB
Formato Adobe PDF
460.04 kB 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/261615
Citazioni
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 3
social impact