b_like_karthik's blog

Convert a graph to a tree
By b_like_karthik, history, 4 months ago, In English

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...

  • Vote: I like it
  • +11
  • Vote: I do not like it

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply