The Complexity of Temporal Vertex Cover in Small-Degree Graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2022
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916168590163968 |
|---|---|
| author | Hamm, Thekla Klobas, Nina Mertzios, George B. Spirakis, Paul G. |
| author_facet | Hamm, Thekla Klobas, Nina Mertzios, George B. Spirakis, Paul G. |
| contents | Temporal graphs naturally model graphs whose underlying topology changes over time. Recently, the problems TEMPORAL VERTEX COVER (or TVC) and SLIDING-WINDOW TEMPORAL VERTEX COVER(or $Δ$-TVC for time-windows of a fixed-length $Δ$) have been established as natural extensions of the classic problem VERTEX COVER on static graphs with connections to areas such as surveillance in sensor networks. In this paper we initiate a systematic study of the complexity of TVC and $Δ$-TVC on sparse graphs. Our main result shows that for every $Δ\geq 2$, $Δ$-TVC is NP-hard even when the underlying topology is described by a path or a cycle. This resolves an open problem from literature and shows a surprising contrast between $Δ$-TVC and TVC for which we provide a polynomial-time algorithm in the same setting. To circumvent this hardness, we present a number of exact and approximation algorithms for temporal graphs whose underlying topologies are given by a path, that have bounded vertex degree in every time step, or that admit a small-sized temporal vertex cover. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2204_04832 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | The Complexity of Temporal Vertex Cover in Small-Degree Graphs Hamm, Thekla Klobas, Nina Mertzios, George B. Spirakis, Paul G. Data Structures and Algorithms Discrete Mathematics Temporal graphs naturally model graphs whose underlying topology changes over time. Recently, the problems TEMPORAL VERTEX COVER (or TVC) and SLIDING-WINDOW TEMPORAL VERTEX COVER(or $Δ$-TVC for time-windows of a fixed-length $Δ$) have been established as natural extensions of the classic problem VERTEX COVER on static graphs with connections to areas such as surveillance in sensor networks. In this paper we initiate a systematic study of the complexity of TVC and $Δ$-TVC on sparse graphs. Our main result shows that for every $Δ\geq 2$, $Δ$-TVC is NP-hard even when the underlying topology is described by a path or a cycle. This resolves an open problem from literature and shows a surprising contrast between $Δ$-TVC and TVC for which we provide a polynomial-time algorithm in the same setting. To circumvent this hardness, we present a number of exact and approximation algorithms for temporal graphs whose underlying topologies are given by a path, that have bounded vertex degree in every time step, or that admit a small-sized temporal vertex cover. |
| title | The Complexity of Temporal Vertex Cover in Small-Degree Graphs |
| topic | Data Structures and Algorithms Discrete Mathematics |
| url | https://arxiv.org/abs/2204.04832 |