Document Open Access Logo

The Complexity of Computing Optimum Labelings for Temporal Connectivity

Authors Nina Klobas , George B. Mertzios , Hendrik Molter , Paul G. Spirakis

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2022.62.pdf
  • Filesize: 1.21 MB
  • 15 pages

Document Identifiers

Author Details

Nina Klobas
  • Department of Computer Science, Durham University, UK
George B. Mertzios
  • Department of Computer Science, Durham University, UK
Hendrik Molter
  • Department of Industrial Engineering and Management, Ben-Gurion University of the Negev, Israel
Paul G. Spirakis
  • Department of Computer Science, University of Liverpool, UK
  • Computer Engineering & Informatics Department, University of Patras, Greece

Funding

  • Mertzios, George B.: Supported by the EPSRC grant EP/P020372/1.
  • Molter, Hendrik: Supported by the ISF, grant No. 1070/20.
  • Spirakis, Paul G.: Supported by the NeST initiative of the School of EEE and CS at the University of Liverpool and by the EPSRC grant EP/P02002X/1.

Cite AsGet BibTex

Nina Klobas, George B. Mertzios, Hendrik Molter, and Paul G. Spirakis. The Complexity of Computing Optimum Labelings for Temporal Connectivity. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 62:1-62:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.MFCS.2022.62

Abstract

A graph is temporally connected if there exists a strict temporal path, i.e., a path whose edges have strictly increasing labels, from every vertex u to every other vertex v. In this paper we study temporal design problems for undirected temporally connected graphs. The basic setting of these optimization problems is as follows: given a connected undirected graph G, what is the smallest number |λ| of time-labels that we need to add to the edges of G such that the resulting temporal graph (G,λ) is temporally connected? As it turns out, this basic problem, called Minimum Labeling (ML), can be optimally solved in polynomial time. However, exploiting the temporal dimension, the problem becomes more interesting and meaningful in its following variations, which we investigate in this paper. First we consider the problem Min. Aged Labeling (MAL) of temporally connecting the graph when we are given an upper-bound on the allowed age (i.e., maximum label) of the obtained temporal graph (G,λ). Second we consider the problem Min. Steiner Labeling (MSL), where the aim is now to have a temporal path between any pair of "important" vertices which lie in a subset R ⊆ V, which we call the terminals. This relaxed problem resembles the problem Steiner Tree in static (i.e., non-temporal) graphs. However, due to the requirement of strictly increasing labels in a temporal path, Steiner Tree is not a special case of MSL. Finally we consider the age-restricted version of MSL, namely Min. Aged Steiner Labeling (MASL). Our main results are threefold: we prove that (i) MAL becomes NP-complete on undirected graphs, while (ii) MASL becomes W[1]-hard with respect to the number |R| of terminals. On the other hand we prove that (iii) although the age-unrestricted problem MSL remains NP-hard, it is in FPT with respect to the number |R| of terminals. That is, adding the age restriction, makes the above problems strictly harder (unless P=NP or W[1]=FPT).

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
  • Mathematics of computing → Discrete mathematics
Keywords
  • Temporal graph
  • graph labeling
  • foremost temporal path
  • temporal connectivity
  • Steiner Tree

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Eleni C. Akrida, Leszek Gasieniec, George B. Mertzios, and Paul G. Spirakis. Ephemeral networks with random availability of links: The case of fast networks. Journal of Parallel and Distributed Computing, 87:109-120, 2016. Google Scholar
  2. Eleni C. Akrida, Leszek Gasieniec, George B. Mertzios, and Paul G. Spirakis. The complexity of optimal design of temporally connected graphs. Theory of Computing Systems, 61(3):907-944, 2017. Google Scholar
  3. Eleni C. Akrida, George B. Mertzios, Sotiris E. Nikoletseas, Christoforos L. Raptopoulos, Paul G. Spirakis, and Viktor Zamaraev. How fast can we reach a target vertex in stochastic temporal graphs? In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, (ICALP), volume 132, pages 131:1-131:14, 2019. Google Scholar
  4. Eleni C. Akrida, George B. Mertzios, Paul G. Spirakis, and Viktor Zamaraev. Temporal vertex cover with a sliding time window. In Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP), pages 148:1-148:14, 2018. Google Scholar
  5. Paola Alimonti and Viggo Kann. Hardness of approximating problems on cubic graphs. In Proceedings of the 3rd Italian Conference on Algorithms and Complexity (CIAC), pages 288-298, 1997. Google Scholar
  6. Kyriakos Axiotis and Dimitris Fotakis. On the size and the approximability of minimum temporally connected subgraphs. In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, (ICALP), pages 149:1-149:14, 2016. Google Scholar
  7. Matthias Bentert, Anne-Sophie Himmel, Hendrik Molter, Marco Morik, Rolf Niedermeier, and René Saitenmacher. Listing all maximal k-plexes in temporal graphs. ACM Journal of Experimental Algorithmics, 24(1):13:1-13:27, 2019. Google Scholar
  8. Binh-Minh Bui-Xuan, Afonso Ferreira, and Aubin Jarry. Computing shortest, fastest, and foremost journeys in dynamic networks. International Journal of Foundations of Computer Science, 14(2):267-285, 2003. Google Scholar
  9. Richard T. Bumby. A problem with telephones. SIAM Journal on Algebraic and Discrete Methods, 2(1):13-18, 1981. Google Scholar
  10. Sebastian Buß, Hendrik Molter, Rolf Niedermeier, and Maciej Rymar. Algorithmic aspects of temporal betweenness. In Proceedings of the 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD), pages 2084-2092, 2020. Google Scholar
  11. Arnaud Casteigts, Joseph G. Peters, and Jason Schoeters. Temporal cliques admit sparse spanners. Journal of Computer and System Sciences, 121:1-17, 2021. Google Scholar
  12. Argyrios Deligkas, Eduard Eiben, and George Skretas. Minimizing reachability times on temporal graphs via shifting labels. CoRR, abs/2112.08797, 2021. URL: http://arxiv.org/abs/2112.08797.
  13. Argyrios Deligkas and Igor Potapov. Optimizing reachability sets in temporal graphs by delaying. In Proceedings of the 34th Conference on Artificial Intelligence (AAAI), pages 9810-9817, 2020. Google Scholar
  14. S.E. Dreyfus and R.A. Wagner. The steiner problem in graphs. Networks, 1:195-207, 1971. Google Scholar
  15. Jessica Enright, Kitty Meeks, George B. Mertzios, and Viktor Zamaraev. Deleting edges to restrict the size of an epidemic in temporal networks. Journal of Computer and System Sciences, 119:60-77, 2021. Google Scholar
  16. Jessica Enright, Kitty Meeks, and Fiona Skerman. Assigning times to minimise reachability in temporal graphs. Journal of Computer and System Sciences, 115:169-186, 2021. Google Scholar
  17. Thomas Erlebach, Michael Hoffmann, and Frank Kammer. On temporal graph exploration. In Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP), pages 444-455, 2015. Google Scholar
  18. Thomas Erlebach and Jakob T. Spooner. Faster exploration of degree-bounded temporal graphs. In Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS), pages 36:1-36:13, 2018. Google Scholar
  19. F. Göbel, J.Orestes Cerdeira, and H.J. Veldman. Label-connected graphs and the gossip problem. Discrete Mathematics, 87(1):29-40, 1991. Google Scholar
  20. Roman Haag, Hendrik Molter, Rolf Niedermeier, and Malte Renken. Feedback edge sets in temporal graphs. Discrete Applied Mathematics, 307:65-78, 2022. Google Scholar
  21. Thekla Hamm, Nina Klobas, George B. Mertzios, and Paul G. Spirakis. The complexity of temporal vertex cover in small-degree graphs. In Proceedings of the 36th Conference on Artificial Intelligence (AAAI), 2022. To appear. Google Scholar
  22. Sandra M. Hedetniemi, Stephen T. Hedetniemi, and Arthur L. Liestman. A survey of gossiping and broadcasting in communication networks. Networks, 18(4):319-349, 1988. Google Scholar
  23. Petter Holme and Jari Saramäki. Temporal network theory, volume 2. Springer, 2019. Google Scholar
  24. Richard M. Karp. Reducibility among combinatorial problems. In Complexity of Computer Computations, pages 85-103. Springer, 1972. Google Scholar
  25. David Kempe, Jon M. Kleinberg, and Amit Kumar. Connectivity and inference problems for temporal networks. Journal of Computer and System Sciences, 64(4):820-842, 2002. Google Scholar
  26. Nina Klobas, George B. Mertzios, Hendrik Molter, Rolf Niedermeier, and Philipp Zschoche. Interference-free walks in time: Temporally disjoint paths. In Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI), pages 4090-4096, 2021. Google Scholar
  27. Nina Klobas, George B. Mertzios, Hendrik Molter, and Paul G. Spirakis. The complexity of computing optimum labelings for temporal connectivity. CoRR, abs/2202.0588, 2022. URL: http://arxiv.org/abs/2202.0588.
  28. George B. Mertzios, Othon Michail, Ioannis Chatzigiannakis, and Paul G. Spirakis. Temporal network optimization subject to connectivity constraints. In Proceedings of the 40th International Colloquium on Automata, Languages and Programming (ICALP), pages 657-668, 2013. Google Scholar
  29. George B Mertzios, Hendrik Molter, Rolf Niedermeier, Viktor Zamaraev, and Philipp Zschoche. Computing maximum matchings in temporal graphs. In Proceedings of the 37th International Symposium on Theoretical Aspects of Computer Science (STACS), volume 154, pages 27:1-27:14, 2020. Google Scholar
  30. George B. Mertzios, Hendrik Molter, Malte Renken, Paul G. Spirakis, and Philipp Zschoche. The complexity of transitively orienting temporal graphs. In Proceedings of the 46th International Symposium on Mathematical Foundations of Computer Science (MFCS), pages 75:1-75:18, 2021. Google Scholar
  31. George B. Mertzios, Hendrik Molter, and Viktor Zamaraev. Sliding window temporal graph coloring. Journal of Computer and System Sciences, 120:97-115, 2021. Google Scholar
  32. Othon Michail and Paul G. Spirakis. Traveling salesman problems in temporal graphs. Theoretical Computer Science, 634:1-23, 2016. Google Scholar
  33. Othon Michail and Paul G. Spirakis. Elements of the theory of dynamic networks. Communications of the ACM, 61(2):72-72, January 2018. Google Scholar
  34. Hendrik Molter, Malte Renken, and Philipp Zschoche. Temporal reachability minimization: Delaying vs. deleting. In Proceedings of the 46th International Symposium on Mathematical Foundations of Computer Science (MFCS '21), pages 76:1-76:15, 2021. Google Scholar
  35. Vincenzo Nicosia, John Tang, Cecilia Mascolo, Mirco Musolesi, Giovanni Russo, and Vito Latora. Graph metrics for temporal networks. In Temporal Networks. Springer, 2013. Google Scholar
  36. Suhas Thejaswi, Juho Lauri, and Aristides Gionis. Restless reachability in temporal graphs. CoRR, abs/2010.08423, 2021. URL: http://arxiv.org/abs/2010.08423.
  37. Tiphaine Viard, Matthieu Latapy, and Clémence Magnien. Computing maximal cliques in link streams. Theoretical Computer Science, 609:245-252, 2016. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact