Georgia Institute of Technology College of Sciences

We give an $\mathcal{O}_{\mathcal{H}}(n^5)$-time algorithm to test whether an $n$-vertex labeled tour graph has a full immersion isomorphic to a labeled tour graph $\mathcal{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 $\mathcal{H}$. Our results have implications for vertex-minors, whose study is motivated by applications in quantum networking.