The Complexity of Contracting Bipartite Graphs into Small Cycles

Krithika, R.; Sharma, Roohani; Tale, Prafullkumar

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

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.