This paper defines the problem $\mathrm{B{\scriptsize OUNDED} \ D{\scriptsize EGREE}\ C{\scriptsize ONTRACTION}}$ as follows:

Instance: A graph $G$ and two integers $d$ and $k$.

Question: Is there a graph $H\in \mathcal{H}_{\le d}$, where $\mathcal{H}_{\le d}$ denotes the class of graphs that have maximum degree at most $d$, such that $G$ is $k$-contractible to $H$?

Theorem 3 of that work states that $\mathrm{B{\scriptsize OUNDED} \ D{\scriptsize EGREE}\ C{\scriptsize ONTRACTION}}$ is NP-complete for any fixed $d\ge2$.

I am interested in the similar problem, which one might call $\mathrm{B{\scriptsize OUNDED}\ D{\scriptsize EGREE}\ F{\scriptsize ULL}\ C{\scriptsize ONTRACTION}}$:

Instance: A graph $G$ and an integer $d$.

Question: Can $G$ be fully contracted (reduced to a single vertex) ensuring that $H\in \mathcal{H}_{\le d}$, for every intermediate graph $H$ generated in the contraction sequence?

Has this problem ever been studied? Is it NP-complete in general for connected graphs? Is it easier for any well-studied classes of graphs (for which the decision is not immediately obvious, e.g., cycles)?


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.