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)

  • $\begingroup$ well this is indeed very similar question $\endgroup$ – MindaugasK Jul 9 '13 at 8:35
  • 2
    $\begingroup$ 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. $\endgroup$ – Gilles 'SO- stop being evil' Jul 16 '13 at 17:07

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$;

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.