Sookhail's blog

Need some hint...
By Sookhail, history, 4 years ago, In English

Hi, can you give me a hint about this problem ??

Given a connected simple graph with n vertices and m edges, find the minimum number of operations required to remove the graph completely

in an operation you can do one of the following things:

1- remove a vertex from the graph

2- remove 2 vertices connecting to an edge

$$$n, m < 10^6$$$
  • Vote: I like it
  • +7
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it +26 Vote: I do not like it

It is always optimal to perform operations of type $$$2$$$ as many times as possible. So the answer to the problem is $$$= n - $$$ maximum matching.

For a general graph, you can solve it in $$$O(n^3)$$$ and in case of a bipartite graph, you can do the same in $$$O(n \sqrt{n})$$$.

→ Reply