SpringerLink
Log in

Multi-Parameter Analysis of Finding Minors and Subgraphs in Edge-Periodic Temporal Graphs

  • Conference paper
  • First Online:
SOFSEM 2023: Theory and Practice of Computer Science (SOFSEM 2023)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 13878))

Abstract

We study the computational complexity of determining structural properties of edge-periodic temporal graphs (EPGs). EPGs are time-varying graphs that compactly represent periodic behavior of components of a dynamic network, for example, train schedules on a rail network. In EPGs, for each edge e of the graph, a binary string \(s_e\) determines in which time steps the edge is present, namely e is present in time step t if and only if \(s_e\) contains a 1 at position \(t \mod |s_e|\). Due to this periodicity, EPGs serve as very compact representations of complex periodic systems and can even be exponentially smaller than classic temporal graphs representing one period of the same system, as the latter contain the whole sequence of graphs explicitly. In this paper, we study the computational complexity of fundamental questions of the new concept of EPGs such as is there a time step or a sliding window of size \(\Delta \) in which the graph (1) is minor-free; (2) contains a minor; (3) is subgraph-free; (4) contains a subgraph; with respect to a given minor or subgraph. We give a detailed parameterized analysis for multiple combinations of parameters for the problems stated above including several algorithms.

E. Arrighi—Supported by Research Council of Norway (no. 274526 and 329745) and IS-DAAD (no. 309319).

N. Morawietz—Supported by DFG project OPERAH (KO 3669/5–1).

F. Sommer—Supported by DFG project EAGR (KO 3669/6–1).

P. Wolf—The research was mainly performed when the author was associated with University of Trier, Germany, and supported by DFG project FE 560/9–1 and DAAD PPP (no. 57525246).

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 64.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 84.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free ship** worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Akrida, E.C., Mertzios, G.B., Nikoletseas, S.E., Raptopoulos, C.L., Spirakis, P.G., Zamaraev, V.: How fast can we reach a target vertex in stochastic temporal graphs? J. Comput. Syst. Sci. 114, 65–83 (2020)

    Article  MathSciNet  MATH  Google Scholar 

  2. Akrida, E.C., Mertzios, G.B., Spirakis, P.G., Zamaraev, V.: Temporal vertex cover with a sliding time window. J. Comput. Syst. Sci. 107, 108–123 (2020)

    Article  MathSciNet  MATH  Google Scholar 

  3. Babai, L., Luks, E.M.: Canonical labeling of graphs. In: Johnson, D.S., et al. eds, Proceedings of the 15th Annual ACM Symposium on Theory of Computing, Boston, Massachusetts, USA, pp. 171–183. ACM (1983)

    Google Scholar 

  4. Berman, K.A.: Vulnerability of scheduled networks and a generalization of Menger’s theorem. Networks 28(3), 125–134 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  5. Bhadra, S., Ferreira, A.: Complexity of connected components in evolving graphs and the computation of multicast trees in dynamic networks. In: Pierre, S., Barbeau, M., Kranakis, E. (eds.) ADHOC-NOW 2003. LNCS, vol. 2865, pp. 259–270. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-39611-6_23

    Chapter  Google Scholar 

  6. Casteigts, A., Flocchini, P.: Deterministic algorithms in dynamic networks: formal models and metrics. Technical Report (2013)

    Google Scholar 

  7. Casteigts, A., Flocchini, P.: Deterministic algorithms in dynamic networks: problems, analysis, and algorithmic tools. Technical Report (2013)

    Google Scholar 

  8. Casteigts, A., Flocchini, P., Quattrociocchi, W., Santoro, N.: Time-varying graphs and dynamic networks. Int. J. Parallel Emergent Distrib. Syst. 27(5), 387–408 (2012)

    Article  Google Scholar 

  9. Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-21275-3

    Book  MATH  Google Scholar 

  10. de Roever, W.-P., Langmaack, H., Pnueli, A. (eds.): COMPOS 1997. LNCS, vol. 1536. Springer, Heidelberg (1998). https://doi.org/10.1007/3-540-49213-5

    Book  Google Scholar 

  11. Ding, B., Yu, J.X., Qin, L.: Finding time-dependent shortest paths over large graphs. In: Kemper, A., et al. eds, Proceedings of the 11th International Conference on Extending Database Technology, vol. 261 of ACM International Conference Proceeding Series, pp. 205–216. ACM (2008)

    Google Scholar 

  12. Erlebach, T., Spooner, J.T.: A game of cops and robbers on graphs with periodic edge-connectivity. In: Chatzigeorgiou, A., Dondi, R., Herodotou, H., Kapoutsis, C., Manolopoulos, Y., Papadopoulos, G.A., Sikora, F. (eds.) SOFSEM 2020. LNCS, vol. 12011, pp. 64–75. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-38919-2_6

    Chapter  MATH  Google Scholar 

  13. Frank, A., Tardos, É.: An application of simultaneous diophantine approximation in combinatorial optimization. Combinatorica 7(1), 49–65 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  14. Ganguly, N., Deutsch, A., Mukherjee, A.: Dyn. Complex Netw. Computer Science, and the Social Sciences, Applications to Biology (2009)

    Google Scholar 

  15. Holme, P.: Modern temporal network theory: a colloquium. Eur. Phys. J. B 88(9), 1–30 (2015)

    Article  Google Scholar 

  16. Holme, P., Saramäki, J.: Temporal networks. Phys. Rep. 519(3), 97–125 (2012)

    Article  Google Scholar 

  17. Jecker, I., Mazzocchi, N., Wolf,P.: Decomposing permutation automata. In: Haddad, S., Varacca, D., eds, 32nd International Conference on Concurrency Theory, CONCUR 2021, Virtual Conference, vol. 203 of LIPIcs, pp. 18:1–18:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)

    Google Scholar 

  18. Hendrik, W., Lenstra: Integer programming with a fixed number of variables. Math. Oper. Res. 8(4), 538–548 (1983)

    Google Scholar 

  19. Kannan, R.: Minkowski’s convex body theorem and integer programming. Math. Oper. Res. 12(3), 415–440 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  20. Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of Computer Computations, pp. 85–103 (1972)

    Google Scholar 

  21. Kempe, D., Kleinberg, J.M., Kumar, A.: Connectivity and inference problems for temporal networks. J. Comput. Syst. Sci. 64(4), 820–842 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  22. Leskovec, J., Krevl, A.: SNAP datasets: stanford large network dataset collection. http://snap.stanford.edu/data/ (2014)

  23. Lovász, L.: Graph minor theory. Bull. Am. Math. Soc. 43(1), 75–86 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  24. Mertzios, G.B., Michail, O., Spirakis, P.G.: Temporal network optimization subject to connectivity constraints. Algorithmica 81(4), 1416–1449 (2019)

    Article  MathSciNet  MATH  Google Scholar 

  25. Mertzios, G.B., Molter, H., Zamaraev, V.: Sliding window temporal graph coloring. J. Comput. Syst. Sci. 120, 97–115 (2021)

    Article  MathSciNet  MATH  Google Scholar 

  26. Michail, O., Spirakis, P.G.: Traveling salesman problems in temporal graphs. Theoret. Comput. Sci. 634, 1–23 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  27. Michail, O., Spirakis, P.G.: Elements of the theory of dynamic networks. Commun. ACM 61(2), 72 (2018)

    Article  Google Scholar 

  28. Morawietz, N., Rehs, C., Weller, M.: A timecop’s work is harder than you think. In: Esparza, J., Král’, D., eds, 45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020, Prague, Czech Republic, vol. 170 of LIPIcs, pp. 71:1–71:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)

    Google Scholar 

  29. Morawietz, N., Wolf, P.: A timecop’s chase around the table. In: Bonchi, F., Puglisi, S.J., eds, 46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021, Tallinn, Estonia, vol. 202 of LIPIcs, pp. 77:1–77:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)

    Google Scholar 

  30. Pagin, P.: Compositionality, computability, and complexity. Rev. Symbolic Logic 14(3), 551–591 (2021)

    Article  MathSciNet  MATH  Google Scholar 

  31. Robertson, N., Seymour, P.D.: Graph Minors. XIII. The Disjoint Paths Problem. J. Comb. Theory Ser. B 63(1), 65–110 (1995)

    Google Scholar 

  32. Sapiezynski, P., Stopczynski, A., Gatej, R., Lehmann, S.: Tracking human mobility using WiFi signals. PLoS ONE 10(7), 1–11 (2015)

    Article  Google Scholar 

  33. Wehmuth, K., Ziviani, A., Fleury, E.: A unifying model for representing time-varying graphs. In: 2015 IEEE International Conference on Data Science and Advanced Analytics, DSAA 2015, Campus des Cordeliers, Paris, France, pp. 1–10. IEEE (2015)

    Google Scholar 

  34. Huanhuan, W., Cheng, J., Huang, S., Ke, Y., Yi, L., Yanyan, X.: Path problems in temporal graphs. Proc. VLDB Endowment 7(9), 721–732 (2014)

    Article  Google Scholar 

  35. Zhang, Z.: Routing in intermittently connected mobile ad hoc networks and delay tolerant networks: overview and challenges. IEEE Commun. Surv. Tutorials 8(1–4), 24–37 (2006)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. University of Bergen, Bergen, Norway

    Emmanuel Arrighi & Petra Wolf

  2. Philipps-Universität Marburg, Marburg, Germany

    Niels Grüttemeier, Nils Morawietz & Frank Sommer

Authors
  1. Emmanuel Arrighi
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Niels Grüttemeier
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Nils Morawietz
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Frank Sommer
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Petra Wolf
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Frank Sommer .

Editor information

Editors and Affiliations

  1. University of Liverpool, Liverpool, UK

    Leszek Gąsieniec

Rights and permissions

Reprints and permissions

Copyright information

© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Arrighi, E., Grüttemeier, N., Morawietz, N., Sommer, F., Wolf, P. (2023). Multi-Parameter Analysis of Finding Minors and Subgraphs in Edge-Periodic Temporal Graphs. In: Gąsieniec, L. (eds) SOFSEM 2023: Theory and Practice of Computer Science. SOFSEM 2023. Lecture Notes in Computer Science, vol 13878. Springer, Cham. https://doi.org/10.1007/978-3-031-23101-8_19

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-23101-8_19

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-23100-1

  • Online ISBN: 978-3-031-23101-8

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation