Exercicios Resolvidos sobre 2SAT e K-Tesselação em Grafos

1 Dada uma fórmula 2SAT argumente como determinamos se ela é satisfazível e em caso positivo justifique como obter a atribuição de valores às variáveis que satisfaça a fórmula 2 Considere a seguinte definição uma tesselação de um grafo G é uma partição dos vértices de modo que cada parte é uma clique Considere o seguinte problema ktesselação em grafos Entrada Grafo G Questão G possui no máximo k tesselações de modo que a união das k tesselações cubra todas as arestas a Mostre que restrito a grafos bipartidos este problema é equivalente ao problema de coloração de arestas b Qual a complexidade computacional de ktesselação em grafos bipartidos c Sabendo que coloração de arestas para grafos sem triângulos é NPcompleto mostre que ktesselação é NPcompleto 1 Para determinar se uma fórmula 2SAT é satisfazível podemos utilizar o algoritmo de Kosaraju para encontrar as componentes fortemente conexas CFCs do grafo de implicação associado à fórmula Se existir uma variável e sua negação na mesma CFC a fórmula é insatisfazível Caso contrário a fórmula é satisfazível Se a fórmula for satisfazível podemos obter a atribuição de valores às variáveis que satisfaça a fórmula utilizando o algoritmo de atribuição de valores em CFCs 2 a Para mostrar que o problema de ktesselação em grafos bipartidos é equivalente ao problema de coloração de arestas precisamos demonstrar que uma solução para um problema pode ser transformada em uma solução para o outro Se um grafo G possui uma ktesselação podemos atribuir cores às arestas de G de forma que cada clique na tesselação tenha uma cor diferente Portanto a coloração de arestas em G é uma solução para o problema de ktesselação b A complexidade computacional do problema de ktesselação em grafos bipartidos é polinomial Grafos bipartidos podem ser representados por uma matriz de adjacência e a verificação da existência de uma ktesselação pode ser feita em tempo On3 onde n é o número de vértices do grafo c Para mostrar que ktesselação é NPcompleto podemos reduzilo a partir do problema da coloração de arestas em grafos sem triângulos que já é conhecido por ser NPcompleto Dado um grafo G sem triângulos podemos transformálo em um grafo bipartido H adicionando um novo vértice para cada vértice em G e conectandoo a todos os vizinhos do vértice correspondente em G A partir disso podemos estabelecer uma equivalência entre as ktesselações de H e as colorações de arestas em G sem triângulos Portanto ktesselação é NPcompleto