Relaxamento LP de conjunto independente

13

Eu tentei o seguinte relaxamento de LP do conjunto independente máximo

max \sum_{i} x_{Eu}

$\max \sum_i x_i$

st x_{Eu} + x_{j} \leq 1 \forall (Eu, j) \in E

$\text{s.t.}\ x_i+x_j\le 1\ \forall (i,j)\in E$

x_{Eu} \geq 0 0

$x_i\ge 0$

Eu recebo $1/2$ para cada variável para cada gráfico cúbico não bipartido que tentei.

É verdade para todos os gráficos cúbicos não bipartidos conectados?
Existe relaxamento de LP que funciona melhor para esses gráficos?

Atualização 03/05 :

Aqui está o resultado do relaxamento de LP baseado em clique sugerido por Nathan

Resumi experiências aqui. Curiosamente, parece haver alguns gráficos não bipartidos para os quais o relaxamento mais simples do LP é essencial.

graph-theory co.combinatorics linear-programming Yaroslav Bulatov
fonte

A solução certamente não é única. Em um gráfico bipartido cúbico, você pode ter uma solução ideal com em uma parte e na outra parte.

x_{i} = 1 / 2

$x_i = 1/2$

x_{i} = 1

$x_i = 1$

x_{i} = 0

$x_i = 0$

Jukka Suomela

1

Desculpe, perdi uma parte importante, considero apenas gráficos cúbicos não bipartidos. Todo grafo cúbico bipartite Tentei tinha uma solução integral

Yaroslav Bulatov

Você também precisa adicionar "conectado" se quiser evitar soluções não exclusivas.

Jukka Suomela

2

(1) Você esqueceu de escrever as restrições da não-negatividade. (2) Para gráficos bipartidos, o valor ótimo desse relaxamento de LP é sempre igual ao tamanho máximo de um conjunto independente. Este é um corolário imediato do teorema de König .

Tsuyoshi Ito

2

@Yaroslav: Uma pergunta paralela: como você desenha esses gráficos?

Tim

16

Não bipartido ligado gráficos cúbicos têm a única solução óptima ; em um gráfico cúbico bipartido, você tem uma solução ideal integral. $x_i = 1/2$

Prova: em um gráfico cúbico, se você somar todos os restrições , terá e, portanto, o ideal é no máximo . $3n/2$ $x_i + x_j \le 1$ $\sum_i 3 x_i \le 3n/2$ $n/2$

A solução para todos os é trivialmente viável, e, por conseguinte, também optimizada. $x_i = 1/2$ $i$

Em um gráfico cúbico bipartido, cada parte tem metade dos nós, e a solução em uma parte é, por conseguinte, também optimizada. $x_i = 1$

Qualquer solução óptima deve ser apertado, isto é, que deve ter $\sum_i 3 x_i = 3n/2$ e, por conseguinte, para cada aresta . Assim, se você tem um ciclo estranho, você deve escolher para cada nó no ciclo. E então, se o gráfico estiver conectado, essa opção será propagada por toda parte. $x_i + x_j = 1$ $\{i,j\}$ $x_i = 1/2$

Jukka Suomela
fonte

2

Como escrevi em um comentário sobre a questão, você só precisa da bipartididade para provar a existência de uma solução ideal integral (mas isso requer uma prova diferente da sua).

Tsuyoshi Ito

@Tsuyoshi: Sim, é bom ter em mente o teorema de König. Por exemplo, juntamente com a observação acima, ele mostrará que qualquer gráfico cúbico bipartido possui uma fatoração 1 (ou seja, pode ser particionado em três combinações perfeitas). É claro que essa é a maneira "errada" de provar esse resultado, mas acho que demonstra bem o poder do teorema de König - se você se lembra do teorema de König, existem muitos resultados clássicos na teoria dos grafos que você pode reinventar facilmente .

Jukka Suomela

12

Este LP é semi-integral para todos os gráficos, ou seja, existe uma solução ideal para que cada variável esteja em {0,1 / 2,1}. Simplesmente decorre de um teorema de Nemhauser e Trotter. Obviamente, a mesma conclusão de meia integralidade segue para o LP do problema do complemento (capa de vértice). Quando o gráfico é bipartido, a solução é integral. Segue-se simplesmente do teorema min-cut de fluxo máximo ou trabalhando com soluções pontuais extremas deste LP. Além disso, as arestas de 1/2 formam um ciclo ímpar.

Obviamente, este LP não é bom para resolver problemas de SI. Adicionar restrições de Clique ou SDPs é uma abordagem muito melhor.

Embalagens de vértices: propriedades estruturais e algoritmos GL Nemhauser e Trotter-Math. Program., 1975

Mohit Singh
fonte

Certo, veja também o Teorema 5.6 de deste documento, para um algoritmo muito simples que encontra com eficiência uma solução semi-integral.

Jukka Suomela

O LP com restrições Clique resolveu cerca de 50% mais gráficos do conjunto acima .... onde posso encontrar a formulação SDP?

Yaroslav Bulatov 01/03

7

A tese de doutorado de Sergiy Butenko de 2003 revisa alguns outros relaxamentos de LP da MIS, bem como alguns relaxamentos quadráticos.

Suresh Venkat
fonte

6

$K_4$

Isso é chamado de número de conjunto independente fracionário. Você encontrará algumas informações lá: http://en.wikipedia.org/wiki/Fractional_coloring ou no livro "Teoria dos grafos fracionais" de Daniel Ullman e Edward Scheinerman ( http://www.ams.jhu.edu/~ers / fgt / ).

Praticamente, essa formulação é NP-Difícil de calcular, mesmo que todas as variáveis sejam contínuas -> o número de panelinhas é exponencial e difícil de calcular ... Mas você é livre para enumerar apenas algumas panelinhas especiais, por exemplo, apenas as arestas (que você acabou de fazer) ou arestas + triângulos ou todas as panelinhas até $K_k$

Nathann

(*) dito isto, você teoricamente tem uma diferença arbitrariamente grande entre o resultado ideal no LP, onde todas as panelinhas são representadas e o conjunto independente ideal

Nathann Cohen
fonte

1

k

$k$

(k + 1)

$(k+1)$

x_{i} = 1 / k

$x_i = 1/k$

i

$i$

interessante, isso parece estar relacionado com a facilidade de IndependentSet em grafos cordais

Yaroslav Bulatov

Fiz algumas experiências, ea solução deste LP relaxamento sempre foi integral na grafos cordais

Yaroslav Bulatov

1

@YaroslavBulatov Há uma razão para sua observação. As desigualdades de clique e os limites da não-negatividade fornecem o casco convexo de conjuntos independentes, se e somente se o gráfico for perfeito. Os gráficos de acordes são perfeitos.

precisa

Relaxamento LP de conjunto independente

Respostas: