Document Open Access Logo

Snapshot Disjointness in Temporal Graphs

Authors Allen Ibiapina , Ana Silva

PDF
Thumbnail PDF

File

LIPIcs.SAND.2023.1.pdf
  • Filesize: 1.13 MB
  • 20 pages

Document Identifiers

Author Details

Allen Ibiapina
  • ParGO Group, Departament of Mathematics, Federal University of Ceará, Fortaleza, Brazil
Ana Silva
  • ParGO Group, Departament of Mathematics, Federal University of Ceará, Fortaleza, Brazil

Funding

This study was financed in part by the Coordenação de Aperfeiçoamento de Pessoal de Nível Superior – Brasil (CAPES) – Finance Code 001, CNPq grants 303803/2020-7, and FUNCAP/CNPq PNE-0112-00061.01.00/16 and MLC-0191-00056.01.00/22.

Cite As Get BibTex

Allen Ibiapina and Ana Silva. Snapshot Disjointness in Temporal Graphs. In 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 257, pp. 1:1-1:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.SAND.2023.1

Abstract

In the study of temporal graphs, only paths respecting the flow of time are relevant. In this context, many concepts of walks disjointness have been proposed over the years, and the validity of Menger’s Theorem, as well as the complexity of related problems, has been investigated. Menger’s Theorem states that the maximum number of disjoint paths between two vertices is equal to the minimum number of vertices required to disconnect them. In this paper, we introduce and investigate a type of disjointness that is only time dependent. Two walks are said to be snapshot disjoint if they are not active in a same snapshot (also called timestep). The related paths and cut problems are then defined and proved to be W[1]-hard and XP-time solvable when parameterized by the size of the solution. Additionally, in the light of the definition of Mengerian graphs given by Kempe, Kleinberg and Kumar in their seminal paper (STOC'2000), we define a Mengerian graph for time as a graph G for which there is no time labeling for its edges where Menger’s Theorem does not hold in the context of snapshot disjointness. We then give a characterization of Mengerian graphs in terms of forbidden structures and provide a polynomial-time recognition algorithm. Finally, we also prove that, given a temporal graph (G,λ) and a pair of vertices s,z ∈ V(G), deciding whether at most h multiedges can separate s from z is NP-complete, where one multiedge uv is the set of all edges with endpoints u and v.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Combinatorics
  • Mathematics of computing → Paths and connectivity problems
Keywords
  • Temporal graphs
  • Menger’s Theorem
  • Snapshot disjointness

Metrics

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

References

  1. Amir Afrasiabi Rad, Paola Flocchini, and Joanne Gaudet. Computation and analysis of temporal betweenness in a knowledge mobilization network. Computational social networks, 4(1):1-22, 2017. Google Scholar
  2. Georg Baier, Thomas Erlebach, Alexander Hall, Ekkehard Köhler, Petr Kolman, Ondřej Pangrác, Heiko Schilling, and Martin Skutella. Length-bounded cuts and flows. ACM Transactions on Algorithms (TALG), 7(1):1-27, 2010. Google Scholar
  3. Kenneth A Berman. Vulnerability of scheduled networks and a generalization of Menger’s Theorem. Networks: An International Journal, 28(3):125-134, 1996. Google Scholar
  4. 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
  5. 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 2020, volume 181 of LIPIcs, pages 30:1-30:18, 2020. URL: https://doi.org/10.4230/LIPIcs.ISAAC.2020.30.
  6. Marek Cygan, Fedor V Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized algorithms, volume 5(4). Springer, 2015. Google Scholar
  7. Eugen Füchsle, Hendrik Molter, Rolf Niedermeier, and Malte Renken. Temporal Connectivity: Coping with Foreseen and Unforeseen Delays. In James Aspnes and Othon Michail, editors, 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022), volume 221 of Leibniz International Proceedings in Informatics (LIPIcs), pages 17:1-17:17, Dagstuhl, Germany, 2022. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.SAND.2022.17.
  8. Petr A Golovach and Dimitrios M Thilikos. Paths of bounded length and their cuts: Parameterized complexity and algorithms. Discrete Optimization, 8(1):72-86, 2011. Google Scholar
  9. Petter Holme. Modern temporal network theory: a colloquium. The European Physical Journal B, 88(9):234, 2015. Google Scholar
  10. Allen Ibiapina, Raul Lopes, Andrea Marino, and Ana Silva. Menger’s theorem for temporal paths (not walks). ArXiv, 2022. URL: https://arxiv.org/abs/2206.15251.
  11. Allen Ibiapina and Ana Silva. Mengerian graphs: Characterization and recognition. arxiv, 2022. URL: https://arxiv.org/abs/2208.06517.
  12. Alon Itai, Yehoshua Perl, and Yossi Shiloach. The complexity of finding maximum disjoint paths with length constraints. Networks, 12(3):277-286, 1982. Google Scholar
  13. David Kempe, Jon Kleinberg, and Amit Kumar. Connectivity and inference problems for temporal networks. Journal of Computer and System Sciences, 64:820-842, 2002. Google Scholar
  14. Matthieu Latapy, Tiphaine Viard, and Clémence Magnien. Stream graphs and link streams for the modeling of interactions over time. Social Network Analysis and Mining, 8(1):61, 2018. Google Scholar
  15. Chung-Lun Li, S Thomas McCormick, and David Simchi-Levi. The complexity of finding two disjoint paths with min-max objective function. Discrete Applied Mathematics, 26(1):105-115, 1990. Google Scholar
  16. George B Mertzios, Othon Michail, and Paul G Spirakis. Temporal network optimization subject to connectivity constraints. Algorithmica, 81(4):1416-1449, 2019. Google Scholar
  17. Yossi Shiloach and Yehoshua Perl. Finding two disjoint paths between two pairs of vertices in a graph. Journal of the ACM (JACM), 25(1):1-9, 1978. Google Scholar
  18. Douglas Brent West et al. Introduction to graph theory, volume 2. Prentice hall Upper Saddle River, 2001. Google Scholar
  19. B 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
  20. Philipp Zschoche, Till Fluschnik, Hendrik Molter, and Rolf Niedermeier. The complexity of finding small separators in temporal graphs. J. Comput. Syst. Sci., 107:72-92, 2020. URL: https://doi.org/10.1016/j.jcss.2019.07.006.
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 About DROPS Imprint Privacy Contact