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 agree to our terms of service and acknowledge you have read our privacy policy.