The Complexity of Contracting Bipartite Graphs into Small Cycles
share
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 C_4-Contractibility is NP-complete in general graphs. It is easy to verify that C_3-Contractibility is polynomial-time solvable. Dabrowski and Paulusma [IPL 2017] showed that C_ℓ-Contractibility is -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 C_5-Contractibility and C_4-Contractibility are NP-complete on bipartite graphs.
READ FULL TEXT