Header menu link for other important links
X
The Complexity of Contracting Bipartite Graphs into Small Cycles
, Roohani Sharma, Prafullkumar Tale
Published in Springer Science and Business Media Deutschland GmbH
2022
Volume: 13453 LNCS
   
Pages: 356 – 369 - 369
Abstract
For a positive integer $$\ell \ge 3$$, the $$C:\ell $$ -Contractibility problem takes as input an undirected simple graph G and determines whether G can be transformed into a graph isomorphic to $$C:\ell $$ (the induced cycle on $$\ell $$ vertices) using only edge contractions. Brouwer and Veldman [JGT 1987] showed that $$C:4$$ -Contractibility is $$\textsf{NP}$$ -complete in general graphs. It is easy to verify that that $$C:3$$ -Contractibility is polynomial-time solvable. Dabrowski and Paulusma [IPL 2017] showed that $$C:{\ell }$$ -Contractibility is $$\textsf{NP}$$ -complete on bipartite graphs for $$\ell = 6$$ and posed as open problems the status of $$C:{\ell }$$ -Contractibility when $$\ell $$ is 4 or 5. In this paper, we show that both $$C:5$$ -Contractibility and $$C:4$$ -Contractibility are $$\textsf{NP}$$ -complete on bipartite graphs. © 2022, Springer Nature Switzerland AG.
About the journal
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherSpringer Science and Business Media Deutschland GmbH
ISSN03029743
Open AccessNo