A Finer View of the Parameterized Landscape of Labeled Graph Contractions
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917265585209344 |
|---|---|
| author | Mathur, Yashaswini Tale, Prafullkumar |
| author_facet | Mathur, Yashaswini Tale, Prafullkumar |
| contents | 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 Ð. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_06102 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Finer View of the Parameterized Landscape of Labeled Graph Contractions Mathur, Yashaswini Tale, Prafullkumar Data Structures and Algorithms Discrete Mathematics 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 Ð. |
| title | A Finer View of the Parameterized Landscape of Labeled Graph Contractions |
| topic | Data Structures and Algorithms Discrete Mathematics |
| url | https://arxiv.org/abs/2510.06102 |