arXiv preprint ·
Finding full immersions is fixed-parameter tractable in labeled tour graphs
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
A Complete Characterization of $q$-Ary $2$-Designs in Doubly-Extended Reed-Solomon Codes
A Universal Threshold Theory for Local Properties of Random Linear Codes
How Unbalanced Must a Latin Rectangle Be?
First-Order Model Checking on Monadically Dependent Graph Classes
A Polynomial Erdős-Pósa bound for Eulerian digraphs
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.