{"id":"arxiv/2606.06439","url":"https://arxiv.org/abs/2606.06439","tags":["cs.DS","cs.DM","math.CO"],"score":0,"title":"Temporal matching in trees","domain":"cs.DS","source":"arxiv","authors":["Márk Hunor Juhász","Péter Madarasi"],"reviews":0,"subject":"cs.DS","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-06-04","reactions":{}}