Existem algoritmos de tempo poli para determinar se um gráfico é quase bipartido?

8

Dado um gráfico não direcionado G, podemos dizer que G é quase bipartido se a exclusão de k arestas (ou vértices) o tornasse bipartido.

Existem algoritmos de tempo poli para determinar se um gráfico é exatamente ou aproximadamente quase bipartido?

Lembik
fonte
1
O que você quer dizer com "aproximadamente quase bipartido"?
É difícil para o general porque é basicamente o problema do corte máximo. Eu não acho que esta é a pesquisa de nívelk
Sasho Nikolov
@RickyDemer, quis dizer que a saída poderia ser uma aproximação de 1 + eps do número de arestas ou vértices necessários para tornar o gráfico bipartido, por exemplo. Eu permitiria alguma probabilidade de erro também.
Lembik

Respostas:

16

A versão do vértice é chamada "ciclo ímpar transversal"; é NP-completo, mas com parâmetros fixos tratáveis. Vejo:

Yannakakis, Mihalis (1978), "Problemas completos de NP com exclusão de nó e borda", Anais do 10º Simpósio da ACM sobre Teoria da Computação (STOC '78), pp. 253-264, doi: 10.1145 / 800133.804355 .

Reed, Bruce; Smith, Kaleigh; Vetta, Adrian (2004), "Localizando ciclos transversais ímpares", Operations Research Letters, 32 (4): 299-301, doi: 10.1016 / j.orl.2003.10.009 .

Hüffner, Falk (2005), "Engenharia de algoritmos para uma bipartização ótima de grafos", Algoritmos experimentais e eficientes: 240-252, doi: 10.1007 / 11427186_22 .

A versão de borda foi chamada de "bipartização de borda"; também é NP-completo, mas com parâmetros fixos tratáveis. Vejo:

Guo, Jiong; Gramm, Jens; Hüffner, Falk; Niedermeier, Rolf; Wernicke, Sebastian (2006), "Algoritmos de parâmetros fixos baseados em compressão para conjunto de vértices de feedback e bipartização de arestas", JCSS 72 (8): 1386–1396, doi: 10.1016 / j.jcss.2006.02.001 .

(adicionado após o comentário de daniello):

O ciclo ímpar transversal possui um algoritmo de aproximação , mas (assumindo a conjectura de jogos únicos) não possui aproximação de fator constante; veja (referências copiadas de "On Kernels polinomiais para parametrizações estruturais do ciclo ímpar transversal" por Jansen e Kratsch):O(registron)

Agarwal, Amit, Charikar, Moses, Makarychev, Konstantin, Makarychev, Yury, algoritmos de aproximação para algoritmos de aproximação Min UnCut, exclusão Min 2CNF e problemas de corte direcionado, STOC'05, pp. 573–581 .O(registron)

Khot, S., Sobre o poder de jogos únicos de 2 provadores e 1 round, STOC '02, pp. 767-775.

Wernicke, S., Sobre a tratabilidade algorítmica da análise de polimorfismo de nucleotídeo único (SNP) e problemas relacionados. Dissertação de mestrado, Instituto Wilhelm-Schickard für Informatik, U. Tübingen (2003)

David Eppstein
fonte
Eu me lembro o problema também é jogos únicos difícil aproximar dentro de qualquer fator constante, mas não se lembra da referência
Daniello
Obrigado por esta ótima resposta. Os resultados da dureza não podem existir algoritmos de teste de propriedade do tempo poli, mesmo se permitirmos aproximação e aleatoriedade?
Lembik 29/08/16
O maior autovalor do Laplaciano dá alguma indicação de bipartidade?
Lembik