SheikhSoheil's blog

By SheikhSoheil, history, 6 weeks 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

»
6 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

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

»
6 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

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

»
6 weeks 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})$$$.