Document Open Access Logo

Temporal Vertex Cover with a Sliding Time Window

Authors Eleni C. Akrida , George B. Mertzios , Paul G. Spirakis , Viktor Zamaraev



PDF
Thumbnail PDF

File

LIPIcs.ICALP.2018.148.pdf
  • Filesize: 0.52 MB
  • 14 pages

Document Identifiers

Author Details

Eleni C. Akrida
  • Department of Computer Science, University of Liverpool, UK
George B. Mertzios
  • Department of Computer Science, Durham University, UK
Paul G. Spirakis
  • Department of Computer Science, University of Liverpool, UK, Department of Computer Engineering & Informatics, University of Patras, Greece
Viktor Zamaraev
  • Department of Computer Science, Durham University, UK

Cite AsGet BibTex

Eleni C. Akrida, George B. Mertzios, Paul G. Spirakis, and Viktor Zamaraev. Temporal Vertex Cover with a Sliding Time Window. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 148:1-148:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ICALP.2018.148

Abstract

Modern, inherently dynamic systems are usually characterized by a network structure, i.e. an underlying graph topology, which is subject to discrete changes over time. Given a static underlying graph G, a temporal graph can be represented via an assignment of a set of integer time-labels to every edge of G, indicating the discrete time steps when this edge is active. While most of the recent theoretical research on temporal graphs has focused on the notion of a temporal path and other "path-related" temporal notions, only few attempts have been made to investigate "non-path" temporal graph problems. In this paper, motivated by applications in sensor and in transportation networks, we introduce and study two natural temporal extensions of the classical problem Vertex Cover. In our first problem, Temporal Vertex Cover, the aim is to cover every edge at least once during the lifetime of the temporal graph, where an edge can only be covered by one of its endpoints at a time step when it is active. In our second, more pragmatic variation Sliding Window Temporal Vertex Cover, we are also given a natural number Delta, and our aim is to cover every edge at least once at every Delta consecutive time steps. In both cases we wish to minimize the total number of "vertex appearances" that are needed to cover the whole graph. We present a thorough investigation of the computational complexity and approximability of these two temporal covering problems. In particular, we provide strong hardness results, complemented by various approximation and exact algorithms. Some of our algorithms are polynomial-time, while others are asymptotically almost optimal under the Exponential Time Hypothesis (ETH) and other plausible complexity assumptions.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph theory
  • Mathematics of computing → Graph algorithms
Keywords
  • Temporal networks
  • temporal vertex cover
  • APX-hard
  • approximation algorithm
  • Exponential Time Hypothesis

Metrics

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

References

  1. Eric Aaron, Danny Krizanc, and Elliot Meyerson. DMVP: foremost waypoint coverage of time-varying graphs. In Proceedings of the 40th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), pages 29-41, 2014. Google Scholar
  2. 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
  3. 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
  4. 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
  5. 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.
  6. 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.
  7. Arnaud Casteigts, Paola Flocchini, Walter Quattrociocchi, and Nicola Santoro. Time-varying graphs and dynamic networks. International Journal of Parallel, Emergent and Distributed Systems (IJPEDS), 27(5):387-408, 2012. Google Scholar
  8. Arnaud Casteigts, Bernard Mans, and Luke Mathieson. On the feasibility of maintenance algorithms in dynamic graphs. CoRR, abs/1107.2722, 2011. URL: http://arxiv.org/abs/1107.2722.
  9. Rong chii Duh and Martin Fürer. Approximation of k-set cover by semi-local optimization. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing (STOC), pages 256-264, 1997. Google Scholar
  10. Andrea E. F. Clementi, Claudio Macci, Angelo Monti, Francesco Pasquale, and Riccardo Silvestri. Flooding time of edge-markovian evolving graphs. SIAM Journal on Discrete Mathematics (SIDMA), 24(4):1694-1712, 2010. Google Scholar
  11. Stefan Dobrev, Stephane Durocher, Mohsen Eftekhari Hesari, Konstantinos Georgiou, Evangelos Kranakis, Danny Krizanc, Lata Narayanan, Jaroslav Opatrny, Sunil M. Shende, and Jorge Urrutia. Complexity of barrier coverage with relocatable sensors in the plane. Theoretical Computer Science, 579:64-73, 2015. Google Scholar
  12. 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
  13. Afonso Ferreira. Building a reference combinatorial model for MANETs. IEEE Network, 18(5):24-29, 2004. Google Scholar
  14. Paola Flocchini, Bernard Mans, and Nicola Santoro. Exploration of periodically varying graphs. In Proceedings of the 20th International Symposium on Algorithms and Computation (ISAAC), pages 534-543, 2009. Google Scholar
  15. George Giakkoupis, Thomas Sauerwald, and Alexandre Stauffer. Randomized rumor spreading in dynamic graphs. In Proceedings of the 41st International Colloquium on Automata, Languages and Programming (ICALP), pages 495-507, 2014. Google Scholar
  16. Mohsen Eftekhari Hesari, Evangelos Kranakis, Danny Krizanc, Oscar Morales Ponce, Lata Narayanan, Jaroslav Opatrny, and Sunil M. Shende. Distributed algorithms for barrier coverage using relocatable sensors. Distributed Computing, 29(5):361-376, 2016. Google Scholar
  17. 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
  18. P. Holme and J. Saramäki, editors. Temporal Networks. Springer, 2013. Google Scholar
  19. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? Journal of Computer and System Sciences, 63(4):512-530, 2001. Google Scholar
  20. David Kempe, Jon M. Kleinberg, and Amit Kumar. Connectivity and inference problems for temporal networks. In Proceedings of the 32nd annual ACM symposium on Theory of computing (STOC), pages 504-513, 2000. Google Scholar
  21. Orestis Kostakis and Aristides Gionis. On mining temporal patterns in dynamic graphs, and other unrelated problems. In Proceedings of the 6th International Conference on Complex Networks and Their Applications (COMPLEX NETWORKS), pages 516-527, 2017. Google Scholar
  22. Orestis Kostakis, Nikolaj Tatti, and Aristides Gionis. Discovering recurring activity in temporal networks. Data Mining and Knowledge Discovery, 31(6):1840-1871, 2017. Google Scholar
  23. Evangelos Kranakis, Danny Krizanc, Flaminia L. Luccio, and Brett Smith. Maintaining intruder detection capability in a rectangular domain with sensors. In Proceedings of the 11th International Symposium on Algorithms and Experiments for Wireless Sensor Networks (ALGOSENSORS), pages 27-40, 2015. Google Scholar
  24. Jure Leskovec, Jon M. Kleinberg, and Christos Faloutsos. Graph evolution: Densification and shrinking diameters. ACM Transactions on Knowledge Discovery from Data, 1(1), 2007. Google Scholar
  25. 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), Part II, pages 657-668, 2013. Google Scholar
  26. Othon Michail and Paul G. Spirakis. Traveling salesman problems in temporal graphs. Theoretical Computer Science, 634:1-23, 2016. Google Scholar
  27. Othon Michail and Paul G. Spirakis. Elements of the theory of dynamic networks. Communications of the ACM, 61(2):72-72, 2018. Google Scholar
  28. Sotiris E. Nikoletseas and Paul G. Spirakis. Probabilistic distributed algorithms for energy efficient routing and tracking in wireless sensor networks. Algorithms, 2(1):121-157, 2009. URL: http://dx.doi.org/10.3390/a2010121.
  29. John Kit Tang, Mirco Musolesi, Cecilia Mascolo, and Vito Latora. Characterising temporal distance and reachability in mobile and online social networks. ACM Computer Communication Review, 40(1):118-124, 2010. Google Scholar
  30. Vijay V. Vazirani. Approximation algorithms. Springer, 2003. Google Scholar
  31. Jordan Viard, Matthieu Latapy, and Clémence Magnien. Revealing contact patterns among high-school students using maximal cliques in link streams. In Proceedings of the 2015 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM), pages 1517-1522, 2015. Google Scholar
  32. Tiphaine Viard, Matthieu Latapy, and Clémence Magnien. Computing maximal cliques in link streams. Theoretical Computer Science, 609:245-252, 2016. Google Scholar
  33. Chuan Zhu, Chunlin Zheng, Lei Shu, and Guangjie Han. A survey on coverage and connectivity issues in wireless sensor networks. Journal of Network and Computer Applications, 35(2):619-632, 2012. 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