Exemplos apertados para aproximar o problema do conjunto de vértices de feedback

8

Existem vários algoritmos de 2 aproximações para o problema de conjunto de vértices de feedback UNWEIGHTED (FVS), que estão resumidos em [4]. Observe que a redução da cobertura do vértice para o FVS preserva a aproximação. Assumindo uma conjectura de jogo única, não podemos esperar algoritmos melhores. A questão é:

Existe um gráfico não ponderado no qual parte do algoritmo realmente atinja a proporção 2?

[1] contém um exemplo tão restrito para FVS ponderada.

  1. Vineet Bafna e Piotr Berman e Toshihiro Fujito, http://doi.org/10.1137/S0895480196305124 ;
  2. Ann Becker e Dan Geiger, http://doi.org/10.1016/0004-3702(95)00004-6 ;
  3. Toshihiro Fujito, http://doi.org/10.1016/0020-0190(96)00094-4 ;
  4. Fabián A. Chudak, Michel X. Goemans, Dorit S. Hochbaum, David P. Williamson, http://doi.org/10.1016/S0167-6377(98)00021-2 .
Yixin Cao
fonte

Respostas:

7

2-o(1)

GnKn,nn2n-4Gn

insira a descrição da imagem aqui

(observe que não há arestas entre os vértices da cerceta).

n-1

Agora não há ciclos semi-disjuntos, e os graus dos vértices são os seguintes:

  1. n
  2. n-1

F

F

FFVS2n-4

2n-4n-1=2-o(1)

RB
fonte
Obrigado! É exatamente isso que eu quero. Apenas um pequeno comentário: se eu entender o algoritmo de Bafna et al. Corretamente, os vértices roxos não serão inseridos na pilha, pois depois que todos os vértices azuis estiverem inseridos, o gráfico restante será acíclico (um caminho em quatro vértices).
Yixin Cao
@YixinCao - embora o gráfico seja realmente acíclico após a remoção dos azuis, eles ainda fazem loop em todos os vértices do peso residual 0, e os azuis e roxos chegam a 0 na mesma iteração. Pelo menos é o que parece no jornal deles.
RB
G1
desculpe, você está correto, e eu entendi algo errado.
Yixin Cao