Análise Strucu

PROJETO E ANALISE DE ALGORITMOS (INF 2926)
3a Lista de Exerccios
1. Considere os seguintes problemas:
 Vertex Cover (VC): Dados um grafo (n~ao orientado) G = (V;E) e um inteiro positivo
K  jV j; determinar se existe S  V , jSj  K, tal que para toda aresta (u; v) 2 E, pelo menos um entre u e v, pertence a S.
 Dominating Set (DS): Dados um grafo (n~ao orientado) H = (N;A) e um inteiro positivo
L  jNj; determinar se existe U  N, jUj  L, tal que para todo vertice w 2 N n U existe um vertice u 2 U tal que (u;w) 2 A.
 Uncapacitated Facility Location (UFL): Dados conjuntos M e N, inteiros cij para i 2 M e j 2 N, inteiros fj para j 2 N e um inteiro T; determinar se existe um conjunto J  N tal que
P
i2M min j2J cij +
P
j2J fj  T.
(a) Sabendo que (VC) e NP-completo (foi provado em aula!), prove que (DS) tambem e
NP-completo.
Dicas: Observe que todo VC e um DS. Pense em formas de obrigar que um DS tambem seja um VC, ou seja se cobrir todos os vertices no grafo do problema (DS) (o grafo H) ent~ao cobre todas a arestas da inst^ancia (o grafo G) do problema VC. Voc^e precisara incluir um vertice para cada aresta no VC. E o que mais ?
(b) Sabendo que (VC) e NP-completo (foi provado em aula!), prove que (UFL) tambem e
NP-completo.
Dicas: Observe que, se for interpretado que o (UFL) e denido sobre um grafo, este grafo tem dois tipos de vertices. Um deles sera associado aos vertices no VC e outro tipo sera associado as arestas no VC. O valores de cij ser~ao ou zero ou innito. Quanto valera fj e
T ?
(c) Considere a inst^ancia do (VC) onde G = (V;E) e dada na Figura 1 abaixo, sendo K =
3. Utilize as transformac~oes que voc^e prop^os nos itens anteriores para obter inst^ancias equivalentes do (DS) e do (UFL).
2. Considere um tabuleiro com 4 linhas e n colunas onde cada casa esta preenchida com um numero inteiro positivo. Voc^e possui 2n pecas e deseja colocar estas pecas no tabuleiro de modo que os