En teoría de grafos , un no bloqueador es un subconjunto de vértices en un grafo no dirigido , todos los cuales son adyacentes a vértices fuera del subconjunto. De manera equivalente, un no bloqueador es el complemento de un conjunto dominante . [1]
El problema computacional de encontrar el no bloqueador más grande en un grafo fue formulado por Papadimitriou y Yannakakis (1991), quienes observaron que pertenece a MaxSNP . [2] Aunque calcular un conjunto dominante no es manejable con parámetros fijos bajo supuestos estándar, el problema complementario de encontrar un no bloqueador de un tamaño dado es manejable con parámetros fijos. [1]
En gráficos sin vértices aislados , cada no bloqueador máximo (aquel al que no se pueden agregar más vértices) es en sí mismo un conjunto dominante. [3]
Una forma de construir un algoritmo manejable con parámetros fijos para el problema de no bloqueadores es usar la kernelización , un principio de diseño algorítmico en el que se utiliza un algoritmo de tiempo polinomial para reducir una instancia de problema más grande a una instancia equivalente cuyo tamaño está limitado por una función del parámetro. Para el problema de no bloqueadores, una entrada al problema consiste en un gráfico y un parámetro , y el objetivo es determinar si tiene un no bloqueador con o más vértices. [1]
Este problema tiene una kernelización sencilla que lo reduce a un problema equivalente con como máximo vértices. Primero, se eliminan todos los vértices aislados de , ya que no pueden ser parte de ningún no bloqueador. Una vez hecho esto, el grafo restante debe tener un no bloqueador que incluya al menos la mitad de sus vértices; por ejemplo, si se aplica un doble color a cualquier árbol de expansión del grafo, cada clase de color es un no bloqueador y una de las dos clases de color incluye al menos la mitad de los vértices. Por lo tanto, si el grafo con los vértices aislados eliminados todavía tiene o más vértices, el problema se puede resolver inmediatamente. De lo contrario, el grafo restante es un kernel con como máximo vértices. [1]
Dehne et al. mejoraron esto a un núcleo de tamaño como máximo . Su método implica fusionar pares de vecinos de vértices de grado uno hasta que todos esos vértices tengan un solo vecino y eliminar todos menos uno de los vértices de grado uno, dejando una instancia equivalente con solo un vértice de grado uno. Luego, muestran que (excepto para valores pequeños de , que se pueden manejar por separado) esta instancia debe ser más pequeña que el límite de tamaño del núcleo o contener un bloqueador de vértices. [1]
Una vez que se ha obtenido un núcleo pequeño, se puede resolver una instancia del problema de no bloqueo en un tiempo manejable con parámetros fijos aplicando un algoritmo de búsqueda de fuerza bruta al núcleo. La aplicación de límites de tiempo más rápidos (pero aún exponenciales) conduce a un límite de tiempo para el problema de no bloqueo de la forma . Son posibles algoritmos aún más rápidos para ciertas clases especiales de grafos. [1]
