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.