cs.DS cs.DM
A Faster Parameterized Algorithm for Temporal Matching. 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 .