Please use this identifier to cite or link to this item:
http://dr.iiserpune.ac.in:8080/xmlui/handle/123456789/10602| Title: | The Complexity of Contracting Bipartite Graphs into Small Cycles |
| Authors: | Krithika, R. Sharma, Roohani TALE, PRAFULLKUMAR Dept. of Mathematics |
| Keywords: | Computational Complexity 2025-DEC-WEEK2 TOC-DEC-2025 2025 |
| Issue Date: | Dec-2025 |
| Publisher: | Episciences |
| Citation: | Discrete Mathematics & Theoretical Computer Science, 27(3). |
| Abstract: | For a positive integer ℓ≥3, the Cℓ-Contractibility problem takes as input an undirected simple graph G and determines whether G can be transformed into a graph isomorphic to Cℓ (the induced cycle on ℓ vertices) using only edge contractions. Brouwer and Veldman [JGT 1987] showed that C4-Contractibility is NP-complete in general graphs. It is easy to verify that C3-Contractibility is polynomial-time solvable. Dabrowski and Paulusma [IPL 2017] showed that Cℓ-Contractibility is \NP-complete\ on bipartite graphs for ℓ=6 and posed as open problems the status of the problem when ℓ is 4 or 5. In this paper, we show that both C5-Contractibility and C4-Contractibility are NP-complete on bipartite graphs. |
| URI: | https://doi.org/10.46298/dmtcs.14658 http://dr.iiserpune.ac.in:8080/xmlui/handle/123456789/10602 |
| ISSN: | 1365-8050 |
| Appears in Collections: | JOURNAL ARTICLES |
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.