A finer view of the parameterized landscape of labeled graph contractions
Yashaswini Mathur, Prafullkumar Tale · Journal of Computer and System Sciences · 2026
We study the Labeled Contractibility 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 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 treewidth tw of G , via an application of Courcelle's theorem with a non-elementary dependence on the parameter. In this work, we present a constructive fixed-parameter algorithm for Labeled Contractibility with running time 2 O ( tw 2 ) ⋅ | V ( G ) | O ( 1 ) . We also prove that unless the Exponential Time Hypothesis ( ETH ) fails, it does not admit an algorithm running in time 2 o ( tw 2 ) ⋅ | V ( G ) | O ( 1 ) . This result adds Labeled Contractibility to a small list of problems for which a 2 Θ ( tw 2 ) dependence is optimal under ETH . We further strengthen existing hardness results by showing that the problem remains NP -hard even when both input graphs have bounded maximum degree. We also investigate parameterizations by ( k + δ ( G ) ) , where δ ( G ) denotes the degeneracy of G , and rule out the existence of subexponential-time algorithms. This answers a question on subexponential fixed-parameter tractability raised by Lafond and Marchand [WADS 2025]. We additionally provide an improved FPT algorithm running in time ( δ ( H ) + 1 ) k ⋅ | V ( G ) | O ( 1 ) . Finally, we analyze a brute-force algorithm for Labeled Contractibility with running time | V ( H ) | O ( | V ( G ) | ) , and show that this running time is optimal under ETH .