Making the interval membership width of temporal graphs connected and bidirectional

Temporal graphs are graphs that evolve over time. Many problems which are polynomial-time solvable in standard graphs become NP-hard when appropriately defined in the realm of temporal graphs.This suggested the definition of several parameters for temporal graphs and to prove the fixed-parameter tractability of several problems with respect to these parameters. In this paper, we introduce a hierarchy of parameters based on the previously defined interval membership width and the temporal evolution of the connected components of the underlying static graph. We show that the Eulerian trail problem and the temporal 2-coloring problem are both fixed-parameter tractable with respect to any parameter in the hierarchy. We also introduce a vertex-variant of the parameters and show that the firefighter problem, known to be FPT with respect to the vertex-variant of the interval membership width, is also FPT with respect to one of the parameters in the second level of the hierarchy.