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

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.