Encuentre qué vértices eliminar del gráfico para obtener el componente más grande más pequeño

Dado un gráfico , encuentre vértices , cuya eliminación daría como resultado un gráfico con el componente más grande más pequeño. $G = (V, E)$$k$$\{v^*_1,\dots,v^*_k\}$

Supongo que para grandesy grande el problema es difícil (NP-hard), pero estoy interesado en valores pequeños de ( ).$n = |V|$$k$$k$$k \in \{1, 2, 3, 4\}$

Para , creo que es posible encontrar el mejor vértice para eliminar realizando una sola búsqueda en profundidad de la gráfica (es decir, verificando los puntos de articulación).$k = 1$$\{v^*_1\}$

Para , sería posible encontrar los mejores vértices realizando búsquedas de profundidad primero (cada una de ellas para el gráfico ). Se podría aplicar un enfoque similar en el caso .$k = 2$$\{v^*_1, v^*_2\}$$n$$G_i = G / \{v_i\}$$k > 2$

Me pregunto si hay una solución mejor que esa.

(Relacionado: contar el número mínimo de vértices sin enumerarlos necesariamente )

El problema que está describiendo se conoce como Conectividad de orden de componentes en el campo de las medidas de vulnerabilidad de los gráficos . La versión de decisión del problema es la siguiente:

Conectividad de orden de componentes :

Entrada: Gráfico , enteros y$G = (V,E)$$k$$\ell$

Pregunta: ¿Existe un conjunto de vértices de tamaño como máximo tal que el tamaño del componente más grande de sea ​​como máximo ?$X \subseteq V$$k$$G - X$$\ell$

El problema es obviamente NP-completo ya que generaliza la cobertura de vértices; el caso cuando es la cubierta del vértice. Por lo tanto, el problema no puede ser un parámetro fijo manejable cuando es parametrizado por (a menos que ). También se sabe que el problema es -hard cuando está parametrizado por . Por lo tanto, tenemos que recurrir a algoritmos con un tiempo de ejecución exponencial en .$\ell=1$$\ell$$FPT = W[1]$$W[1]$$k$$k+\ell$

Pregunta muy interesante Para la entrada$G,k,\ell$, un enfoque de fuerza bruta sería:

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

El algoritmo se ejecuta a tiempo. $(\ell + 1)^k \cdot n^2$.

Observe que cualquier instancia de sí $G,k,\ell$ del problema tiene ancho de árbol y, de hecho, ancho de ruta como máximo $k+\ell$. Esto se puede observar al ver que tomar un conjunto de eliminación$X$ de tamaño como máximo $k$ produce un gráfico $G-X$ donde cada componente conectado tiene tamaño como máximo $\ell$. Por lo tanto, una descomposición de ruta válida es simplemente construir una bolsa para cada uno de los componentes en$G-X$ y luego agregue todo $X$a cada bolsa Se deduce que cualquier instancia de sí tiene$|E(G)| \leq n(k+\ell)$.

Un problema relacionado se ha estudiado en el pasado con el nombre de Integridad de gráficos o Integridad de vértices para distinguir la versión de eliminación de vértices y la versión de eliminación de bordes:

Integridad de vértices :

Entrada: gráfico$G = (V,E)$entero $p$

Pregunta: ¿Existe un conjunto de vértices?$X \subseteq V$ tal que $|X| + \max_{D \in cc(G-X)}|D| \leq p$?

Es decir, la suma del conjunto de eliminación y el tamaño del componente máximo deben minimizarse. Este problema también es NP-hard. Ver, por ejemplo,

• Clark, LH, Entringer, RC, Fellows, MR: Complejidad computacional de integridad. J. Combin. Matemáticas. Combin Comput 2, 179-191 (1987)
• Fellows, M., Stueckle, S .: El orden de inmersión, los subgrafos prohibidos y la complejidad de la integridad de la red. J. Combin. Matemáticas. Combin Comput 6, 23–32 (1989)