Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official. ×

Is the steiner tree on unweighted graph also NP-hard?

Правка en1, от AnotherRound, 2017-08-10 10:32:26

The steiner tree problem can be formulated this way:

We have a weighted connected graph (V, E) and a subset of its vertices(let's say it is Q). We have to find a subtree of this graph that has minimal weight and contains Q. Now, this is a "famous" NP problem, but I thought what if the graph was unweighted, or alternatively all edges have the same weight? Is this problem easier or has the same complexity?

Теги graph


  Rev. Язык Кто Когда Δ Комментарий
en1 Английский AnotherRound 2017-08-10 10:32:26 463 Initial revision (published)