Temporal matching in trees

Abstract

We study maximum matching problems in temporal graphs whose underlying graph is a tree. We consider two temporal models. In a $\hat{I}”$-matching, selected time edges sharing an endpoint must have time ticks differing by at least $\hat{I}”$. In a ${\hat{I}}^3$-matching, the selected objects are blocks of ${\hat{I}}^3$ consecutive appearances of the same underlying edge. We also consider the related ordered static problem of $d$-distance matchings. We show that maximum $\hat{I}”$-matching remains NP-hard on temporal trees for every $\hat{I}”\ge 2$, even in the sparse case where each edge appears at most twice. Using a reduction between the temporal models, we obtain the analogous result for maximum ${\hat{I}}^3$-matching on temporal trees, even when each edge admits at most two ${\hat{I}}^3$-edges. We also show, via a reduction from $d$-distance matching, that maximum ${\hat{I}}^3$-matching is APX-hard even when the underlying graph is bipartite. Complementing these hardness results, we identify several tractable cases. We prove that maximum $\hat{I}”$-matching is polynomial-time solvable on temporal trees in which every edge appears exactly once, and that maximum ${\hat{I}}^3$-matching is polynomial-time solvable when each edge admits at most one ${\hat{I}}^3$-edge. We also give dynamic-programming algorithms under bounded local-use and local-sparsity assumptions, and derive polynomial-time solvability of maximum $d$-distance matching when the input bipartite graph is a tree. Finally, we prove that both maximum $\hat{I}”$-matching and maximum ${\hat{I}}^3$-matching admit polynomial-time approximation schemes on temporal trees.