Erro no limite inferior para um algoritmo para cobertura de vértices

Question

Eu tenho o seguinte algoritmo aleatório para o problema de cobertura de vértices.Deixar $B_0$ seja o conjunto de saída:

• Corrigir alguma ordem $e_1, e_2, ..., e_m$ sobre todas as arestas no conjunto de arestas E de G, e defina $B_0 = \emptyset$.
• adicionar à $B_0$ todos os vértices isolados, ou seja,aqueles sem bordas incidentes.
• Para cada borda $e$ em $e_1, e_2, ..., e_m$
  • se ambos os pontos finais de $e$ não contido em $B_0$, então
  • jogue uma moeda honesta decidindo qual dos pontos finais escolher e adicione esse ponto final a $B_0$.

Como posso provar isso, para cada constante $c \geq 1$, o algoritmo pode produzir um $B_0$ com $ | B_0 | ge c | opt | $?

Answer 1

Corrija um gráfico estrela de $c + 1$ vértices.Um gráfico estrela é um vértice conectado a todos os outros vértices do gráfico (um vértice universal chamado centro), e todos os outros vértices são pares. não adjacente.Aqui está um exemplo visual. $c$ é o centro da estrela.

Agora, a solução ideal é embalar o centro da estrela.O tamanho desta solução é igual a 1.Para cada aresta, suponha que nosso algoritmo empacote a outra extremidade da aresta (o vértice não universal), então precisamos empacotar todos os vértices do gráfico, exceto o centro e, portanto, precisamos embalar $c$ vértices diferentes.No total obtemos $ | B_0 | = C | opt | $ para qualquer valor arbitrário, mas fixo, de $c$.

---

ObservaçãoUma simples modificação do algoritmo produz um algoritmo de aproximação desrandomizado com tamanho de resposta no máximo duas vezes maior que o ideal.É o seguinte:se ambas as extremidades da aresta não estiverem em $B_0$, e adicione ambos pontos finais para $B_0$ e iterar.

A razão pela qual isso funciona é simples.As arestas, que têm seus extremos adicionados para uma correspondência máxima e, portanto, adicionamos duas vezes o número de vértices em uma correspondência máxima à cobertura.Observe que o tamanho de uma correspondência em um gráfico é um limite inferior para o tamanho da cobertura mínima de vértices e, portanto, adicionamos no máximo o dobro de vértices como o tamanho da cobertura mínima de vértices.