Efficiently finding structured subgraphs in labeled tour graphs
Finding full immersions is fixed-parameter tractable in labeled tour graphs
Data Structures and Algorithms
Summary
Finding certain patterns inside complex networks is often difficult and slow. This paper focuses on special graphs called labeled tour graphs and presents a new algorithm that can quickly check for a specific kind of subgraph, called a full immersion, in these graphs. The authors also develop a broader theoretical tool that helps understand how certain circuits in graphs behave. These results link to problems in quantum networking and improve understanding of complex graph structures.
What this means in practice
- •For quantum network engineers: Identify subgraph patterns important for managing quantum network states represented by vertex-minors in circle graphs.
- •For network algorithm developers: Design algorithms that test for complex vertex-minors in dense graphs, supporting improved network routing or optimization.
A theory result. No direct application yet.
Authors
Hadas Barabash, Jim Geelen, Rose McCarty, Caleb McFarland, Paul Wollan
Abstract
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.