Seja
um grafo. Um conjunto estável de
é um subconjunto de vértices
tal que não existe aresta entre quaisquer dois vértices em
. Uma clique de
é um subconjunto de vértices
tal que sempre existe aresta entre quaisquer dois vértices em
. Essas arestas são as arestas da clique. Uma cobertura das arestas de
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:
Conteúdo/teoria que vamos usar:
- Como modelar o Problema do Conjunto Estável (independent set) como um PL (programação linear).
- Como extrair o Dual desse PL.
- 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
, crio uma variável 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
temos uma variável de dual . - 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.