×

zbMATH — the first resource for mathematics

The complexity of finding small separators in temporal graphs. (English) Zbl 1436.68265
Summary: Temporal graphs have time-stamped edges. Building on previous work, we study the problem of finding a small vertex set (the separator) whose removal destroys all temporal paths between two designated terminal vertices. Herein, we consider two models of temporal paths: those that pass through arbitrarily many edges per time step (non-strict) and those that pass through at most one edge per time step (strict). Regarding the number of time steps of a temporal graph, we show a complexity dichotomy (NP-completeness versus polynomial-time solvability) for both problem variants. Moreover, we prove both problem variants to be NP-complete even on temporal graphs whose underlying graph is planar. Finally, we introduce the notion of a temporal core (vertices whose incident edges change over time) and prove that the non-strict variant is fixed-parameter tractable when parameterized by the temporal core size, while the strict variant remains NP-complete, even for constant-size temporal cores.
MSC:
68R10 Graph theory (including graph drawing) in computer science
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q25 Analysis of algorithms and problem complexity
68Q27 Parameterized complexity, tractability and kernelization
Software:
cliques
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ahuja, R. K.; Magnanti, T. L.; Orlin, J. B., Network Flows: Theory, Algorithms and Applications (1993), Prentice Hall · Zbl 1201.90001
[2] 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
[3] Akrida, E. C.; Mertzios, G. B.; Spirakis, P. G.; Zamaraev, V., Temporal vertex cover with a sliding time window, (Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP ’18). Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP ’18), LIPIcs, vol. 107 (2018), Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik), Article 148 pp.
[4] Akrida, E. C.; Czyzowicz, J.; Gąsieniec, L.; Kuszner, Ł.; Spirakis, P. G., Temporal flows in temporal networks, J. Comput. Syst. Sci., 103, 46-60 (2019) · Zbl 1423.68324
[5] Arnborg, S.; Lagergren, J.; Seese, D., Easy problems for tree-decomposable graphs, J. Algorithms, 12, 2, 308-340 (1991) · Zbl 0734.68073
[6] Axiotis, K.; Fotakis, D., On the size and the approximability of minimum temporally connected subgraphs, (Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP ’16) (2016), Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik), Article 149 pp. · Zbl 1388.68299
[7] Baier, G.; Erlebach, T.; Hall, A.; Köhler, E.; Kolman, P.; Pangrác, O.; Schilling, H.; Skutella, M., Length-bounded cuts and flows, ACM Trans. Algorithms, 7, 1, Article 4 pp. (2010) · Zbl 1295.68119
[8] Bentert, M.; Himmel, A.-S.; Molter, H.; Morik, M.; Niedermeier, R.; Saitenmacher, R., Listing all maximal k-plexes in temporal graphs, (Proceedings of the 2018 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, (ASONAM ’18) (2018), IEEE Computer Society). (Proceedings of the 2018 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, (ASONAM ’18) (2018), IEEE Computer Society), ACM J. Exp. Algorithmics, 41-46 (2019), Long version to appear at
[9] Berman, K. A., Vulnerability of scheduled networks and a generalization of Menger’s Theorem, Networks, 28, 3, 125-134 (1996) · Zbl 0865.90048
[10] Boccaletti, S.; Bianconi, G.; Criado, R.; Del Genio, C. I.; Gómez-Gardenes, J.; Romance, M.; Sendina-Nadal, I.; Wang, Z.; Zanin, M., The structure and dynamics of multilayer networks, Phys. Rep., 544, 1, 1-122 (2014)
[11] Casteigts, A.; Flocchini, P., Deterministic Algorithms in Dynamic Networks: Formal Models and Metrics (April 2013), Defence R&D Canada, Technical Report
[12] Casteigts, A.; Flocchini, P., Deterministic Algorithms in Dynamic Networks: Problems, Analysis, and Algorithmic Tools (April 2013), Defence R&D Canada, Technical Report
[13] 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)
[14] Chen, J.; Molter, H.; Sorge, M.; Suchý, O., Cluster editing in multi-layer and temporal graphs, (Proceedings of the 29th International Symposium on Algorithms and Computation (ISAAC ’18). Proceedings of the 29th International Symposium on Algorithms and Computation (ISAAC ’18), LIPIcs, vol. 123 (2018), Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik), Article 24 pp.
[15] Corley, H.; Sha, D. Y., Most vital links and nodes in weighted networks, Oper. Res. Lett., 1, 4, 157-160 (1982) · Zbl 0488.90069
[16] Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C., Introduction to Algorithms (2009), MIT Press · Zbl 1187.68679
[17] Courcelle, B.; Engelfriet, J., Graph Structure and Monadic Second-order Logic: A Language-Theoretic Approach (2012), Cambridge University Press · Zbl 1257.68006
[18] Cygan, M.; Pilipczuk, M.; Pilipczuk, M.; Wojtaszczyk, J. O., On multiway cut parameterized above lower bounds, ACM Trans. Comput. Theory, 5, 1, Article 3 pp. (2013) · Zbl 1322.68098
[19] Cygan, M.; Fomin, F. V.; Kowalik, Ł.; Lokshtanov, D.; Marx, D.; Pilipczuk, M.; Pilipczuk, M.; Saurabh, S., Parameterized Algorithms (2015), Springer · Zbl 1334.90001
[20] Diestel, R., Graph Theory, Graduate Texts in Mathematics, vol. 173 (2016), Springer
[21] Downey, R. G.; Fellows, M. R., Fundamentals of Parameterized Complexity (2013), Springer · Zbl 1358.68006
[22] Erlebach, T.; Spooner, J. T., Faster exploration of degree-bounded temporal graphs, (Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS ’18). Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS ’18), LIPIcs, vol. 117 (2018), Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik), Article 36 pp.
[23] Erlebach, T.; Hoffmann, M.; Kammer, F., On temporal graph exploration, (Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP ’15). Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP ’15), Lecture Notes in Computer Science, vol. 9134 (2015), Springer), 444-455 · Zbl 1440.68186
[24] Ferreira, A., Building a reference combinatorial model for MANETs, IEEE Netw., 18, 5, 24-29 (2004)
[25] Flum, J.; Grohe, M., Parameterized Complexity Theory (2006), Springer-Verlag: Springer-Verlag Berlin
[26] Fluschnik, T.; Hermelin, D.; Nichterlein, A.; Niedermeier, R., Fractals for kernelization lower bounds, SIAM J. Discrete Math., 32, 1, 656-681 (2018) · Zbl 1388.68112
[27] Fluschnik, T.; Molter, H.; Niedermeier, R.; Renken, M.; Zschoche, P., Temporal graph classes: a view through temporal separators, Theor. Comput. Sci. (2019)
[28] Ford, L. R.; Fulkerson, D. R., Maximal flow through a network, Can. J. Math., 8, 3, 399-404 (1956) · Zbl 0073.40203
[29] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), W. H. Freeman · Zbl 0411.68039
[30] Golovach, P. A.; Thilikos, D. M., Paths of bounded length and their cuts: parameterized complexity and algorithms, Discrete Optim., 8, 1, 72-86 (2011) · Zbl 1248.90071
[31] Himmel, A.-S., Algorithmic Investigations into Temporal Paths (April 2018), TU Berlin, Master Thesis
[32] Himmel, A.-S.; Molter, H.; Niedermeier, R.; Sorge, M., Adapting the Bron-Kerbosch algorithm for enumerating maximal cliques in temporal graphs, Soc. Netw. Anal. Min., 7, 1, Article 35 pp. (2017)
[33] Holme, P., Modern temporal network theory: a colloquium, Eur. Phys. J. B, 88, 9, 234 (2015)
[34] Holme, P.; Saramäki, J., Temporal networks, Phys. Rep., 519, 3, 97-125 (2012)
[35] Kempe, D.; Kleinberg, J.; Kumar, A., Connectivity and inference problems for temporal networks, J. Comput. Syst. Sci., 64, 4, 820-842 (2002) · Zbl 1015.68005
[36] Latapy, M.; Viard, T.; Magnien, C., Stream graphs and link streams for the modeling of interactions over time, Soc. Netw. Anal. Min., 8, 1, Article 61 pp. (2018)
[37] Liang, Q.; Modiano, E., Survivability in time-varying networks, IEEE Trans. Mob. Comput., 16, 9, 2668-2681 (2017)
[38] Lovász, L.; Neumann-Lara, V.; Plummer, M., Mengerian theorems for paths of bounded length, Period. Math. Hung., 9, 4, 269-276 (1978) · Zbl 0393.05033
[39] Menger, K., Zur allgemeinen Kurventheorie, Fundam. Math., 10, 1, 96-115 (1927) · JFM 53.0561.01
[40] Mertzios, G. B.; Michail, O.; Chatzigiannakis, I.; Spirakis, P. G., Temporal network optimization subject to connectivity constraints, (Proceedings of the 40th International Colloquium on Automata, Languages, and Programming (ICALP ’13) (2013), Springer), 657-668 · Zbl 1334.68027
[41] Mertzios, G. B.; Molter, H.; Zamaraev, V., Sliding window temporal graph coloring, (Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI ’19) (2019), AAAI Press), 7667-7674
[42] Michail, O., An introduction to temporal graphs: an algorithmic perspective, Internet Math., 12, 4, 239-280 (2016)
[43] Michail, O.; Spirakis, P. G., Traveling salesman problems in temporal graphs, Theor. Comput. Sci., 634, 1-23 (2016) · Zbl 1338.90349
[44] Niedermeier, R., Invitation to Fixed-Parameter Algorithms (2006), Oxford University Press · Zbl 1095.68038
[45] Pan, F.; Schild, A., Interdiction problems on planar graphs, Discrete Appl. Math., 198, 215-231 (2016) · Zbl 1327.05234
[46] Scellato, S.; Leontiadis, I.; Mascolo, C.; Basu, P.; Zafer, M., Evaluating temporal robustness of mobile networks, IEEE Trans. Mob. Comput., 12, 1, 105-117 (2013)
[47] Schieber, B.; Bar-Noy, A.; Khuller, S., The Complexity of Finding Most Vital Arcs and Nodes (1995), College Park: College Park MD, USA, Technical Report
[48] Viard, T.; Latapy, M.; Magnien, C., Computing maximal cliques in link streams, Theor. Comput. Sci., 609, 245-252 (2016) · Zbl 1331.68158
[49] Wu, H.; Cheng, J.; Ke, Y.; Huang, S.; Huang, Y.; Wu, H., Efficient algorithms for temporal path computation, IEEE Trans. Knowl. Data Eng., 28, 11, 2927-2942 (2016)
[50] Zschoche, P., On Finding Separators in Temporal Graphs (April 2017), TU Berlin, Master Thesis
[51] Zschoche, P.; Fluschnik, T.; Molter, H.; Niedermeier, R., The complexity of finding small separators in temporal graphs, (Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018), LIPIcs, vol. 117 (2018), Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik), Article 45 pp.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.