A Dichotomy for Terminal Cyclability

Abstract

Given an undirected graph $G$ and a set $R\subseteq V(G)$ of terminals, Terminal Cyclability asks whether $G$ contains a simple cycle visiting every vertex of $R$. We establish a complexity dichotomy for this problem on red-minor-closed classes of annotated graphs. In particular, we show that Terminal Cyclability is polynomial-time solvable on every such class excluding any annotated planar graph. The problem is NP-complete whenever the class contains all annotated planar graphs. More precisely, we give an $|G{|}^{2^{\mathbf{poly}(b)}}$-time algorithm, where $b$ is the bidimensionality of $(G,R)$. Our main technical contribution is the introduction of a weak irrelevant vertex rule. Rather than removing irrelevant vertices until the treewidth becomes constant, we only remove irrelevant vertices until the treewidth is logarithmic in the graph size. Such a weakening is necessary as a parameter-only treewidth threshold for an irrelevant vertex rule in this setting is known to be impossible to realise. Combined with a single-exponential algorithm for Terminal Cyclability parameterized by treewidth, this yields the polynomial-time algorithm for our dichotomy.