In search of the lost tree: Hardness and relaxation of spanning trees in temporal graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915945041100800 |
|---|---|
| author | Casteigts, Arnaud Corsini, Timothée Morawietz, Nils |
| author_facet | Casteigts, Arnaud Corsini, Timothée Morawietz, Nils |
| contents | A temporal graph is a graph whose edges appear at certain points in time. These graphs are temporally connected (in class TC) if all vertices can reach each other by temporal paths (traversing the edges in chronological order). Reachability based on temporal paths is not transitive, with important consequences. For instance, TC graphs do not always admit TC spanning trees.
In this paper, we show that deciding if a given temporal graph admits a TC spanning tree is actually NP-complete. Then, we explore possible relaxations. A key feature of TC spanning trees is to support reachability along the same paths in both directions. We show that this property is not equivalent to TC spanning trees, it is more general and it can be tested in polynomial time. Still, minimizing the size of a spanner preserving this property -- a bidirectional spanner -- is \textsf{NP}-hard even more generally than TC spanning tree, including the setting of simple temporal graphs.
Along the way, we show that deciding the existence of TC spanning tree is FPT when parameterized by the feedback edge set number (fes) of the underlying graph, and deciding bidirectional spanners of size $k$ is FPT when parameterized by fes + $\ell$ (the maximum number of labels per edge). On the structural side, we show that TC trees always admit a pivot vertex or a pivot edge -- reachable by all vertices by a certain time and able to reach all vertices afterward -- a fact that may be of independent interest. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_06260 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | In search of the lost tree: Hardness and relaxation of spanning trees in temporal graphs Casteigts, Arnaud Corsini, Timothée Morawietz, Nils Discrete Mathematics Distributed, Parallel, and Cluster Computing 68R10, 68W15 G.2.2; C.2.4 A temporal graph is a graph whose edges appear at certain points in time. These graphs are temporally connected (in class TC) if all vertices can reach each other by temporal paths (traversing the edges in chronological order). Reachability based on temporal paths is not transitive, with important consequences. For instance, TC graphs do not always admit TC spanning trees. In this paper, we show that deciding if a given temporal graph admits a TC spanning tree is actually NP-complete. Then, we explore possible relaxations. A key feature of TC spanning trees is to support reachability along the same paths in both directions. We show that this property is not equivalent to TC spanning trees, it is more general and it can be tested in polynomial time. Still, minimizing the size of a spanner preserving this property -- a bidirectional spanner -- is \textsf{NP}-hard even more generally than TC spanning tree, including the setting of simple temporal graphs. Along the way, we show that deciding the existence of TC spanning tree is FPT when parameterized by the feedback edge set number (fes) of the underlying graph, and deciding bidirectional spanners of size $k$ is FPT when parameterized by fes + $\ell$ (the maximum number of labels per edge). On the structural side, we show that TC trees always admit a pivot vertex or a pivot edge -- reachable by all vertices by a certain time and able to reach all vertices afterward -- a fact that may be of independent interest. |
| title | In search of the lost tree: Hardness and relaxation of spanning trees in temporal graphs |
| topic | Discrete Mathematics Distributed, Parallel, and Cluster Computing 68R10, 68W15 G.2.2; C.2.4 |
| url | https://arxiv.org/abs/2312.06260 |