Finding full immersions is fixed-parameter tractable in labeled tour graphs

Source: arxiv.org/abs/2611.06776

Hadas Barabash, Jim Geelen, Rose McCarty, Caleb McFarland, Paul Wollan

arXivarxiv/2611.06776Nov 4, 2026cs.DSscore 0

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…

JSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2611.06776
curl -X POST /api/v1/records/arxiv/2611.06776/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.06776/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'