English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Paper

The Complexity of Contracting Bipartite Graphs into Small Cycles

MPS-Authors
/persons/resource/persons255161

Sharma,  Roohani
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

arXiv:2206.07358.pdf
(Preprint), 458KB

Supplementary Material (public)
There is no public supplementary material available
Citation

Krithika, R., Sharma, R., & Tale, P. (2022). The Complexity of Contracting Bipartite Graphs into Small Cycles. Retrieved from https://arxiv.org/abs/2206.07358.


Cite as: https://hdl.handle.net/21.11116/0000-000C-1DCB-0
Abstract
For a positive integer $\ell \geq 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 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_{\ell}$-Contractibility is \NP-complete\ on
bipartite graphs for $\ell = 6$ and posed as open problems the status of the
problem when $\ell$ is 4 or 5. In this paper, we show that both
$C_5$-Contractibility and $C_4$-Contractibility are NP-complete on bipartite
graphs.