Document Open Access Logo

Computing Maximum Matchings in Temporal Graphs

Authors George B. Mertzios , Hendrik Molter , Rolf Niedermeier , Viktor Zamaraev , Philipp Zschoche

PDF
Thumbnail PDF

File

LIPIcs.STACS.2020.27.pdf
  • Filesize: 0.56 MB
  • 14 pages

Document Identifiers

Author Details

George B. Mertzios
  • Department of Computer Science, Durham University, UK
Hendrik Molter
  • TU Berlin, Faculty IV, Algorithmics and Computational Complexity, Berlin, Germany
Rolf Niedermeier
  • TU Berlin, Faculty IV, Algorithmics and Computational Complexity, Berlin, Germany
Viktor Zamaraev
  • Department of Computer Science, University of Liverpool, UK
Philipp Zschoche
  • TU Berlin, Faculty IV, Algorithmics and Computational Complexity, Berlin, Germany

Funding

  • Mertzios, George B.: Supported by the EPSRC grant EP/P020372/1.
  • Molter, Hendrik: Supported by the DFG, project MATE (NI369/17).
  • Zamaraev, Viktor: Supported by the EPSRC grant EP/P020372/1. The main part of this paper was prepared while affiliated with the Department of Computer Science, Durham University, UK.

Cite As Get BibTex

George B. Mertzios, Hendrik Molter, Rolf Niedermeier, Viktor Zamaraev, and Philipp Zschoche. Computing Maximum Matchings in Temporal Graphs. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 27:1-27:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.STACS.2020.27

Abstract

Temporal graphs are graphs whose topology is subject to discrete changes over time. Given a static underlying graph G, a temporal graph is represented by assigning a set of integer time-labels to every edge e of G, indicating the discrete time steps at which e is active. We introduce and study the complexity of a natural temporal extension of the classical graph problem Maximum Matching, taking into account the dynamic nature of temporal graphs. In our problem, Maximum Temporal Matching, we are looking for the largest possible number of time-labeled edges (simply time-edges) (e,t) such that no vertex is matched more than once within any time window of Δ consecutive time slots, where Δ ∈ ℕ is given. The requirement that a vertex cannot be matched twice in any Δ-window models some necessary "recovery" period that needs to pass for an entity (vertex) after being paired up for some activity with another entity. We prove strong computational hardness results for Maximum Temporal Matching, even for elementary cases. To cope with this computational hardness, we mainly focus on fixed-parameter algorithms with respect to natural parameters, as well as on polynomial-time approximation algorithms.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
  • Theory of computation → Fixed parameter tractability
  • Theory of computation → Approximation algorithms analysis
Keywords
  • Temporal Graph
  • Link Stream
  • Temporal Line Graph
  • NP-hardness
  • APX-hardness
  • Approximation Algorithm
  • Fixed-parameter Tractability
  • Independent Set

Metrics

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

Related Versions

References

  1. E. C. Akrida, G. B. Mertzios, P. G. Spirakis, and V. Zamaraev. Temporal vertex cover with a sliding time window. J. Comput. Syst. Sci., 107:108-123, 2020. Google Scholar
  2. P. Alimonti and V. Kann. Some APX-completeness results for cubic graphs. Theor. Comput. Sci., 237(1-2):123-134, 2000. Google Scholar
  3. J. Aronson, M. Dyer, A. Frieze, and S. Suen. Randomized greedy matching ii. Random Struct. Algorithms, 6(1):55-73, 1995. Google Scholar
  4. G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, and M. Protasi. Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer, 2012. Google Scholar
  5. E. Bampis, B. Escoffier, M. Lampis, and V. Th. Paschos. Multistage matchings. In Proc. of 16th SWAT, volume 101 of LIPIcs, pages 7:1-7:13. Schloss Dagstuhl - LZI, 2018. Google Scholar
  6. J. Baste, B. Bui-Xuan, and A. Roux. Temporal matching. Theor. Comput. Sci., 806:184-196, 2020. Google Scholar
  7. M. Bentert, A-S. Himmel, H. Molter, M. Morik, R. Niedermeier, and R. Saitenmacher. Listing all maximal k-plexes in temporal graphs. ACM J. Exp. Algorithmics, 24(1):1-13, 2019. Google Scholar
  8. R. van Bevern, O. Y. Tsidulko, and P. Zschoche. Fixed-parameter algorithms for maximum-profit facility location under matroid constraints. In Proc. of 11th CIAC, volume 11485 of LNCS, pages 62-74. Springer, 2019. Google Scholar
  9. B. N. Clark, C. J. Colbourn, and D. S. Johnson. Unit disk graphs. Discrete Math., 86(1-3):165-177, 1990. Google Scholar
  10. F. V. Fomin, D. Lokshtanov, F. Panolan, and S. Saurabh. Efficient computation of representative families with applications in parameterized and exact algorithms. J. ACM, 63(4):29:1-29:60, 2016. Google Scholar
  11. M. R. Garey and D. S. Johnson. The rectilinear Steiner tree problem is NP-complete. SIAM J. Appl. Math., 32(4):826-834, 1977. Google Scholar
  12. A. Gupta, K. Talwar, and U. Wieder. Changing bases: Multistage optimization for matroids and matchings. In Proc. of 41st ICALP, volume 8572 of LNCS, pages 563-575. Springer, 2014. Google Scholar
  13. D. Hausmann and B. Korte. k-greedy algorithms for independence systems. Oper. Res., 22(1):219-228, 1978. Google Scholar
  14. A-S. Himmel, H. Molter, R. Niedermeier, and M. Sorge. Adapting the bron-kerbosch algorithm for enumerating maximal cliques in temporal graphs. Soc. Netw. Anal. Min., 7(1):35:1-35:16, 2017. Google Scholar
  15. P. Holme and J. Saramäki. Temporal networks. Physics Reports, 519(3):97-125, 2012. Google Scholar
  16. D. Kempe, J. Kleinberg, and A. Kumar. Connectivity and inference problems for temporal networks. J. Comput. Syst. Sci., 64(4):820-842, 2002. Google Scholar
  17. B. Korte and D. Hausmann. An analysis of the greedy heuristic for independence systems. Discrete Math., 2:65-74, 1978. Google Scholar
  18. M. Latapy, T. Viard, and C. Magnien. Stream graphs and link streams for the modeling of interactions over time. Soc. Netw. Anal. Min., 8(1):61, 2018. Google Scholar
  19. G. B. Mertzios, H. Molter, and V. Zamaraev. Sliding window temporal graph coloring. In Proc. of 33rd AAAI, pages 7667-7674. AAAI Press, 2019. Google Scholar
  20. M. Poloczek and M. Szegedy. Randomized greedy algorithms for the maximum matching problem with new analysis. In Proc. of 53rd FOCS, pages 708-717. IEEE, 2012. Google Scholar
  21. A. Schrijver. Bipartite edge coloring in O(Δm) time. SIAM J. Comput., 28(3):841-846, 1998. Google Scholar
  22. L. G. Valiant. Universality considerations in VLSI circuits. IEEE Trans. Comput., 100(2):135-140, 1981. Google Scholar
  23. H. Wu, J. Cheng, Y. Ke, S. Huang, Y. Huang, and H. Wu. Efficient algorithms for temporal path computation. IEEE Trans. Knowl. Data. Eng., 28(11):2927-2942, 2016. Google Scholar
  24. P. Zschoche, T. Fluschnik, H. Molter, and R. Niedermeier. The complexity of finding small separators in temporal graphs. J. Comput. Syst. Sci., 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 About DROPS Imprint Privacy Contact