Seja G=(V, E) um grafo. Um conjunto estável de G é um subconjunto de vértices U subseteq V tal que não existe aresta entre quaisquer dois vértices em U. Uma clique de G é um subconjunto de vértices K subseteq V tal que sempre existe aresta entre quaisquer dois vértices em K. Essas arestas são as arestas da clique. Uma cobertura das arestas de G por cliques é um conjunto de cliques cuja união das arestas é E. Mostre que o problema de encontrar um conjunto estável de cardinalidade máxima é um dual para o problema de encontrar uma cobertura de arestas por cliques de cardinalidade mínima.

Passo 1

Beleza, então o enunciado pede pra mostrar que o problema “achar um conjunto estável de tamanho máximo em G” é dual, no sentido de programação linear, do problema “achar uma cobertura mínima de vértices por cliques em G” (vamos entender abaixo por que “vértices” faz mais sentido do que “arestas”).
Conteúdo/teoria que vamos usar:
  1. Como modelar o Problema do Conjunto Estável (independent set) como um PL (programação linear).
  2. Como extrair o Dual desse PL.
  3. Interpretar variáveis e restrições do Dual como uma cobertura de vértices por cliques.

Passo 2

Modelando o Máximo Conjunto Estável (primal):
  • Para cada vértice max sumvin V xv , crio uma variável sumvin C xv ;<=;1 que vale 1 se estiver no conjunto estável.
  • Objetivo:
  • Restrição para garantir que não peguemos duas pontas de uma aresta (ou seja, nada de aresta interna): para cada clique (em particular cada aresta é um clique de tamanho 2)
  • E .
Esse é o primal em PL (se relaxássemos para , em vez de binário, ele já basta pra ver a dualidade).

Passo 3

Agora montamos o Dual desse PL:
  • Para cada clique sumCcolon vin C yC ;>=;1 temos uma variável de dual min sumCsubseteq V,,,C clique yC .
  • Como no primal cada vértice aparece em todas as restrições de cliques que contêm , no Dual teremos, para cada vértice , uma restrição que “cobre” :
  • Objetivo do Dual (minimizar somatório das variáveis de cada clique):

Passo 4

Interpretação combinatória do Dual:
  • Cada seleciona (com peso 1, no caso integral) a clique .
  • A restrição exige que todo vértice seja “coberto” por pelo menos uma das cliques escolhidas.
  • Então, em termos óbvios, estamos cobrindo o conjunto de vértices de por cliques, usando o menor número de cliques.

Resposta

Portanto, a versão PL do máximo conjunto estável em é o problema Primal, e o Dual natural desse PL é exatamente o problema de cobrir todos os vértices de com o menor número de cliques. Logo, eles são problemas duais em programação linear.

Exercícios relacionados