5
$\begingroup$

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)?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.