×

Temporal vertex cover with a sliding time window. (English) Zbl 1436.68219

Summary: Modern, inherently dynamic systems are usually characterized by a network structure which is subject to discrete changes over time. Given a static underlying graph, a temporal graph can be represented via an assignment of a set of integer time-labels to every edge, indicating the discrete time steps when this edge is active. While most of the recent theoretical research on temporal graphs focused on temporal paths and other “path-related” temporal notions, only few attempts have been made to investigate “non-path” temporal problems. In this paper we introduce and study two natural temporal extensions of the classical problem VERTEX COVER. We present a thorough investigation of the computational complexity and approximability of these two temporal covering problems. We provide strong hardness results, complemented by 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.

MSC:

68R10 Graph theory (including graph drawing) in computer science
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W25 Approximation algorithms

Software:

cliques
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

References:

[1] Aaron, E.; Krizanc, D.; Meyerson, E., DMVP: foremost waypoint coverage of time-varying graphs, (Proceedings of the 40th International Workshop on Graph-Theoretic Concepts in Computer Science. Proceedings of the 40th International Workshop on Graph-Theoretic Concepts in Computer Science, WG (2014)), 29-41 · Zbl 1417.68048
[2] Akrida, E. C.; Gasieniec, L.; Mertzios, G. B.; Spirakis, P. G., Ephemeral networks with random availability of links: the case of fast networks, J. Parallel Distrib. Comput., 87, 109-120 (2016)
[3] Akrida, E. C.; Gasieniec, L.; Mertzios, G. B.; Spirakis, P. G., The complexity of optimal design of temporally connected graphs, Theory Comput. Syst., 61, 3, 907-944 (2017) · Zbl 1379.68250
[4] Akrida, E. C.; Mertzios, G. B.; Nikoletseas, S.; Raptopoulos, C.; Spirakis, P. G.; Zamaraev, V., How fast can we reach a target vertex in stochastic temporal graphs?, (Proceedings of the 46th International Colloquium on Automata, Languages and Programming. Proceedings of the 46th International Colloquium on Automata, Languages and Programming, ICALP (2019)), in press · Zbl 1509.68193
[5] Akrida, E. C.; Mertzios, G. B.; Spirakis, P. G., The temporal explorer who returns to the base, (Proceedings of the 11th International Conference on Algorithms and Complexity. Proceedings of the 11th International Conference on Algorithms and Complexity, CIAC ’19 (2019)), in press · Zbl 1477.68191
[6] Akrida, E. C.; Mertzios, G. B.; Spirakis, P. G.; Zamaraev, V., Temporal vertex covers and sliding time windows, (Proceedings of the 45th International Colloquium on Automata, Languages, and Programming. Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, ICALP (2018)), 148:1-148:14 · Zbl 1499.68243
[7] Alimonti, P.; Kann, V., Some APX-completeness results for cubic graphs, Theor. Comput. Sci., 237, 1-2, 123-134 (2000) · Zbl 0939.68052
[8] Baste, J.; Bui-Xuan, B.-M.; Roux, A., Temporal matching, Theor. Comput. Sci. (2019)
[9] Bui-Xuan, B.-M.; Ferreira, A.; Jarry, A., Computing shortest, fastest, and foremost journeys in dynamic networks, Int. J. Found. Comput. Sci., 14, 2, 267-285 (2003) · Zbl 1075.68545
[10] Casteigts, A.; Flocchini, P., Deterministic Algorithms in Dynamic Networks: Formal Models and Metrics (April 2013), Defence R&D Canada, Technical report
[11] Casteigts, A.; Flocchini, P., Deterministic Algorithms in Dynamic Networks: Problems, Analysis, and Algorithmic Tools (April 2013), Defence R&D Canada, Technical report
[12] Casteigts, A.; Flocchini, P.; Quattrociocchi, W.; Santoro, N., Time-varying graphs and dynamic networks, Int. J. Parallel Emerg. Distrib. Syst., 27, 5, 387-408 (2012)
[13] Casteigts, A.; Mans, B.; Mathieson, L., On the feasibility of maintenance algorithms in dynamic graphs (2011), Technical report, available at
[14] Duh, R. chii; Fürer, M., Approximation of \(k\)-set cover by semi-local optimization, (Proceedings of the 29th Annual ACM Symposium on Theory of Computing. Proceedings of the 29th Annual ACM Symposium on Theory of Computing, STOC (1997)), 256-264 · Zbl 0962.68172
[15] Clementi, A. E.F.; Macci, C.; Monti, A.; Pasquale, F.; Silvestri, R., Flooding time of edge-Markovian evolving graphs, SIAM J. Discrete Math., 24, 4, 1694-1712 (2010) · Zbl 1221.68170
[16] Cygan, M.; Dell, H.; Lokshtanov, D.; Marx, D.; Nederlof, J.; Okamoto, Y.; Paturi, R.; Saurabh, S.; Wahlström, M., On problems as hard as CNF-SAT, ACM Trans. Algorithms, 12, 3, 41:1-41:24 (2016) · Zbl 1442.68064
[17] Dobrev, S.; Durocher, S.; Hesari, M. E.; Georgiou, K.; Kranakis, E.; Krizanc, D.; Narayanan, L.; Opatrny, J.; Shende, S. M.; Urrutia, J., Complexity of barrier coverage with relocatable sensors in the plane, Theor. Comput. Sci., 579, 64-73 (2015) · Zbl 1312.68212
[18] Enright, J.; Meeks, K.; Mertzios, G. B.; Zamaraev, V., Deleting edges to restrict the size of an epidemic in temporal networks (2018), Technical report, available at
[19] Erlebach, T.; Hoffmann, M.; Kammer, F., On temporal graph exploration, (Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming. Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming, ICALP (2015)), 444-455 · Zbl 1440.68186
[20] Feige, U., A threshold of \(\ln n\) for approximating set cover, J. ACM, 45, 4, 634-652 (1998) · Zbl 1065.68573
[21] Ferreira, A., Building a reference combinatorial model for MANETs, IEEE Netw., 18, 5, 24-29 (2004)
[22] Flocchini, P.; Mans, B.; Santoro, N., Exploration of periodically varying graphs, (Proceedings of the 20th International Symposium on Algorithms and Computation. Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC (2009)), 534-543 · Zbl 1272.05196
[23] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), W. H. Freeman & Co.: W. H. Freeman & Co. New York, NY, USA · Zbl 0411.68039
[24] Giakkoupis, G.; Sauerwald, T.; Stauffer, A., Randomized rumor spreading in dynamic graphs, (Proceedings of the 41st International Colloquium on Automata, Languages and Programming. Proceedings of the 41st International Colloquium on Automata, Languages and Programming, ICALP (2014)), 495-507 · Zbl 1409.68214
[25] Hesari, M. E.; Kranakis, E.; Krizanc, D.; Ponce, O. M.; Narayanan, L.; Opatrny, J.; Shende, S. M., Distributed algorithms for barrier coverage using relocatable sensors, Distrib. Comput., 29, 5, 361-376 (2016) · Zbl 1405.68434
[26] Himmel, A.; Molter, H.; Niedermeier, R.; Sorge, M., Adapting the Bron-Kerbosch algorithm for enumerating maximal cliques in temporal graphs, Soc. Netw. Anal. Min., 7, 1, 35:1-35:16 (2017)
[27] (Holme, P.; Saramäki, J., Temporal Networks (2013), Springer)
[28] Impagliazzo, R.; Paturi, R., On the complexity of \(k\)-SAT, J. Comput. Syst. Sci., 62, 2, 367-375 (2001) · Zbl 0990.68079
[29] Impagliazzo, R.; Paturi, R.; Zane, F., Which problems have strongly exponential complexity?, J. Comput. Syst. Sci., 63, 4, 512-530 (2001) · Zbl 1006.68052
[30] Kempe, D.; Kleinberg, J. M.; Kumar, A., Connectivity and inference problems for temporal networks, (Proceedings of the 32nd Annual ACM Symposium on Theory of Computing. Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, STOC (2000)), 504-513 · Zbl 1296.68015
[31] Kostakis, O.; Gionis, A., On mining temporal patterns in dynamic graphs, and other unrelated problems, (Proceedings of the 6th International Conference on Complex Networks and Their Applications. Proceedings of the 6th International Conference on Complex Networks and Their Applications, COMPLEX NETWORKS (2017)), 516-527
[32] Kostakis, O.; Tatti, N.; Gionis, A., Discovering recurring activity in temporal networks, Data Min. Knowl. Discov., 31, 6, 1840-1871 (2017) · Zbl 1416.62700
[33] Kranakis, E.; Krizanc, D.; Luccio, F. L.; Smith, B., Maintaining intruder detection capability in a rectangular domain with sensors, (Proceedings of the 11th International Symposium on Algorithms and Experiments for Wireless Sensor Networks. Proceedings of the 11th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS (2015)), 27-40
[34] Leskovec, J.; Kleinberg, J. M.; Faloutsos, C., Graph evolution: densification and shrinking diameters, ACM Trans. Knowl. Discov. Data, 1, 1 (2007)
[35] Lokshtanov, D.; Marx, D.; Saurabh, S., Lower bounds based on the Exponential Time Hypothesis, Bull. Eur. Assoc. Theor. Comput. Sci., 41-71 (2011) · Zbl 1258.68068
[36] Mertzios, G. B.; Michail, O.; Chatzigiannakis, I.; Spirakis, P. G., Temporal network optimization subject to connectivity constraints, Algorithmica, 81, 4, 1416-1449 (2019) · Zbl 1421.68139
[37] Mertzios, G. B.; Molter, H.; Niedermeier, R.; Zamaraev, V.; Zschoche, P., Computing maximum matchings in temporal graphs (2019), Technical report, available at
[38] Mertzios, G. B.; Molter, H.; Zamaraev, V., Sliding window temporal graph coloring, (Proceedings of the 33rd AAAI Conference on Artificial Intelligence. Proceedings of the 33rd AAAI Conference on Artificial Intelligence, AAAI (2019)), in press · Zbl 1473.68123
[39] Michail, O.; Spirakis, P. G., Traveling salesman problems in temporal graphs, Theor. Comput. Sci., 634, 1-23 (2016) · Zbl 1338.90349
[40] Michail, O.; Spirakis, P. G., Elements of the theory of dynamic networks, Commun. ACM, 61, 2, 72 (Jan. 2018)
[41] Niedermeier, R.; Rossmanith, P., An efficient fixed-parameter algorithm for 3-hitting set, J. Discret. Algorithms, 1, 1, 89-102 (2003) · Zbl 1118.68511
[42] Nikoletseas, S. E.; Spirakis, P. G., Probabilistic distributed algorithms for energy efficient routing and tracking in wireless sensor networks, Algorithms, 2, 1, 121-157 (2009) · Zbl 1461.68255
[43] Rozenshtein, P.; Tatti, N.; Gionis, A., The network-untangling problem: from interactions to activity timelines, (Proceedings of the Joint European Conference on Machine Learning and Knowledge Discovery in Databases (2017)), 701-716
[44] Tang, J. K.; Musolesi, M.; Mascolo, C.; Latora, V., Characterising temporal distance and reachability in mobile and online social networks, ACM Comput. Commun. Rev., 40, 1, 118-124 (2010)
[45] Vazirani, V. V., Approximation Algorithms (2003), Springer · Zbl 1005.68002
[46] Viard, J.; Latapy, M.; Magnien, C., Revealing contact patterns among high-school students using maximal cliques in link streams, (Proceedings of the 2015 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining. Proceedings of the 2015 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM (2015)), 1517-1522
[47] Viard, T.; Latapy, M.; Magnien, C., Computing maximal cliques in link streams, Theor. Comput. Sci., 609, 245-252 (2016) · Zbl 1331.68158
[48] Zhu, C.; Zheng, C.; Shu, L.; Han, G., A survey on coverage and connectivity issues in wireless sensor networks, J. Netw. Comput. Appl., 35, 2, 619-632 (2012)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.