A finer view of the parameterized landscape of labeled graph contractions

Abstract

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 (2025) [42] initiated the parameterized complexity study of this problem, showing it to be 𝖶⁡[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 𝗍𝗐 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𝒪⁡(𝗍𝗐2) ⋅|𝑉⁡(𝐺)|𝒪⁡(1). We also prove that unless the Exponential Time Hypothesis (ETH) fails, it does not admit an algorithm running in time 2𝑜⁡(𝗍𝗐2) ⋅|𝑉⁡(𝐺)|𝒪⁡(1). This result adds Labeled Contractibility to a small list of problems for which a 2Θ⁡(𝗍𝗐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 (𝑘+ 𝛿⁡(𝐺)), where 𝛿⁡(𝐺) 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 (2025) [42]. We additionally provide an improved FPT algorithm running in time (𝛿⁡(𝐻)+1)𝑘 ⋅|𝑉⁡(𝐺)|𝒪⁡(1). Finally, we analyze a brute-force algorithm for Labeled Contractibility with running time |𝑉⁡(𝐻)|𝒪⁡(|𝑉⁡(𝐺)|), and show that this running time is optimal under ETH.