Graphs and Matroids | Hadas Barabash, Finding full immersions is fixed-parameter tractable in labeled tour graphs

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.