{"ID":3083570,"CreatedAt":"2026-06-05T06:46:15.197025399Z","UpdatedAt":"2026-06-07T05:16:48.22291569Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2606.06439","arxiv_id":"2606.06439","title":"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 $Δ$-matching, selected time edges sharing an endpoint must have time ticks differing by at least $Δ$. In a $γ$-matching, the selected objects are blocks of $γ$ consecutive appearances of the same underlying edge. We also consider the related ordered static problem of $d$-distance matchings. We show that maximum $Δ$-matching remains NP-hard on temporal trees for every $Δ\\geq 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 $γ$-matching on temporal trees, even when each edge admits at most two $γ$-edges. We also show, via a reduction from $d$-distance matching, that maximum $γ$-matching is APX-hard even when the underlying graph is bipartite. Complementing these hardness results, we identify several tractable cases. We prove that maximum $Δ$-matching is polynomial-time solvable on temporal trees in which every edge appears exactly once, and that maximum $γ$-matching is polynomial-time solvable when each edge admits at most one $γ$-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 $Δ$-matching and maximum $γ$-matching admit polynomial-time approximation schemes on temporal trees.","short_abstract":"We study maximum matching problems in temporal graphs whose underlying graph is a tree. We consider two temporal models. In a $Δ$-matching, selected time edges sharing an endpoint must have time ticks differing by at least $Δ$. In a $γ$-matching, the selected objects are blocks of $γ$ consecutive appearances of the sam...","url_abs":"https://arxiv.org/abs/2606.06439","url_pdf":"https://arxiv.org/pdf/2606.06439v1","authors":"[\"Márk Hunor Juhász\",\"Péter Madarasi\"]","published":"2026-06-04T17:41:21Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.DM\",\"math.CO\"]","methods":"[]","has_code":false}