Límite inferior de error para un algoritmo para la cobertura de vértices

Question

Tengo el siguiente algoritmo aleatorio para el problema de cobertura de vértices.Dejar $B_0$ Sea el conjunto de salida:

• arreglar algún orden $e_1, e_2, ..., e_m$ sobre todos los bordes en el conjunto de bordes E de G, y establezca $B_0 = \conjuntovacío$.
• añadir $B_0$ todos los vértices aislados, es decirlos que no tienen bordes incidentes.
• Para cada borde $e$ en $e_1, e_2, ..., e_m$
  • si ambos puntos finales de $e$ no contenido en $B_0$, entonces
  • lanzar una moneda justa para decidir cuál de los puntos finales elegir y agregar este punto final a $B_0$.

¿Cómo puedo demostrar que, por cada constante $c \geq 1$, el algoritmo podría producir un $B_0$ con $ | B_0 | ge c | opt | $?

Answer 1

Arreglar un gráfico estelar de $c + 1$ vértices.Un gráfico de estrellas es un vértice conectado a todos los demás vértices del gráfico (un vértice universal llamado centro), y todos los demás vértices están en pares. no adyacente.Aquí hay un ejemplo visual. $c$ es el centro de la estrella.

Ahora una solución óptima es empacar el centro de la estrella.El tamaño de esta solución es igual a 1.Para cada arista, supongamos que nuestro algoritmo empaqueta el otro extremo de la arista (el vértice no universal), entonces necesitamos empaquetar todos los vértices del gráfico excepto el centro y, por lo tanto, necesitamos empaquetar $c$ diferentes vértices.En total obtenemos $ | B_0 | = C | opt | $ para cualquier valor arbitrario pero fijo de $c$.

---

NotaUna simple modificación del algoritmo produce un algoritmo de aproximación desaleatorizado con un tamaño de respuesta como máximo dos veces mayor que el óptimo.Dice lo siguiente:si ambos puntos finales del borde no están en $B_0$, Luego añade ambos puntos finales a $B_0$ e iterar.

La razón por la que esto funciona es simple.Los bordes, a quienes se les agregan sus puntos finales para una coincidencia máxima y, por lo tanto, agregamos el doble de vértices en una coincidencia máxima a la cubierta.Tenga en cuenta que el tamaño de una coincidencia en un gráfico es un límite inferior del tamaño de una cobertura mínima de vértices y, por lo tanto, agregamos como máximo el doble de vértices como tamaño de la cobertura mínima de vértices.