Algoritmos FPT para o Problema
da k-Cobertura por Vértices
Roteiro






Problema da k-Cobertura por Vértices
Problemas NP-completos
Complexidade Parametrizada
Problemas FPT
Algoritmo de Buss
Algoritmo de Balasubramanian et al
Problema da k-Cobertura por
Vértices (1)


Dado um grafo G e um inteiro positivo k.
Existe um subconjunto de vértices V’, |V’|<=k, tal
que cada aresta do grafo incide em pelo menos um
vértice desse subconjunto?
v1
v2
v3
v4
v5
v6
v7
v8
v9
v10
k=4
A cobertura por vértices não
é necessariamente única.
Problema da k-Cobertura por
Vértices (2)




Uma aplicação prática: alinhamento
múltiplo de seqüências (Biologia
Computacional).
Melhor algoritmo conhecido: algoritmo
trivial da força bruta.
Tempo: O(nk).
O problema é NP-completo.
Problemas NP-completos



Na prática, precisamos encontrar
formas de resolver as instâncias que
temos em mãos.
Lidar com a intratabilidade dos
problemas é um grande desafio da
Ciência da Computação.
Vários métodos já foram desenvolvidos
com este objetivo.
Complexidade Parametrizada
(1)



Vem obtendo sucesso na solução de
instâncias que antes eram consideradas
muito grandes para serem resolvidas.
Entrada do problema: parte principal e
parâmetro.
Problemas da Teoria dos Grafos (como a
k-Cobertura por Vértices):
- parte principal: grafo;
- parâmetro: número inteiro.
Complexidade Parametrizada
(2)
COMPLEXIDADE CLÁSSICA
COMPLEXIDADE PARAMETRIZADA
parâmetro
ENTRADA
Parte principal da entrada
contribui polinomialmente

Isolar a explosão combinatorial apenas em
termos do parâmetro.
Complexidade Parametrizada
(3)



Algoritmo que gaste tempo exponencial em
relação ao parâmetro (k), mas tempo
polinomial em relação à parte principal da
entrada (x).
A assunção fundamental é k << |x|.
Principais áreas de atuação: aquelas onde
parâmetros em pequenos intervalos são
úteis em aplicações práticas.
Problemas FPT (1)

Um problema é tratável por parâmetro fixo
(FPT) se e somente se possui um algoritmo
que o resolve em tempo O(nc f(k)), onde:




n é o tamanho da parte principal da entrada
k é o parâmetro
c é uma constante independente de k
f é uma função arbitrária
Problemas FPT (2)

Existem duas técnicas algorítmicas
comuns em algoritmos FPT:


Redução ao núcleo do problema.
Árvore limitada de busca.
Redução ao núcleo do
problema



Reduzimos a instância original, em tempo
polinomial, em uma outra instância
equivalente, cujo tamanho é limitado por k.
Se houver uma solução para essa instância
reduzida, podemos transformá-la em uma
solução para a instância original.
O uso desta técnica resulta em:
O(nc + f(k)).
Árvore Limitada de Busca


Consiste em analisar exaustivamente uma
árvore criada a partir da instância reduzida
do método de redução ao núcleo do
problema, em busca de uma solução.
O tamanho da árvore deve ser limitado em
função do parâmetro k.
Problemas FPT (5)

A k-Cobertura por Vértices foi um dos
primeiros problemas que provou-se ser
FPT. A seguir, alguns resultados:
Buss
Balasubramanian et al - 1
Balasubramanian et al - 2
Niedermeier e Rossmanith
Chen, Jia e Kanj
O(kn + (2k 2 ) k k 2 )
k
2
O(kn + 1.732051 k )
k
2
O(kn + 1.324718 k )
k
2
O(kn + 1.29175 k )
O(kn + 1.271 k k 2 )
Algoritmo de Buss (1)



Resolve o problema da k-Cobertura por
Vértices em tempo O(kn + (2k2)k k2).
Baseado no método de redução ao
núcleo do problema.
Todos os vértices de grau maior que k
do grafo devem pertencer a qualquer
cobertura por vértices de tamanho
menor ou igual a k.
Algoritmo de Buss (2)



Passo 1: Seja H o conjunto de todos os vértices de G
com grau maior que k. Se |H| > k, não há cobertura.
Senão, k’ = k - |H|.
Passo 2: Criamos G’, resultado da remoção dos
vértices de G que estão em H, bem como das arestas
neles incidentes e de vértices isolados. Se G’ tiver
mais do que k.k’ arestas, não há cobertura.
Passo 3: Encontre, por força bruta, uma cobertura por
vértices de tamanho menor ou igual a k’ para G’. Se
encontrar, esses vértices mais H formam uma
cobertura por vértices desejada para G.
Algoritmo de Buss (3)
grafo
grafo G’
G
G’
G
v1
v1
v3
v3
k=3
H = {v5}
v2
v2
v4
v4
v6
v6
v5
v5
k’ = k - |H| = 2
Cobertura
porformam
vérticesuma
para G’
{v2,v3}
+ {v5}
cobertura por vértices de
v5
v6
Como
alg.será
força
|H|
G’removido
tem
<bruta:
k, menos
continua...
até
porque
encontrar
do que
tem
um
tamanho
menor
ou
igual
aé
grau
vértice
k.k’
{v2,v3}.
arestas,
maior
isolado
que
continua...
3
para
o grafo
G3.
Algoritmo de Balasubramanian
(1)



Algoritmo referente ao Teorema 1 de
Balasubramanian et al.
Resolve o problema da k-Cobertura por
Vértices em tempo
O(kn + 1.732051k k2).
Algoritmo executa o método da redução
ao núcleo do problema e depois, o
método da árvore limitada de busca.
Algoritmo de Balasubramanian
(2)




Primeiro, execute os dois primeiros passos
do algoritmo de Buss.
Crie uma árvore de busca, que será
percorrida em profundidade.
Cada nó armazena uma instância reduzida
do grafo (<G’’=(V’’,E’’)>, k’’) e uma
cobertura por vértices parcial (PVC).
A raiz da árvore armazena: <G’,k’> e H.
Algoritmo de Balasubramanian
(3)

Em cada nó da árvore, execute os passos a
seguir, até encontrar a cobertura por
vértices desejada ou até que seja
determinado que esta não existe.



Escolha um vértice v qualquer de V’’.
A partir de v, faça uma busca em profundidade que
passe por no máximo três arestas.
Baseado nos possíveis caminhos gerados, crie filhos
para o nó (Casos 1 e 2) ou reduza o grafo dentro do nó
(Casos 3 e 4).
Algoritmo de Balasubramanian
(4)

Caso 1: caminho simples v, v1, v2, v3.
Caminho gerado
em G’’
v
Árvore de Busca
<G’’=(V’’,E’’),k’’>
PVC
v1
v2
v3
<G’’’,k’’’>
<G’’’,k’’’>
<G’’’,k’’’>
<G’’’=
{v,v2},(V’’
E’’’),
-PVC
{v1,v2},
<G’’’= (V’’
E’’’),
- {v1,v3},
E’’’),
PVC(V’’ -<G’’’=
PVC
k’’’ = k’’ - 2>k’’’ = k’’ - 2> k’’’ = k’’ - 2>
PVC = PVC
PVC
 {v,v2}
= PVCPVC
 {v1,v2}
= PVC  {v1,v3}
Algoritmo de Balasubramanian
(5)

Caso 2: ciclo v, v1, v2, v.
Caminho gerado
Caminho gerado
em G’’
em G’’
vv
v1
v1
Árvore de Busca
Árvore de Busca
<G’’=(V’’,E’’),k’’>
<G’’=(V’’,E’’),k’’>
PVC
PVC
v2
v2
<G’’’,k’’’>
<G’’’,k’’’>
<G’’’,k’’’>
<G’’’,k’’’>
<G’’’,k’’’>
<G’’’,k’’’>
<G’’’=
(V’’ -<G’’’=
{v,v1},(V’’
E’’’),
-PVC
{v1,v2},
E’’’),
PVC
PVC
<G’’’=
(V’’
- {v,v2},PVC
E’’’),
PVC
PVC
k’’’ = k’’ - 2>k’’’ = k’’ - 2> k’’’ = k’’ - 2>
PVC = PVC
 {v,v1}
PVC
= PVC 
{v1,v2}
PVC
= PVC  {v,v2}
Algoritmo de Balasubramanian
(6)

Caso 3: caminho simples v, v1, v2.
Caminho gerado
em G’’
v
v1
v2
Árvore de Busca
<G’’=(V’’,E’’),k’’>
<G’’’=
(V’’ - {v1}, E’’’),
PVC
k’’’ = k’’ - 1>
PVC = PVC  {v1}
Algoritmo de Balasubramanian
(7)

Caso 4: caminho simples v, v1.
Caminho gerado
em G’’
v
v1
Árvore de Busca
<G’’=(V’’,E’’),k’’>
<G’’’=
(V’’ - {v}, E’’’),
PVC
k’’’ = k’’ - 1>
PVC = PVC  {v}
Algoritmo de Balasubramanian
(8)




Árvore ternária.
Interrompemos o crescimento da árvore
quando |PVC| = k.
Um grafo resultante vazio significa que PVC
é uma cobertura por vértices de tamanho
menor ou igual a k para G.
Se percorremos todos os nós da árvore,
podemos concluir que não existe a
cobertura por vértices desejada.
Algoritmo de Balasubramanian
(9)
grafo G
grafo G’’
G’
v10
v11 v2
v1
v1 v9
H = {v8}
k' =v23
v8
v3
v3
v12 v5
v5
v6
v4
v4
árvore de busca
k3>= 4
<G’,
<G’,k’>
{v8}
<G’’,k’’>
<G’’,k’’>
v6 PVC
PVC
<G’’,k’’>
<G’’,k’’>
PVC
1>
0>
<G’’,
<G’’,
1> 1>PVC
<G’’,
{v8,
{v8,
v4,
v4,
v6,
{v8,
v6}
v2}
v5,
{v8,v6}
v5, v7}
v7
v7
{v2, v4, v6, v8} é uma cobertura por vértices de
tamanho menor ou igual a 4 para o grafo G.
Algoritmo de Dehne et al (1)




Paraleliza o Teorema 1 de Balasubramanian et
al, seguindo o modelo CGM.
Paraleliza as duas fases do algoritmo FPT.
Resolve instâncias ainda maiores do que
aquelas resolvidas pelo seqüencial.
Redução ao núcleo do problema paralelo:

p processadores ordenam as arestas pelo identificador do
vértice em tempo O(1) para descobrir o grau dos vértices.
Algoritmo de Dehne et al (2)

Árvore limitada de busca paralelo:
<G’,k’>
log3 p
folhas
0 1
...
i
...
p-1