Monday, November 23, 2026 3:00 pm
-
4:00 pm
EST (GMT -05:00)
| Speaker: | Hadas Barabash |
| Affiliation: | Georgia Tech |
| Room: | MC 6029 |
Abstract: We give an $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 \emph{labeled tour graph} is a connected $4$-regular graph whose edges are labeled by binary vectors of fixed length. To obtain a \emph{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 \emph{vertex-minors}, whose study is motivated by applications in quantum networking.