conjunto máximo independente de vértices
TRANSCRIPT
Problemas NP – Completos
de * de 15
Teoria da Computação
Maximum Independent Set
por
Diego Magalhães CunhaMycke Richard Guntijo
Tauan Nascimento Almeida
Problemas NP – Completos
de * de 15
Agenda
1. Introdução 2. Definição do Problema3. Prova de NP – Completude4. Solução Computacional5. Exemplos6. Conclusão7. Referências
Maximum Independent Set
Problemas NP – Completos
de * de 15
1. Introdução
● Definido por Karp em 1972.
● Encontrar o maior conjunto independente de
vértices. Conjunto Independente de vértices
máximo.
● Equivalente a encontrar um clique máximo em
um grafo completo.
Maximum Independent Set
Problemas NP – Completos
de * de 15
2. Definição do Problema
O conjunto independente de Vértices (CI) de um
grafo G = (V, A) é constituído do subconjunto
V' ⊆ V, tal que v, w ∈ V' ⇒ (v, w) ~∈ A, isto é,
todo par de vértices de V' é não adjacente (i.
e. V' é um subgrafo totalmente desconectado).
Maximum Independent Set
Problemas NP – Completos
de * de 15
2. Definição do Problema
Um conjunto independente é maximal quando não existe nenhum outro conjunto independente que o contenha (i.e. um conjunto que não pode ser completado).
Maximum Independent Set
Problemas NP – Completos
de * de 15
2. Definição do Problema
Este é máximo se todos os outros conjuntos independentes têm cardinalidade menor ou igual.
Maximum Independent Set
Problemas NP – Completos
de * de 15
3. Prova de NP – Completude
O problema de encontrar o CI máximo de um
grafo (PCI) é NP-Completo, pois não existe um
algoritmo determinista que o resolva em tempo
polinomial e o problema do clique (PC) pode ser
reduzido polinomialmente ao PCI.
Maximum Independent Set
Problemas NP – Completos
de * de 15
3. Prova de NP – Completude
Redução do Clique - Clique de um grafo G = (V,
A) é constituído do subconjunto V' ⊆ V , tal que
v, w ∈ V' ⇒ (v, w) ∈ A, isto é, todo par de
vértices de V' é adjacente (V' é um subgrafo
completo).
No grafo exemplo apresentado, V' =
{1, 2} é um exemplo de cardinalidade 2.
Maximum Independent Set
Problemas NP – Completos
de * de 15
3. Prova de NP – Completude
Considere A1 o problema do clique e A2 o
problema do conjunto independente de vértices.
Uma instância I do clique consiste em um grafo
G(V, A) e um inteiro k > 0.
A instância f(I) de conjunto independente pode
ser obtida considerando-se o grafo
complementar de G e o mesmo inteiro k.Maximum Independent Set
Problemas NP – Completos
de * de 15
3. Prova de NP – Completude
A função f(I) é uma transformação polinomial
porque:● O complemento de G pode ser obtido a partir de
G em tempo polinomial.
● G possui clique de tamanho ≥ K se e somente o
complemento de G possui conjunto
independente de vértices de tamanho ≥ k.
Maximum Independent Set
Problemas NP – Completos
de * de 15
3. Prova de NP – Completude
Maximum Independent Set
Problemas NP – Completos
de * de 15
3. Prova de NP – Completude
Maximum Independent Set
Problemas NP – Completos
de * de 15
4. Solução Computacional
● Através de força bruta
● Enumerar todo conjunto S ⊆ V
● Verificar se S é independente
● Se sim, verificar se S é o maior conjunto
independente até o momento
Maximum Independent Set
Problemas NP – Completos
de * de 15
4. Solução Computacional
Maximum Independent Set
Problemas NP – Completos
de * de 15
5. Exemplos
Aplicações práticas:
I. Reunir o maior número possível de pessoas do seu círculo de amizades que não se conhecem;
II. O conjunto máximo de projetos que podem ser executados em paralelo em um único período de tempo;
III. Resolver o problema das n rainhas.
Maximum Independent Set
Problemas NP – Completos
de * de 15
6. Conclusões
● Algoritmos genéticos são muito utilizados na
tentativa de uma aproximação da solução
ótima.
● Já existem bibliotecas para aproximação da
solução ótima, como a NetworkX.
Maximum Independent Set
Problemas NP – Completos
de * de 15
7. Referências[1] PAPADIMITRIOU, Christos H. & STEIGLITZ, Kenneth. Combinatorial optimization – algorithms and complexity, Dover Publications, 1998, pp. 342-405.
[2] SKIENA, S. S., Who is interested in algorithms and why? - lessons from Stony Brook algorithm repository. In: Second Workshop on Algorithm Engineering (WAE'98), pp. 204-212, Saarbrücken, Germany, 1998.
[3] NetworkX, < http://networkx.github.com/ >, Acesso em 23 de fevereiro de 2013.
Maximum Independent Set