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 [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 tree-width 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 Labeled Contractibility with running time 2 O(tw2) · |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(tw2) · |V (G)| O(1). This result adds Labeled Contractibility 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 NPcomplete 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 question raised in Lafond and Marchand [WADS 2025]. We additionally provide an improved FPT algorithm with better dependence on (k + δ(G)) than previously known. 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.