SDP relajación de conjunto independiente

Estoy mirando la página 28 de Lovasz "Programas semidefinidos y optimización combinatoria" y ofrece la siguiente aproximación del número de independencia del gráfico

max u^{'} Z u

$\max u' Z u$ sujeto a

Z ≻ 0

$Z\succ 0$

Z_{i j} = 0 \forall i j \in E (G)

$Z_{ij}=0 \ \forall ij\in E(G)$

t r (Z) = 1

$tr(Z)=1$

¿Puedo obtener un conjunto independiente (o algo parecido a un conjunto independiente) directamente de la solución de relajación SDP? Lovasz dice que SDP es la única forma conocida de resolver este problema exactamente para gráficos perfectos, ¿sigue siendo cierto?

Aclaración: hay una relajación SDP similar para el tamaño del corte máximo, y puedo obtener la solución completa (el corte real, en lugar de su tamaño) tomando raíz cuadrada de Z y haciendo redondeo aleatorio (Ch.6 del libro de Williamson / Shmoys ) Me pregunto si hay una técnica similar para este problema.

ds.algorithms graph-theory semidefinite-programming independent-set Yaroslav Bulatov
fuente

Para la primera pregunta, realmente no entiendo lo que quieres decir con "el conjunto independiente real". El SDP es una relajación, por lo que el valor óptimo del SDP limita el número de independencia desde arriba. Si difieren, ningún conjunto independiente alcanza el valor óptimo del SDP. Este puede ser el caso si el gráfico no es perfecto. ¿Podría hacer más explícito lo que necesita para su "conjunto independiente real"?

Yoshio Okamoto

Quiero obtener el conjunto independiente más grande en lugar del "tamaño del conjunto independiente más grande"

Yaroslav Bulatov

Gracias por la aclaración, pero todavía me pregunto. El SDP para corte máximo se utiliza para aproximación. A saber, el redondeo aleatorio proporciona un corte que tiene un valor "cercano" al valor de corte óptimo, no necesariamente un corte máximo real. Si necesita una técnica similar, supongo que lo que realmente quiere es un conjunto independiente que tenga un tamaño cercano al número de independencia. ¿O te concentras en gráficos perfectos o quieres lidiar con gráficos generales?

Yoshio Okamoto

Quiero encontrar el conjunto máximo independiente en Perfect Graph. ipsofacto da una solución, pero requiere resolver varios SDP

Yaroslav Bulatov

Respuestas:

Creo que SDP es la única técnica conocida para resolver el problema de conjunto máximo independiente en gráficos perfectos. Para obtener el conjunto independiente, uno podría hacer lo siguiente. Adivina si un vértice está en el conjunto independiente, bórralo y resuelve el SDP. Si devuelve el mismo valor, entonces hay un conjunto independiente sin este vértice. Entonces, haga este vértice adyacente a todos los otros vértices y continúe. Esto debería darle un conjunto independiente real.

De lo contrario, hemos identificado un vértice del conjunto independiente, y podemos eliminarlo y continuar en el gráfico restante.

ipsofacto
fuente

Además, esto se ha implementado y funciona bastante bien (con algunas optimizaciones): E. Alper Yıldırım y Xiaofei Fan-Orzechowski, Sobre la extracción de conjuntos máximos estables en gráficos perfectos usando la función Theta de Lovász , optimización computacional y aplicaciones 33 , 229–247, 2006 . dx.doi.org/10.1007/s10589-005-3060-5

András Salamon

Interesante ... parece que no se requiere perfección para que la estimación SDP del número de independencia sea exacta (aquí hay un ejemplo de mathoverflow.net/questions/57336/… ), por lo que esto debería funcionar para una clase más grande de gráficos

Yaroslav Bulatov

@Yaroslav: Tienes razón, no se requiere perfección. Pero si adapta la estrategia sugerida por ipsofacto, necesitará que la eliminación de vértices también tenga la misma propiedad. Esta condición se cumple automáticamente si el gráfico es perfecto, pero de lo contrario, debe tener cuidado.

Yoshio Okamoto

No estoy seguro si el comentario de Lovasz aún se mantiene. Ha habido algunos trabajos recientes sobre este (y otros) problemas en gráficos perfectos. Debe echar un vistazo al siguiente enlace para conocer las técnicas que implican el paso de mensajes en lugar de resolver SDP: http://www.cs.columbia.edu/~jebara/papers/uai09perfect.pdf

Nicholas Ruozzi
fuente

Interesante artículo, ¿entiendo correctamente que si max-product converge en un gráfico perfecto, entonces la decodificación codiciosa recuperará el máximo conjunto independiente?

Yaroslav Bulatov

He hojeado el documento, pero no pude encontrar cómo los métodos resuelven el problema de conjunto independiente máximo para gráficos perfectos en tiempo polinómico. El número de camarillas máximas puede ser exponencial en un gráfico perfecto, por lo que los tiempos de ejecución en los corolarios 1 y 2 no son polinómicos. Aunque no entiendo mucho el contenido de la Sección 7, no veo qué problema de optimización lineal resuelve el método de la Sección 7. Los experimentos se realizan para el problema de coincidencia máxima, pero no para el problema de conjunto independiente máximo.

Yoshio Okamoto

@yoshio Tienes razón. Se sabe que el LP para MWIS es integral si incluye las restricciones apropiadas sobre todas las camarillas (exponencialmente muchas). Y es la perfección del gráfico de camarilla lo que discute el artículo. Parece que los autores solo conjeturan que max-product en un NMRF siempre produce la asignación correcta de MAP.

Nicholas Ruozzi

Gracias. Entonces, ¿puedo suponer que el documento no proporciona un algoritmo de tiempo polinómico para el problema de conjunto independiente máximo para gráficos perfectos?

Yoshio Okamoto

@YoshioOkamoto: parece que sí. Un artículo reciente da un ejemplo de un gráfico perfecto donde este enfoque converge a una solución incorrecta. Figura 3 de "Revisión de la estimación de MAP, transmisión de mensajes y gráficos perfectos" ( datalab.uci.edu/papers/AISTATS_perfect_graphs.pdf )

Yaroslav Bulatov