Finding full immersions is fixed-parameter tractable in labeled tour graphs
Abstract
We give an OH(n5)-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 theorem that, in particular, characterizes the maximum number of odd-length circuits in a rooted circuit decomposition of an Eulerian graph. Our results have implications for vertex-minors, whose study is motivated by applications in quantum networking, connections with graph minor theory, and the goal of developing an irrelevant vertex technique for dense graphs. For vertex-minors, circle graphs play the same role as planar graphs do for graph minors. As a corollary of our main theorem, we obtain a fixed-parameter tractable algorithm for apex-vertex-minor testing in k-apex circle graphs. We also prove an irrelevant vertex theorem for such graphs of large rank-width. More broadly, our results are essential to forthcoming work of three of the authors proving a structure theorem for graphs with a forbidden vertex-minor. There, our min-max theorem plays the role of both the algorithmic A-paths and Two Paths Theorems.
Related
- Full immersions in Eulerian group-labeled graphs
- Strong complete immersions in graphs with independence number two
- Direct Message Approximation (DMA): A Consistency-Based Framework for Tractable Approximate Inference on Factor Graphs
- Finding Icebergs in Language-Model Workflow: Diagnosing Latent Structural Fragility with Stochastic Semantic Evidence Graphs
- Coloring Monomial Cayley Graphs: The One-Parameter Case
BibTeX
@misc{barabash2026finding,
title = {{Finding full immersions is fixed-parameter tractable in labeled tour graphs}},
author = {Hadas Barabash and Jim Geelen and Rose McCarty and Caleb McFarland and Paul Wollan},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.06776},
eprint = {2611.06776},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.06776},
}
RIS
TY - UNPB
TI - Finding full immersions is fixed-parameter tractable in labeled tour graphs
AU - Hadas Barabash
AU - Jim Geelen
AU - Rose McCarty
AU - Caleb McFarland
AU - Paul Wollan
PY - 2026
DA - 2026/11/04
PB - arXiv
DO - 10.48550/arxiv.2611.06776
UR - https://arxiv.org/abs/2611.06776
AB - 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 theorem that, in particular, characterizes the maximum number of odd-length circuits in a rooted circuit decomposition of an Eulerian graph. Our results have implications for vertex-minors, whose study is motivated by applications in quantum networking, connections with graph minor theory, and the goal of developing an irrelevant vertex technique for dense graphs. For vertex-minors, circle graphs play the same role as planar graphs do for graph minors. As a corollary of our main theorem, we obtain a fixed-parameter tractable algorithm for apex-vertex-minor testing in k-apex circle graphs. We also prove an irrelevant vertex theorem for such graphs of large rank-width. More broadly, our results are essential to forthcoming work of three of the authors proving a structure theorem for graphs with a forbidden vertex-minor. There, our min-max theorem plays the role of both the algorithmic A-paths and Two Paths Theorems.
ER -