A temporal graph is a sequence of graphs (called layers) over the same vertex set---describing a graph topology which is subject to discrete changes over time. A \Delta-temporal matching M is a set of time edges (e,t) (an edge e paired up with a point in time t) such that for all distinct time edges (e,t),(e',t') \in M we have that e and e' do not share an endpoint, or the time-labels t and t' are at least \Delta time units apart. Mertzios et al. [STACS '20] provided a 2^{O(\Delta\nu)}\cdot |{\mathcal G}|^{O(1)}-time algorithm to compute the maximum size of  \Delta-temporal matching in a temporal graph \mathcal G, where |\mathcal G| denotes the size of \mathcal G, and \nu is the \Delta-vertex cover number of \mathcal G. The \Delta-vertex cover number is the minimum number of vertices which are needed to hit (or cover ) all edges in any \Delta consecutive layers of the temporal graph  . We show an improved algorithm to compute a \Delta-temporal matching of maximum size with a running time of \Delta^{O(\nu)}\cdot |\mathcal G| and hence provide an exponential speedup in terms of \Delta.
A temporal graph is a sequence of graphs (called layers) over the same vertex set -- describing a graph topology which is subject to discrete changes over time. A \Delta-temporal matching M is a set of time edges (e,t) (an edge e paired up with a point in time t) such that for all distinct time edges (e,t),(e',t') \in M we have that e and e' do not share an endpoint, or the time-labels t and t' are at least \Delta time units apart. Mertzios et al. [STACS '20] provided a 2^{O(\Delta\nu)}\cdot |{\mathcal G}|^{O(1)}-time algorithm to compute the maximum size of a \Delta-temporal matching in a temporal graph \mathcal G, where |\mathcal G| denotes the size of \mathcal G, and \nu is the \Delta-vertex cover number of \mathcal G. The \Delta-vertex cover number is the minimum number \nu such that the classical vertex cover number of the union of any \Delta consecutive layers of the temporal graph is upper-bounded by \nu . We show an improved algorithm to compute a \Delta-temporal matching of maximum size with a running time of \Delta^{O(\nu)}\cdot |\mathcal G| and hence provide an exponential speedup in terms of \Delta.
R
set---describing
set -- describing
A
a
R
of vertices which are needed to hit (or cover ) all edges in
\nu such that the classical vertex cover number of the union of
A
is upper-bounded by \nu