Algoritmo de conjunto independiente máximo

Question

No creo que exista un algoritmo para encontrar el máximo conjunto de vértices independiente en un gráfico bipartito distinto del método de fuerza bruta para encontrar el máximo entre todos los conjuntos independientes posibles.

Me pregunto acerca del pseudocódigo para encontrar todos los posibles conjuntos de vértices.

Diga un gráfico bipartito con 4 vértices azules y 4 rojos. Actualmente me

Start with an arbitrary blue, 
    find all red that don't match this blue 
    put all these red in Independent Set 
    find all blue that dont match these red 
    put these blue in Independent Set 
    Repeat for next vertex in blue 

Repeat all over again for all blue then all vertices in red. 

que entender que de esta manera no me da todas las posibles combinaciones de conjunto independiente en absoluto, ya que tras el primer paso que estoy eligiendo todos los siguientes vértices de color que no coinciden en vez de pasar a través de cada posibilidad.

Por ejemplo da una gráfica la búsqueda

B R 
1 1 
1 3 
2 1 
2 3 
3 1 
3 3 
4 2 
4 4 

Start with blue 1 
    Choose red 2 and 4 since they dont match 
    Add 2, 4 to independent Set 
    Choose 2 and 3 from blue since they dont with 2 or 4 from red 
    Add 2 and 3 from blue to independent set as well. 
Independent Set = 1,2,3 from blue 2,4 from red 
Repeat for blue 2, blue 3, ... red n (storing the cardinality for each set) 

¿Hay alguna manera de mejorar este algoritmo para mejorar la búsqueda de todas las posibilidades. Sé que a | Conjunto máximo para un gráfico bipartito | = | Rojo | + | Azul | - | Coincidencia máxima |

El problema surge con la posibilidad de que al elegir todo el rojo posible en el primer intento para un azul determinado, si esos rojos se conectan al resto de azul posible, mi conjunto solo tiene todos los 1 azul y rojo restante.

Answer 1

No creo que exista un algoritmo para encontrar el máximo conjunto de vértices independientes en un gráfico bipartito distinto del método de fuerza bruta para encontrar el máximo entre todos los conjuntos independientes posibles.

No: encontrar el conjunto máximo de independiente es equivalente a encontrar la cobertura mínima vértice (tomando el complemento del resultado), y Konig's theorem establece que la cubierta vértice mínimo en grafos bipartitos es equivalente a un emparejamiento máximo, y que esa se puede encontrar en tiempo polinomial. No sé si encontrar todas las coincidencias, pero parece que puede haber muchas.

Answer 2

Como Aaron McDaid menciona en su respuesta ahora eliminada, el problema de encontrar un conjunto máximo independiente es equivalente a encontrar una camarilla máxima. La equivalencia es que encontrar un conjunto independiente máximo en un grafo G es lo mismo que encontrar una camarilla máxima en el complemento de G. Se sabe que el problema es NP-completo.

La solución de fuerza bruta que menciona toma O(n^2 2^n), pero puede hacerlo mejor que esto. Robson tiene un artículo titulado "Algoritmos para conjuntos independientes máximos" de 1986 que da un algoritmo que toma O(2^{c*n}) para una constante 0<c<1 (creo que c es alrededor de 1/4, pero podría estar equivocado). Nada de esto es específico de un gráfico bipartito .

una cosa a notar si tiene un grafo bipartito es que ambos lados se forma un conjunto independiente. en el grafo bipartito completo K_{b,r} que está dividida B x R con |B|=b y |R|=r donde hay un borde de cada vértice en B a cada vértice en R y ninguno dentro de B ni ninguno dentro de R, un conjunto independiente máximo es B si b>=r, de lo contrario es R.

Tomando B o R no funcionará en general.sdcvvc anotó el ejemplo con los vértices {1,2,3,A,B,C} y los bordes {A,1}, {A,2}, {A,3}, {B,3}, {C,3}. En este caso, el conjunto independiente máximo es {1,2,B,C}, que es más grande que la partición {A,B,C} o {1,2,3}.

Puede mejorar el algoritmo de Robson para comenzar con el mayor de B o R y proceder a partir de ahí, aunque no estoy seguro de la gran diferencia que esto supondrá.

Alternativamente, puede usar el Hopcroft–Karp algorithm en el complemento bipartito de un gráfico para encontrar una coincidencia máxima, y ​​luego tomar los vértices utilizados en la coincidencia como el conjunto independiente. Esto proporciona un algoritmo de tiempo polinomial para resolver el problema.