A Complete Complexity Dichotomy for Deciding Cluster In-Betweenness

Unsupervised learning reads every object through a binary lens: inlier or outlier. Recent work adds a third primitive, the *in-between instance* (IBI): an object atypical for every cluster yet simultaneously compatible with several of them, and whose interest lies in *which* traits it inherits from *which* neighbouring group. Existing formulations answer this with a proximity predicate and a scalar score. We instead pose in-betweenness as an exact reconstruction question: can a bounded number of *actual* cluster members be selected so that, coordinate by coordinate, they reproduce a target? The selection is then itself the attribution. We formalize this as $\mathtt{Inbetween}\text{-}\mathtt{Decision}$, a group-budgeted covering problem over symbolic data, and settle its complexity along five structural parameters: alphabet size $\sigma$, dimensionality $\delta$, number of clusters $\nu$, cluster size $\xi$, target size $\tau$. We obtain a complete dichotomy over all $2^5=32$ bounding regimes: solvable in polynomial time exactly when $\{\sigma ,\delta \}$, $\{\nu ,\xi \}$ or $\{\delta ,\tau \}$ is bounded, each witnessed by a fixed-parameter algorithm and $\mathsf{NP}$-complete otherwise. In-between detection is thus feasible precisely when one of three structural budgets is paid.