A Finer View of the Parameterized Landscape of Labeled Graph Contractions

We study the $\text{textsc}LabeledContractibility$ problem, where the input consists of two vertex-labeled graphs $G$ and $H$, and the goal is to determine whether $H$ can be obtained from $G$ via a sequence of edge contractions. Lafond and Marchand~[WADS 2025] initiated the parameterized complexity study of this problem, showing it to be $\text{W}[1]$-hard when parameterized by the number $k$ of allowed contractions. They also proved that the problem is fixed-parameter tractable when parameterized by the tree-width $\text{tw}$ of $G$, via an application of Courcelle’s theorem resulting in a non-constructive algorithm. In this work, we present a constructive fixed-parameter algorithm for $\text{textsc}LabeledContractibility$ with running time $2^{\mathcal{O}({\text{tw}}^2)}\cdot \mathrm{\mid }V(G){\mathrm{\mid }}^{\mathcal{O}(1)}$. We also prove that unless the Exponential Time Hypothesis (Ð) fails, it does not admit an algorithm running in time $2^{o({\text{tw}}^2)}\cdot \mathrm{\mid }V(G){\mathrm{\mid }}^{\mathcal{O}(1)}$. This result adds $\text{textsc}LabeledContractibility$ to a small list of problems that admit such a lower bound and matching algorithm. We further strengthen existing hardness results by showing that the problem remains \NP-complete even when both input graphs have bounded maximum degree. We also investigate parameterizations by $(k+\delta (G))$ where $\delta (G)$ denotes the degeneracy of $G$, and rule out the existence of subexponential-time algorithms. This answers question raised in Lafond and Marchand~[WADS 2025]. We additionally provide an improved \FPT\ algorithm with better dependence on $(k+\delta (G))$ than previously known. Finally, we analyze a brute-force algorithm for $\text{textsc}LabeledContractibility$ with running time $\mathrm{\mid }V(H){\mathrm{\mid }}^{\mathcal{O}(\mathrm{\mid }V(G)\mathrm{\mid })}$, and show that this running time is optimal under Ð.