The Complexity of Contracting Bipartite Graphs into Small Cycles

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

アイテム詳細

登録内容を編集ファイル形式で保存

一時保存へ追加

タグ情報を表示リリース履歴を表示詳細要約

公開

成果報告書

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

There are no locators available

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

フルテキスト (公開)

arXiv:2206.07358.pdf
(プレプリント), 458KB

付随資料 (公開)

There is no public supplementary material available

引用

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

引用: https://hdl.handle.net/21.11116/0000-000C-1DCB-0

要旨

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.