[Solved]: Find which vertices to delete from graph to get smallest largest component

Problem Detail: 

Given a graph $G = (V, E)$, find $k$ vertices $\{v^*_1,\dots,v^*_k\}$, which removal would result in a graph with smallest largest component.

I assume for large $n = |V|$ and large $k$ the problem is difficult (NP-hard), but I am interested in small values of $k$ ($k \in \{1, 2, 3, 4\}$).

For $k = 1$, I think it is possible to find best vertex $\{v^*_1\}$ to remove by performing single depth-first-search of the graph (i.e., checking articulation points).

For $k = 2$, it would be possible to find best vertices $\{v^*_1, v^*_2\}$ by performing $n$ depth-first searches (each of them for graph $G_i = G / \{v_i\}$). A similar approach could be applied in the case $k > 2$.

I wonder if there is any better solution than that.

(Related: counting the minimum number of vertices without necessarily enumerating them)

Asked By : MindaugasK

Answered By : Pål GD

The problem you are describing is known as Component Order Connectivity in the field of vulnerability measures of graphs. The decision version of the problem is as follows:

Component Order Connectivity:

Input: Graph $G = (V,E)$, integers $k$ and $\ell$

Question: Does there exist a set of vertices $X \subseteq V$ of size at most $k$ such that the size of the largest component of $G - X$ is at most $\ell$?

The problem is obviously NP-complete since it generalizes vertex cover; the case when $\ell=1$ is vertex cover. Hence the problem cannot be fixed parameter tractable when parameterized by $\ell$ (unless $FPT = W[1]$). The problem is also known to be $W[1]$-hard when parameterized by $k$. Hence, we have to resort to algorithms with an exponential running time in $k+\ell$.

Very interesting question. For input $G,k,\ell$, a brute force approach would be:

branching(G,k,l):     Find a connected set of vertices D of G of size l+1     if no such D exists:             return True // no component of size > l     for v in D:         if branching(G-v,k-1,l):             return True     return False 

The algorithm runs in time $(\ell + 1)^k \cdot n^2$.

Observe that any yes instance $G,k,\ell$ of the problem has treewidth, and indeed pathwidth at most $k+\ell$. This can be observed by seeing that taking a deletion set $X$ of size at most $k$ yields a graph $G-X$ where every connected component has size at most $\ell$. Hence, a valid path decomposition is simply to construct one bag for each of the components in $G-X$ and then add all of $X$ to every bag. It follows that any yes instance has $|E(G)| \leq n(k+\ell)$.

A related problem has been studied in the past under the name Graph Integrity, or Vertex Integrity to distinguish the vertex deletion version and the edge deletion version:

Vertex Integrity:

Input: Graph $G = (V,E)$, integer $p$

Question: Does there exist a set of vertices $X \subseteq V$ such that $|X| + \max_{D \in cc(G-X)}|D| \leq p$?

That is, the sum of the deletion set and the size of the maximal component should be minimized. This problem is also NP-hard. See, e.g.,

• Clark, L.H., Entringer, R.C., Fellows, M.R.: Computational complexity of integrity. J. Combin. Math. Combin. Comput 2, 179–191 (1987)
• Fellows, M., Stueckle, S.: The immersion order, forbidden subgraphs and the complexity of network integrity. J. Combin. Math. Combin. Comput 6, 23–32 (1989)

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/12789