# Minimum number of vertices to remove to bound the largest connected component of a graph

I have this problem, maybe anybody could help.

Given a graph $G = (V, E)$ and an integer $k \geq 1$, find the minimum number $l$ of vertices to remove to make the largest connected component of $G \setminus \{v_1, \dots,v_l\}$ have at most $k$ vertices.

I wonder it this problem can be solved quickly (in polynomial time)?

(Related: finding the vertices when $k$ is small)

• well this is indeed very similar question – MindaugasK Jul 9 '13 at 8:35
• I've tried to translate your abbreviations into English. Don't use abbreviations like “max no”, it was very difficult to figure out what you were maximizing. Use grammatical English or mathematical notation. Please review that my translation captures your intended meaning. – Gilles 'SO- stop being evil' Jul 16 '13 at 17:07

## 1 Answer

The optimization version of this problem is known as Graph Integrity, which is unfortunately NP-Hard problem:

The integrity of a graph G, denoted $I(G)$, is defined by: $I(G) = min\{ |S| + m(G − S) : S \subset V (G) \}$ where $m(G − S)$ denotes the maximum order of a component of $G − S$;