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

# | User | Rating |
---|---|---|

1 | tourist | 3947 |

2 | ecnerwala | 3654 |

3 | jiangly | 3627 |

4 | jqdai0815 | 3620 |

5 | orzdevinwang | 3612 |

6 | Benq | 3586 |

7 | Radewoosh | 3582 |

8 | Geothermal | 3569 |

8 | cnnfls_csy | 3569 |

10 | ksun48 | 3474 |

# | User | Contrib. |
---|---|---|

1 | awoo | 163 |

2 | maomao90 | 160 |

3 | adamant | 156 |

4 | atcoder_official | 154 |

5 | maroonrk | 152 |

6 | -is-this-fft- | 148 |

6 | SecondThread | 148 |

8 | Petr | 147 |

9 | nor | 145 |

10 | cry | 144 |

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

↑

↓

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/03/2024 09:54:36 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Auto comment: topic has been updated by b_like_karthik (previous revision, new revision, compare).This problem is NP complete.

Proof by reduction from Independent setI quote from the paper "Maximum induced trees in graphs" by Paul Erdös, Michael Saks and Vera T Sós:

"The problem “given a graph H and integer k does H have an independent set of size k?” is a well-known NP-complete problem. Given H and k, let n be the number of vertices of H and let G be the graph obtained by adjoining a path on n vertices to H, one endpoint of which is joined by an edge to every vertex in H. The problem of whether H has an independent set of size k is easily seen to be equivalent to whether G has an induced tree of size n + k."

Source: https://doi.org/10.1016/0095-8956(86)90028-6

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

Thank you very much