6
$\begingroup$

I am teaching a complexity course, and I want to give some examples of similar looking problems such that one is in P, and the other is NP complete.

This made me think of the following problem: does a given graph contain a spanning tree with a given degree sequence? This is obviously easy for the sequence $n-1,1,...,1$ and hard for $2,...,2,1,1$. Is there a general answer?

$\endgroup$
5
$\begingroup$

Lemke has shown that it is NP-hard to decide whether a cubic graph on $n=2k$ vertices has a spanning tree in which $k+1$ vertices have degree $1$ and $k-1$ vertices have degree $3$.

P. Lemke:
"The maximum-leaf spanning tree problem in cubic graphs is NP-complete."
IMA publication no. 428, University of Minnesota, Mineapolis, 1988.
https://www.ima.umn.edu/Maximum-Leaf-Spanning-Tree-Problem-Cubic-Graphs-NP-Complete

  • Lemke's result implies the NP-completeness of deciding whether there exists a spanning tree without vertices of degree $2$.
  • A slight modification of Lemke's reduction shows that the following problem is NP-complete for every fixed integer $p\ge4$: Decide whether there exists a spanning tree, in which every non-leaf vertex has degree at least $p$.
  • The same modification shows that the following problem is NP-complete for every fixed integer $p\ge4$: Decide whether there exists a spanning tree, in which every vertex degree lies in $\{1,p\}$.
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.