Método para hacer bipartito un grafo

Question

Si tomamos un gráfico $G$ y eliminamos secuencialmente la arista que pertenece al mayor número de ciclos Impares hasta que tengamos un grafo bipartito, ¿quedarán al menos la mitad de las aristas cuando el grafo sea bipartito?

Antecedentes: Es bien conocido todo gráfico, $G$ tiene un subgrafo bipartito con al menos $e(G)/2$ bordes ( $e(G)$ es el número de aristas en $G$ ). Una forma de encontrar tal subgrafo es añadir vértices codiciosamente a uno de los dos vasos en cada paso minimizando el número de aristas que se cruzan. Así que mi interés está en un método codicioso basado en la interpretación del ciclo bipartiteness en lugar de la interpretación de dos colores.

Nota: Este problema ha sido crossposted y resuelto en el negativo en MO https://mathoverflow.net/questions/180370/a-method-for-making-a-graph-bipartite Curiosamente, ni siquiera podemos sustituir $1/2$ con cualquier constante positiva.

Answer 1

Este problema se conoce generalmente en la literatura como el Problema de Zarankiewicz, que tiene una página wiki muy informativa en http://en.wikipedia.org/wiki/Zarankiewicz_problem .

Se centra principalmente en los límites teóricos del número mínimo de aristas que deben eliminarse de un grafo para convertirlo en bipartito. Una idea clave es considerar la estructura de camarilla máxima del grafo. Si el mayor subgrafo completo (o camarilla) tiene m nodos, digamos m pares, no es posible obtener una bicoloración de los m nodos sin eliminar al menos m/2*(m/2-1) aristas. Esto sugiere que una posible ruta para un algoritmo sería un método de rama y límite basado en un análisis de la estructura de la camarilla. Se pueden obtener límites más estrictos, como se indica en el sitio web wiki mencionado anteriormente, basándose en la estructura del grafo y conociendo el número máximo de camarillas.

Por supuesto, los métodos heurísticos, basados en la estructura del ciclo, también pueden ser de interés en las aplicaciones prácticas de este problema.

Answer 2

NO. Partiendo de un gráfico completo con $n$ vértices y $\binom{n}2$ bordes puede acabar teniendo una "estrella" con sólo $n-1$ bordes.