Abstract
Disconnecting two vertices s and z in a graph by removing a minimum number of vertices is a fundamental problem in algorithmic graph theory. This (s, z)-Separation problem is well-known to be polynomial solvable and serves as an important primitive in many applications related to network connectivity.
We study the NP-hard Temporal (s, z) -Separation problem on temporal graphs, which are graphs with fixed vertex sets but edge sets that change over discrete time steps. We tackle this problem by restricting the layers (i.e., graphs characterized by edges that are present at a certain point in time) to specific graph classes.
We restrict the layers of the temporal graphs to be either all split graphs or all permutation graphs (both being perfect graph classes) and provide both intractability and tractability results. In particular, we show that in general Temporal (s, z) -Separation remains NP-hard both on temporal split and temporal permutation graphs, but we also spot promising islands of fixed-parameter tractability particularly based on parameterizations that measure the amount of “change over time”.
Based on the Bachelor thesis of N. Maack. H. Molter was supported by the DFG, project MATE (NI 369/17), and by the ISF, grant No. 1070/20. Main part of this work was done while H. Molter was affiliated with TU Berlin. M. Renken was supported by the DFG, project MATE (NI 369/17).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Such walks are also called “non-strict”, whereas “strict” walks require \(t_i < t_{i+1}\). We focus on non-strict walks in this work.
- 2.
While the vertex set of a temporal graph formally remains unchanged, isolated vertices are equivalent to non-existing vertices as far as separators are concerned.
- 3.
We denote by \(\mathcal {G}- X\) the temporal graph resulting from removing vertices in X from the vertex set of \(\mathcal {G}\).
- 4.
Note that it is not sufficient for each layer to be isomorphic to a permutation graph.
References
Bender, E.A., Richmond, L.B., Wormald, N.C.: Almost all chordal graphs split. 38(2), 214–221 (1985). https://doi.org/10.1017/S1446788700023077
Bentert, M., Himmel, A.-S., Nichterlein, A., Niedermeier, R.: Efficient computation of optimal temporal walks under waiting-time constraints. Appl. Netw. Sci. 5(1), 73 (2020). https://doi.org/10.1007/s41109-020-00311-0
Bodlaender, H.L., Kloks, T., Kratsch, D.: Treewidth and pathwidth of permutation graphs. 8, 606–616 (1995). https://doi.org/10.1137/S089548019223992X
Borgatti, S.P., Everett, M.G.: Models of core/periphery structures. 21(4), 375–395 (2000). https://doi.org/10.1016/S0378-8733(99)00019-2
Brandstädt, A., Le, V.B., Spinrad, J.P.: Graph Classes–A Survey (1999). https://doi.org/10.1137/1.9780898719796
Xuan, B.B., Ferreira, A., Jarry, A.: Computing shortest, fastest, and foremost journeys in dynamic networks. 14(02), 267–285 (2003). https://doi.org/10.1142/S0129054103001728
Buß, S., Molter, H., Niedermeier, R., Rymar, M.: Algorithmic aspects of temporal betweenness, pp. 2084–2092 (2020). https://doi.org/10.1145/3394486.3403259
Enright, J., Meeks, K., Mertzios, G.B., Zamaraev, V.: Deleting edges to restrict the size of an epidemic in temporal networks, 119, 60–77 (2021) https://doi.org/10.1016/j.jcss.2021.01.007
Enright, J., Meeks, K., Skerman, F.: Assigning times to minimise reachability in temporal graphs, 115, 169–186 (2021). https://doi.org/10.1016/j.jcss.2020.08.001
Erlebach, T., Hoffmann, M., Kammer, F.: On temporal graph exploration. 119, 1–18 (2021). https://doi.org/10.1016/j.jcss.2021.01.005
Even, S., Pnueli, A., Lempel, A.: Permutation graphs and transitive graphs. 19(3), 400–410 (1972). https://doi.org/10.1145/321707.321710
Fluschnik, T., Molter, H., Niedermeier, R., Renken, M., Zschoche, P.: Temporal graph classes: a view through temporal separators. 806, 197–218 (2020). https://doi.org/10.1016/j.tcs.2019.03.031
Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs (2004). ISBN 978-0-444-51530-8
Guo, J., Hüffner, F., Niedermeier, R.: A structural view on parameterizing problems: distance from triviality. In: Downey, R., Fellows, M., Dehne, F. (eds.) IWPEC 2004. LNCS, vol. 3162, pp. 162–173. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-28639-4_15
Kempe, D., Kleinberg, J., Kumar, A.: Connectivity and inference problems for temporal networks. 64(4), 820–842 (2002). https://doi.org/10.1006/jcss.2002.1829
Kendall, M.G.: A new measure of rank correlation. 30(1/2), 81–93 (1938). https://doi.org/10.2307/2332226
Maack, N., Molter, H., Niedermeier, R., Renken, M.: On finding separators in temporal split and permutation graphs (2021). http://arxiv.org/abs/2105.12003
Mertzios, G.B., Michail, O., Chatzigiannakis, I., Spirakis, P.G.: Temporal network optimization subject to connectivity constraints. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013. LNCS, vol. 7966, pp. 657–668. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-39212-2_57
Niedermeier, R.: Invitation to fixed-parameter algorithms. (2006). https://doi.org/10.1093/ACPROF:OSO/9780198566076.001.0001
Sen, A., Deng, H., Guha, S.: On a graph partition problem with application to VLSI layout. 43(2), 87–94 (1992). https://doi.org/10.1016/0020-0190(92)90017-P
Zschoche, P., Fluschnik, T., Molter, H., Niedermeier, R.: The complexity of finding small separators in temporal graphs. 107, 72–92 (2020). https://doi.org/10.1016/j.jcss.2019.07.006
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Maack, N., Molter, H., Niedermeier, R., Renken, M. (2021). On Finding Separators in Temporal Split and Permutation Graphs. In: Bampis, E., Pagourtzis, A. (eds) Fundamentals of Computation Theory. FCT 2021. Lecture Notes in Computer Science(), vol 12867. Springer, Cham. https://doi.org/10.1007/978-3-030-86593-1_27
Download citation
DOI: https://doi.org/10.1007/978-3-030-86593-1_27
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-86592-4
Online ISBN: 978-3-030-86593-1
eBook Packages: Computer ScienceComputer Science (R0)