{"ID":2859451,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.06102","arxiv_id":"2510.06102","title":"A Finer View of the Parameterized Landscape of Labeled Graph Contractions","abstract":"We study the \\textsc{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 \\textsc{Labeled Contractibility} with running time \\(2^{\\mathcal{O}(\\tw^2)} \\cdot |V(G)|^{\\mathcal{O}(1)}\\). We also prove that unless the Exponential Time Hypothesis (Ð) fails, it does not admit an algorithm running in time \\(2^{o(\\tw^2)} \\cdot |V(G)|^{\\mathcal{O}(1)}\\). This result adds \\textsc{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 \\NP-complete 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 \\textsc{Labeled Contractibility} with running time \\(|V(H)|^{\\mathcal{O}(|V(G)|)}\\), and show that this running time is optimal under Ð.","short_abstract":"We study the \\textsc{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, s...","url_abs":"https://arxiv.org/abs/2510.06102","url_pdf":"https://arxiv.org/pdf/2510.06102v2","authors":"[\"Yashaswini Mathur\",\"Prafullkumar Tale\"]","published":"2025-10-07T16:33:44Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.DM\"]","methods":"[]","has_code":false}