¿Existen algoritmos de poli tiempo para determinar si un gráfico es casi bipartito?

8

Dado un gráfico G no dirigido, podemos decir que G es casi bipartito si eliminar k bordes (o vértices) lo haría bipartito.

¿Existen algoritmos de poli tiempo para determinar si una gráfica es exacta o aproximadamente casi bipartita?

Lembik
fuente
1
¿Qué quieres decir con "aproximadamente casi bipartito"?
Es np-difícil para general porque es básicamente el problema de corte máximo. No creo que esto sea a nivel de investigaciónk
Sasho Nikolov
@RickyDemer Quise decir que la salida podría ser una aproximación de 1 + eps del número de aristas o vértices necesarios para hacer que el gráfico sea bipartito, por ejemplo. Permitiría alguna probabilidad de error también.
Lembik

Respuestas:

16

La versión de vértice se llama "ciclo impar transversal"; es NP completo pero manejable con parámetros fijos. Ver:

Yannakakis, Mihalis (1978), "Problemas de eliminación completa de nodos y bordes de NP", Actas del 10º Simposio de ACM sobre Teoría de la Computación (STOC '78), págs. 253–264, doi: 10.1145 / 800133.804355 .

Reed, Bruce; Smith, Kaleigh; Vetta, Adrian (2004), "Encontrar ciclos impares transversales", Cartas de investigación de operaciones, 32 (4): 299–301, doi: 10.1016 / j.orl.2003.10.009 .

Hüffner, Falk (2005), "Ingeniería de algoritmos para una bipartición de gráficos óptima", Algoritmos experimentales y eficientes: 240–252, doi: 10.1007 / 11427186_22 .

La versión de borde se ha llamado "bipartización de borde"; también es NP-complete pero manejable con parámetros fijos. Ver:

Guo, Jiong; Gramm, Jens; Hüffner, Falk; Niedermeier, Rolf; Wernicke, Sebastian (2006), "Algoritmos de parámetros fijos basados ​​en la compresión para el conjunto de vértices de retroalimentación y la bipartización de bordes", JCSS 72 (8): 1386–1396, doi: 10.1016 / j.jcss.2006.02.001 .

(agregado después del comentario de daniello):

O(logn)

O(logn)

Khot, S., Sobre el poder de los juegos únicos de 2 rondas y 1 probador, STOC '02, pp. 767–775.

Wernicke, S., Sobre la trazabilidad algorítmica del análisis de polimorfismo de un solo nucleótido (SNP) y problemas relacionados. Tesis de maestría, Wilhelm-Schickard-Institut für Informatik, U. Tübingen (2003)

David Eppstein
fuente
Parece que recuerdo que el problema también es un juego único difícil de aproximar dentro de cualquier factor constante, pero no recuerdo la referencia
daniello
Gracias por esta gran respuesta. ¿Los resultados de dureza no pueden haber un algoritmo de prueba de propiedad de tiempo polivinílico incluso si permitimos la aproximación y la aleatoriedad?
Lembik
¿El mayor valor propio del laplaciano da alguna indicación de bipartidismo?
Lembik