2022/03/14 by Emmanuel Arrighi, Arrighi, Emmanuel, Niels Grüttemeier +7 · 1 citation
Computer Science · #05C83 #05C85 #68Q17 #68Q27 #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Opportunistic and Delay-Tolerant Networks
paper · pdf · doi:10.48550/arxiv.2203.07401
openalex publication_date 2022/03/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the computational complexity of determining structural properties of edge periodic temporal graphs (EPGs). EPGs are time-varying graphs that compactly represent periodic behavior of components of a dynamic network, for example, train schedules on a rail network. In EPGs, for each edge e of the graph, a binary string se determines in which time steps the edge is present, namely e is present in time step t if and only if se contains a 1 at position t \mod |se|. Due to this periodicity, EPGs serve as very compact representations of complex periodic systems and can even be exponentially smaller than classic temporal graphs representing one period of the same system, as the latter contain the whole sequence of graphs explicitly. In this paper, we study the computational complexity of fundamental questions of the new concept of EPGs such as what is the shortest traversal time between two vertices; is there a time step in which the graph (1) is minor-free; (2) contains a minor; (3) is subgraph-free; (4) contains a subgraph; with respect to a given minor or subgraph. We give a detailed parameterized analysis for multiple combinations of parameters for the problems stated above including several parameterized algorithms.