Skip to main content
Computer Science

Return to Question

Commonmark migration
Source Link
Community Bot
Community Bot
  • 1

I am trying to solve the following exercise:

Let $G = (V,E)$ be a graph. Show that the following two problems are NP-hard:

 
  1. $G$ has a spanning tree where every node has at most $k$ neighbors, and $k$ is part of the input.

    $G$ has a spanning tree where every node has at most $k$ neighbors, and $k$ is part of the input.

  2. $G$ has a spanning tree where every node has at most 5 neighbors.

  1. $G$ has a spanning tree where every node has at most 5 neighbors.

It's written that 1 is supposed to be a hint for 2. You can of course choose to ignore it and solve 2 directly.

I tried to reduce $k$-MST to Steiner tree, but I don't know if this is a right way. I read that can use a Hamiltonian circuit, but I don't understand how. Can anybody help me?

I am trying to solve the following exercise:

Let $G = (V,E)$ be a graph. Show that the following two problems are NP-hard:

 
  1. $G$ has a spanning tree where every node has at most $k$ neighbors, and $k$ is part of the input.
  1. $G$ has a spanning tree where every node has at most 5 neighbors.

It's written that 1 is supposed to be a hint for 2. You can of course choose to ignore it and solve 2 directly.

I tried to reduce $k$-MST to Steiner tree, but I don't know if this is a right way. I read that can use a Hamiltonian circuit, but I don't understand how. Can anybody help me?

I am trying to solve the following exercise:

Let $G = (V,E)$ be a graph. Show that the following two problems are NP-hard:

  1. $G$ has a spanning tree where every node has at most $k$ neighbors, and $k$ is part of the input.

  2. $G$ has a spanning tree where every node has at most 5 neighbors.

It's written that 1 is supposed to be a hint for 2. You can of course choose to ignore it and solve 2 directly.

I tried to reduce $k$-MST to Steiner tree, but I don't know if this is a right way. I read that can use a Hamiltonian circuit, but I don't understand how. Can anybody help me?

Bumped by Community user
Bumped by Community user
Bumped by Community user
added 61 characters in body; edited tags; edited title
Source Link
Yuval Filmus
Yuval Filmus
  • 279.1k
  • 27
  • 316
  • 512

Show Np NP-hard problemhardness of existence of spanning tree with given maximal degree

i found this ex

Let G = (V;E) be a graph. Show that the follwing two problems are NP-hard. 1. G has a spanning tree where every node has at most k neighbors and k is part ofI am trying to solve the input. 2. G has a spanning tree where every node has at most 5 neighbors.following exercise:

Let $G = (V,E)$ be a graph. Show that the following two problems are NP-hard:

  1. $G$ has a spanning tree where every node has at most $k$ neighbors, and $k$ is part of the input.
  1. $G$ has a spanning tree where every node has at most 5 neighbors.

It's wrote thanwritten that 1 is supposed to be a hint for 2. You can of course choose to ignore it and solve 2 directly.

I tried to reduce K$k$-MST to Steiner tree, but iI don't know if this is a right way. I read that can use ana Hamiltonian circuit, but iI don't understand how to do. Someone canCan anybody help me?

Show Np-hard problem

i found this ex

Let G = (V;E) be a graph. Show that the follwing two problems are NP-hard. 1. G has a spanning tree where every node has at most k neighbors and k is part of the input. 2. G has a spanning tree where every node has at most 5 neighbors.

It's wrote than 1 is supposed to be a hint. You can of course choose to ignore it and solve 2 directly.

I tried to reduce K-MST to Steiner tree, but i don't know if is a right way. I read that can use an Hamiltonian circuit, but i don't understand how to do. Someone can help me?

NP-hardness of existence of spanning tree with given maximal degree

I am trying to solve the following exercise:

Let $G = (V,E)$ be a graph. Show that the following two problems are NP-hard:

  1. $G$ has a spanning tree where every node has at most $k$ neighbors, and $k$ is part of the input.
  1. $G$ has a spanning tree where every node has at most 5 neighbors.

It's written that 1 is supposed to be a hint for 2. You can of course choose to ignore it and solve 2 directly.

I tried to reduce $k$-MST to Steiner tree, but I don't know if this is a right way. I read that can use a Hamiltonian circuit, but I don't understand how. Can anybody help me?

Source Link
theantomc
theantomc
  • 262
  • 1
  • 12

Show Np-hard problem

i found this ex

Let G = (V;E) be a graph. Show that the follwing two problems are NP-hard. 1. G has a spanning tree where every node has at most k neighbors and k is part of the input. 2. G has a spanning tree where every node has at most 5 neighbors.

It's wrote than 1 is supposed to be a hint. You can of course choose to ignore it and solve 2 directly.

I tried to reduce K-MST to Steiner tree, but i don't know if is a right way. I read that can use an Hamiltonian circuit, but i don't understand how to do. Someone can help me?