{"id":"arxiv/2611.06776","url":"https://arxiv.org/abs/2611.06776","tags":["cs.DS","math.CO"],"score":0,"title":"Finding full immersions is fixed-parameter tractable in labeled tour graphs","domain":"cs.DS","source":"arxiv","authors":["Hadas Barabash","Jim Geelen","Rose McCarty","Caleb McFarland","Paul Wollan"],"reviews":0,"subject":"cs.DS","summary":"We give an $O_H(n^5)$-time algorithm to test whether an $n$-vertex labeled tour graph has a full immersion isomorphic to a labeled tour graph $H$. A labeled tour graph is a connected $4$-regular graph whose edges are labeled by binary vectors of fixed length. To obtain a full immersion, a vertex may be removed only by pairing up its four incident edges and \"splitting off\" both pairs, summing the labels within each pair. Even for one-bit labels, no polynomial-time algorithm was previously known for arbitrary fixed $H$. Our main tool is of independent interest: we give an algorithmic min-max…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-11-04","reactions":{}}