Блог пользователя b_like_karthik

Автор b_like_karthik, история, 4 месяца назад, По-английски

Find the minimum number of nodes to be removed to convert a graph into a tree.

number of nodes < 1e5

number of edges < 2e5

Any help, please...

  • Проголосовать: нравится
  • +11
  • Проголосовать: не нравится

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by b_like_karthik (previous revision, new revision, compare).

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

This problem is NP complete.

Proof by reduction from Independent set

Therefore I doubt that an algorithm exists that can solve this problem for such large graphs in reasonable time.