Document Open Access Logo

The Complexity of Transitively Orienting Temporal Graphs

Authors George B. Mertzios , Hendrik Molter , Malte Renken , Paul G. Spirakis , Philipp Zschoche

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2021.75.pdf
  • Filesize: 0.84 MB
  • 18 pages

Document Identifiers

Author Details

George B. Mertzios
  • Department of Computer Science, Durham University, UK
Hendrik Molter
  • Department of Industrial Engineering and Management, Ben-Gurion University of the Negev, Beer Sheva, Israel
  • Faculty IV, Algorithmics and Computational Complexity, Technische Universität Berlin, Germany
Malte Renken
  • Faculty IV, Algorithmics and Computational Complexity, Technische Universität Berlin, Germany
Paul G. Spirakis
  • Department of Computer Science, University of Liverpool, UK
  • Computer Engineering & Informatics Department, University of Patras, Greece
Philipp Zschoche
  • Faculty IV, Algorithmics and Computational Complexity, Technische Universität Berlin, Germany

Funding

  • Mertzios, George B.: Supported by the EPSRC grant EP/P020372/1.
  • Molter, Hendrik: Supported by the German Research Foundation (DFG), project MATE (NI 369/17), and by the Israeli Science Foundation (ISF), grant No. 1070/20.
  • Renken, Malte: Supported by the German Research Foundation (DFG), project MATE (NI 369/17).
  • 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

George B. Mertzios, Hendrik Molter, Malte Renken, Paul G. Spirakis, and Philipp Zschoche. The Complexity of Transitively Orienting Temporal Graphs. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 75:1-75:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.MFCS.2021.75

Abstract

In a temporal network with discrete time-labels on its edges, entities and information can only "flow" along sequences of edges whose time-labels are non-decreasing (resp. increasing), i.e. along temporal (resp. strict temporal) paths. Nevertheless, in the model for temporal networks of [Kempe, Kleinberg, Kumar, JCSS, 2002], the individual time-labeled edges remain undirected: an edge e = {u,v} with time-label t specifies that "u communicates with v at time t". This is a symmetric relation between u and v, and it can be interpreted that the information can flow in either direction. In this paper we make a first attempt to understand how the direction of information flow on one edge can impact the direction of information flow on other edges. More specifically, naturally extending the classical notion of a transitive orientation in static graphs, we introduce the fundamental notion of a temporal transitive orientation and we systematically investigate its algorithmic behavior in various situations. An orientation of a temporal graph is called temporally transitive if, whenever u has a directed edge towards v with time-label t₁ and v has a directed edge towards w with time-label t₂ ≥ t₁, then u also has a directed edge towards w with some time-label t₃ ≥ t₂. If we just demand that this implication holds whenever t₂ > t₁, the orientation is called strictly temporally transitive, as it is based on the fact that there is a strict directed temporal path from u to w. Our main result is a conceptually simple, yet technically quite involved, polynomial-time algorithm for recognizing whether a given temporal graph 𝒢 is transitively orientable. In wide contrast we prove that, surprisingly, it is NP-hard to recognize whether 𝒢 is strictly transitively orientable. Additionally we introduce and investigate further related problems to temporal transitivity, notably among them the temporal transitive completion problem, for which we prove both algorithmic and hardness results.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
  • Mathematics of computing → Discrete mathematics
Keywords
  • Temporal graph
  • transitive orientation
  • transitive closure
  • polynomial-time algorithm
  • NP-hardness
  • satisfiability

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? Journal of Computer and System Sciences, 114:65-83, 2020. An extended abstract appeared at ICALP 2019. Google Scholar
  4. Eleni C. Akrida, George B. Mertzios, Paul G. Spirakis, and Viktor Zamaraev. Temporal vertex cover with a sliding time window. Journal of Computer and System Sciences, 107:108-123, 2020. Google Scholar
  5. Josh Alman and Virginia Vassilevska Williams. A refined laser method and faster matrix multiplication. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 522-539, 2021. Google Scholar
  6. Bengt Aspvall, Michael F. Plass, and Robert Endre Tarjan. A linear-time algorithm for testing the truth of certain quantified boolean formulas. Information Processing Letters, 8(3):121-123, 1979. Google Scholar
  7. 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
  8. 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
  9. Matthias Bentert, Anne-Sophie Himmel, André Nichterlein, and Rolf Niedermeier. Efficient computation of optimal temporal walks under waiting-time constraints. Applied Network Science, 5(1):73, 2020. Google Scholar
  10. Robert Bredereck, Christian Komusiewicz, Stefan Kratsch, Hendrik Molter, Rolf Niedermeier, and Manuel Sorge. Assessing the computational complexity of multilayer subgraph detection. Network Science, 7(2):215-241, 2019. Google Scholar
  11. 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(02):267-285, 2003. Google Scholar
  12. 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. ACM, 2020. Google Scholar
  13. Arnaud Casteigts and Paola Flocchini. Deterministic Algorithms in Dynamic Networks: Formal Models and Metrics. Technical report, Defence R&D Canada, April 2013. URL: https://hal.archives-ouvertes.fr/hal-00865762.
  14. Arnaud Casteigts and Paola Flocchini. Deterministic Algorithms in Dynamic Networks: Problems, Analysis, and Algorithmic Tools. Technical report, Defence R&D Canada, April 2013. URL: https://hal.archives-ouvertes.fr/hal-00865764.
  15. Arnaud Casteigts, Paola Flocchini, Walter Quattrociocchi, and Nicola Santoro. Time-varying graphs and dynamic networks. International Journal of Parallel, Emergent and Distributed Systems, 27(5):387-408, 2012. Google Scholar
  16. Arnaud Casteigts, Anne-Sophie Himmel, Hendrik Molter, and Philipp Zschoche. Finding temporal paths under waiting time constraints. In 31st International Symposium on Algorithms and Computation (ISAAC), pages 30:1-30:18, 2020. Google Scholar
  17. Arnaud Casteigts, Joseph G. Peters, and Jason Schoeters. Temporal cliques admit sparse spanners. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP), volume 132, pages 134:1-134:14, 2019. Google Scholar
  18. Jiehua Chen, Hendrik Molter, Manuel Sorge, and Ondřej Suchý. Cluster editing in multi-layer and temporal graphs. In Proceedings of the 29th International Symposium on Algorithms and Computation (ISAAC), pages 24:1-24:13, 2018. Google Scholar
  19. J. Enright, K. Meeks, G.B. Mertzios, and V. 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
  20. 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
  21. 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
  22. Till Fluschnik, Hendrik Molter, Rolf Niedermeier, Malte Renken, and Philipp Zschoche. Temporal graph classes: A view through temporal separators. Theoretical Computer Science, 806:197-218, 2020. Google Scholar
  23. Martin Charles Golumbic. Algorithmic graph theory and perfect graphs. Elsevier, 2nd edition, 2004. Google Scholar
  24. S Louis Hakimi, Edward F Schmeichel, and Neal E Young. Orienting graphs to optimize reachability. Information Processing Letters, 63(5):229-235, 1997. Google Scholar
  25. Anne-Sophie Himmel, Hendrik Molter, Rolf Niedermeier, and Manuel Sorge. Adapting the Bron-Kerbosch algorithm for enumerating maximal cliques in temporal graphs. Social Network Analysis and Mining, 7(1):35:1-35:16, 2017. Google Scholar
  26. Petter Holme and Jari Saramäki. Temporal network theory, volume 2. Springer, 2019. Google Scholar
  27. 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
  28. Hyoungshick Kim and Ross Anderson. Temporal node centrality in complex networks. Physical Review E, 85(2):026107, 2012. Google Scholar
  29. Ross M. McConnell and Jeremy P. Spinrad. Linear-time modular decomposition and efficient transitive orientation of comparability graphs. In Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 536-545, 1994. Google Scholar
  30. Ross M. McConnell and Jeremy P. Spinrad. Linear-time transitive orientation. In Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 19-25, 1997. Google Scholar
  31. Ross M. McConnell and Jeremy P. Spinrad. Modular decomposition and transitive orientation. Discrete Mathematics, 201(1-3):189-241, 1999. Google Scholar
  32. David B McDonald and Daizaburo Shizuka. Comparative transitive and temporal orderliness in dominance networks. Behavioral Ecology, 24(2):511-520, 2013. Google Scholar
  33. George B. Mertzios. The recognition of simple-triangle graphs and of linear-interval orders is polynomial. SIAM Journal on Discrete Mathematics, 29(3):1150-1185, 2015. Google Scholar
  34. 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
  35. 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
  36. George B. Mertzios, Hendrik Molter, Malte Renken, Paul G. Spirakis, and Philipp Zschoche. The complexity of transitively orienting temporal graphs. arXiv preprint, 2021. URL: http://arxiv.org/abs/2102.06783.
  37. George B Mertzios, Hendrik Molter, and Viktor Zamaraev. Sliding window temporal graph coloring. In Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI), volume 33, pages 7667-7674, 2019. Google Scholar
  38. Othon Michail and Paul G. Spirakis. Elements of the theory of dynamic networks. Communications of the ACM, 61(2):72-72, 2018. Google Scholar
  39. Robert Moskovitch and Yuval Shahar. Medical temporal-knowledge discovery via temporal abstraction. In Proceedings of the AMIA Annual Symposium, page 452, 2009. Google Scholar
  40. Robert Moskovitch and Yuval Shahar. Fast time intervals mining using the transitivity of temporal relations. Knowledge and Information Systems, 42(1):21-48, 2015. Google Scholar
  41. V. Nicosia, J. Tang, C. Mascolo, M. Musolesi, G. Russo, and V. Latora. Graph metrics for temporal networks. In Temporal Networks. Springer, 2013. Google Scholar
  42. Thomas J. Schaefer. The complexity of satisfiability problems. In Proceedings of the 10th Annual ACM Symposium on Theory of Computing (STOC), pages 216-226, 1978. Google Scholar
  43. Jeremy P. Spinrad. On comparability and permutation graphs. SIAM Journal on Computing, 14(3):658-670, 1985. Google Scholar
  44. Jeremy P. Spinrad. Efficient graph representations, volume 19 of Fields Institute Monographs. American Mathematical Society, 2003. Google Scholar
  45. Xavier Tannier and Philippe Muller. Evaluating temporal graphs built from texts via transitive reduction. Journal of Artificial Intelligence Research (JAIR), 40:375-413, 2011. Google Scholar
  46. Tiphaine Viard, Matthieu Latapy, and Clémence Magnien. Computing maximal cliques in link streams. Theoretical Computer Science, 609:245-252, 2016. Google Scholar
  47. Huanhuan Wu, James Cheng, Yiping Ke, Silu Huang, Yuzhen Huang, and Hejun Wu. Efficient algorithms for temporal path computation. IEEE Transactions on Knowledge and Data Engineering, 28(11):2927-2942, 2016. Google Scholar
  48. Philipp Zschoche, Till Fluschnik, Hendrik Molter, and Rolf Niedermeier. The complexity of finding separators in temporal graphs. Journal of Computer and System Sciences, 107:72-92, 2020. 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