The Complexity of Contracting Bipartite Graphs into Small Cycles

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.