×

zbMATH — the first resource for mathematics

Temporal graph classes: a view through temporal separators. (English) Zbl 1436.68234
Summary: We investigate for temporal graphs the computational complexity of separating two distinct vertices \(s\) and \(z\) by vertex deletion. In a temporal graph, the vertex set is fixed but the edges have (discrete) time labels. Since the corresponding Temporal \((s, z)\)-Separation problem is NP-complete, it is natural to investigate whether relevant special cases exist that are computationally tractable. To this end, we study restrictions of the underlying (static) graph – there we observe polynomial-time solvability in the case of bounded treewidth – as well as restrictions concerning the “temporal evolution” along the time steps. Systematically studying partially novel concepts in this direction, we identify sharp borders between tractable and intractable cases.

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
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Akrida, E. C.; Czyzowicz, J.; Gąsieniec, L.; Kuszner, Ł.; Spirakis, P. G., Temporal flows in temporal networks, (LNCS, vol. 10236 (2017), Springer), 43-54 · Zbl 06751050
[2] Akrida, E. C.; Gąsieniec, L.; Mertzios, G. B.; Spirakis, P. G., The complexity of optimal design of temporally connected graphs, Theory Comput. Syst., 61, 3, 907-944 (Oct 2017)
[3] 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). Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP ’16), LIPIcs, vol. 55 (2016), Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik), 149:1-149:14 · Zbl 1388.68299
[4] Barrat, A.; Fournet, J., Contact patterns among high school students, PLoS ONE, 9, 9, Article e107878 pp. (2014)
[5] Beineke, L. W., Characterizations of derived graphs, J. Comb. Theory, 9, 2, 129-135 (1970) · Zbl 0202.55702
[6] Bodlaender, H. L.; Drange, P. G.; Dregi, M. S.; Fomin, F. V.; Lokshtanov, D.; Pilipczuk, M., A \(c^k n 5\)-approximation algorithm for treewidth, SIAM J. Comput., 45, 2, 317-378 (2016) · Zbl 1333.05282
[7] Booth, K. S.; Lueker, G. S., Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms, J. Comput. Syst. Sci., 13, 3, 335-379 (1976) · Zbl 0367.68034
[8] Brandstadt, A.; Spinrad, J. P., Graph Classes: A Survey, vol. 3 (1999), SIAM
[9] Bui-Xuan, B.; 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] Cai, L., Parameterized complexity of vertex colouring, Discrete Appl. Math., 127, 3, 415-429 (2003) · Zbl 1015.05027
[11] 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)
[12] Cygan, M.; Fomin, F. V.; Kowalik, Ł.; Lokshtanov, D.; Marx, D.; Pilipczuk, M.; Pilipczuk, M.; Saurabh, S., Parameterized Algorithms (2015), Springer · Zbl 1334.90001
[13] Diestel, R., Graph Theory, Graduate Texts in Mathematics, vol. 173 (2016), Springer
[14] Downey, R. G.; Fellows, M. R., Fundamentals of Parameterized Complexity (2013), Springer · Zbl 1358.68006
[15] 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), LNCS, vol. 9134 (2015), Springer), 444-455 · Zbl 1440.68186
[16] Flocchini, P.; Mans, B.; Santoro, N., On the exploration of time-varying networks, Theor. Comput. Sci., 469, 53-68 (2013) · Zbl 1258.68103
[17] Flum, J.; Grohe, M., Parameterized Complexity Theory, Texts in Theoretical Computer Science. An EATCS Series, vol. XIV (2006), Springer Verlag: Springer Verlag Berlin
[18] Fluschnik, T.; Molter, H.; Niedermeier, R.; Zschoche, P., Temporal graph classes: a view through temporal separators, (Proceedings of the 44th International Workshop on Graph-Theoretic Concepts in Computer Science (WG’18). Proceedings of the 44th International Workshop on Graph-Theoretic Concepts in Computer Science (WG’18), LNCS, vol. 11159 (2018), Springer), 216-227 · Zbl 1436.68235
[19] Guo, J.; Hüffner, F.; Niedermeier, R., A structural view on parameterizing problems: distance from triviality, (Proceedings of the 1st International Workshop on Parameterized and Exact Computation (IWPEC ’04) (2004), Springer), 162-173 · Zbl 1104.68050
[20] 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
[21] Kendall, M. G., A new measure of rank correlation, Biometrika, 30, 1/2, 81-93 (1938) · Zbl 0019.13001
[22] A. Khodaverdian, B. Weitz, J. Wu, N. Yosef, Steiner network problems on temporal graphs, CoRR, 2016, abs/1609.04918v2.
[23] Kuhn, F.; Lynch, N. A.; Oshman, R., Distributed computation in dynamic networks, (Proceedings of the 42nd Annual ACM Symposium on Theory of Computing (STOC ’10) (2010), ACM), 513-522 · Zbl 1293.68305
[24] Liu, C.; Wu, J., Scalable routing in cyclic mobile networks, IEEE Trans. Parallel Distrib. Syst., 20, 9, 1325-1338 (2009)
[25] Looges, P. J.; Olariu, S., Optimal greedy algorithms for indifference graphs, Comput. Math. Appl., 25, 7, 15-25 (1993) · Zbl 0794.68115
[26] 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). Proceedings of the 40th International Colloquium on Automata, Languages, and Programming (ICALP ’13), LNCS, vol. 7966 (2013), Springer), 657-668 · Zbl 1334.68027
[27] Michail, O., An introduction to temporal graphs: an algorithmic perspective, Internet Math., 12, 4, 239-280 (2016)
[28] Michail, O.; Spirakis, P. G., Traveling salesman problems in temporal graphs, Theor. Comput. Sci., 634, 1-23 (2016) · Zbl 1338.90349
[29] Nešetřil, J.; de Mendez, P. O., Sparsity: Graphs, Structures, and Algorithms (2012), Springer · Zbl 1268.05002
[30] Niedermeier, R., Invitation to Fixed-Parameter Algorithms (2006), Oxford University Press · Zbl 1095.68038
[31] 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)
[32] 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 ’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), 45:1-45:17, long version:
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.