algoritmos parametrizadoslehilton/mo829b/anotada-parte3.pdf · algoritmos parametrizados Árvores...
TRANSCRIPT
![Page 1: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/1.jpg)
Algoritmos Parametrizados
Árvores de busca limitadas
Lehilton Pedrosa
Segundo Semestre de 2016
Instituto de Computação – Unicamp
![Page 2: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/2.jpg)
Roteiro
1. Ramificação
2. Cobertura por vértices
3. Recorrências
4. Conjunto de vértices de retroalimentação
1
![Page 3: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/3.jpg)
Ramificação
![Page 4: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/4.jpg)
Árvore de busca
Ideia: backtracking
2
![Page 5: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/5.jpg)
Árvore de busca
Ideia: backtracking
• Fazer uma sequência de decisões
2
![Page 6: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/6.jpg)
Árvore de busca
Ideia: backtracking
• Fazer uma sequência de decisões
• Em cada decisão, obter um subproblema
2
![Page 7: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/7.jpg)
Árvore de busca
Ideia: backtracking
• Fazer uma sequência de decisões
• Em cada decisão, obter um subproblema
• Uma folha representa uma solução
2
![Page 8: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/8.jpg)
Árvore de busca
Ideia: backtracking
• Fazer uma sequência de decisões
• Em cada decisão, obter um subproblema
• Uma folha representa uma solução (ou a inexistênciadela)
2
![Page 9: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/9.jpg)
Árvore de busca
3
![Page 10: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/10.jpg)
Árvore de busca
P
3
![Page 11: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/11.jpg)
Árvore de busca
P
Decisão A?
3
![Page 12: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/12.jpg)
Árvore de busca
a1
P
P | a1
Decisão A?
3
![Page 13: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/13.jpg)
Árvore de busca
a2 a1
P
P | a1 P | a2
Decisão A?
3
![Page 14: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/14.jpg)
Árvore de busca
al a2 a1
P
P | a1 P | a2 P | al
Decisão A?
3
![Page 15: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/15.jpg)
Árvore de busca
al a2 a1
P
P | a1
Decisão B?
P | a2 P | al
Decisão A?
3
![Page 16: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/16.jpg)
Árvore de busca
al a2 a1
P
b1
P | a1
Decisão B?
P | a2 P | al
P | a1,b1
Decisão A?
3
![Page 17: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/17.jpg)
Árvore de busca
al a2 a1
P
b2 b1
P | a1
Decisão B?
P | a2 P | al
P | a1,b1 P | a1,b2
Decisão A?
3
![Page 18: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/18.jpg)
Árvore de busca
al a2 a1
P
b2 b1
P | a1
Decisão B?
P | a2 P | al
P | a1,b1 P | a1,b2
Decisão A?
Decisão C?
3
![Page 19: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/19.jpg)
Árvore de busca
al a2 a1
P
b2 b1
P | a1
Decisão B?
c1
P | a2 P | al
P | a1,b1 P | a1,b2
Decisão A?
P | a2,c1
Decisão C?
3
![Page 20: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/20.jpg)
Árvore de busca
al a2 a1
P
b2 b1
P | a1
Decisão B?
c2 c1
P | a2 P | al
P | a1,b1 P | a1,b2
Decisão A?
P | a2,c1 P | a2,c2
Decisão C?
3
![Page 21: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/21.jpg)
Árvores limitadas
Pergunta: Como usar árvores de busca para obter FPT?
4
![Page 22: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/22.jpg)
Árvores limitadas
Pergunta: Como usar árvores de busca para obter FPT?
• Tamanho da árvore é pequeno
4
![Page 23: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/23.jpg)
Árvores limitadas
Pergunta: Como usar árvores de busca para obter FPT?
• Tamanho da árvore é pequeno (função de k)
4
![Page 24: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/24.jpg)
Árvores limitadas
Pergunta: Como usar árvores de busca para obter FPT?
• Tamanho da árvore é pequeno (função de k)
• Tempo gasto em cada nó é polinomial
4
![Page 25: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/25.jpg)
Árvores limitadas
Pergunta: Como usar árvores de busca para obter FPT?
• Tamanho da árvore é pequeno (função de k)
• Tempo gasto em cada nó é polinomial
Vamos considerar:
• Uma instância I de um problema de minimização
4
![Page 26: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/26.jpg)
Árvores limitadas
Pergunta: Como usar árvores de busca para obter FPT?
• Tamanho da árvore é pequeno (função de k)
• Tempo gasto em cada nó é polinomial
Vamos considerar:
• Uma instância I de um problema de minimização
• Uma medida µ(I):
4
![Page 27: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/27.jpg)
Árvores limitadas
Pergunta: Como usar árvores de busca para obter FPT?
• Tamanho da árvore é pequeno (função de k)
• Tempo gasto em cada nó é polinomial
Vamos considerar:
• Uma instância I de um problema de minimização
• Uma medida µ(I):(queremos que µ(I) dependa só do parâmetro k)
4
![Page 28: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/28.jpg)
Ramificação
Em cada nó da árvores executamos uma ramificação
5
![Page 29: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/29.jpg)
Ramificação
Em cada nó da árvores executamos uma ramificação
Ramificação de I
Crie instâncias I1, ..., Iℓ tais que:
5
![Page 30: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/30.jpg)
Ramificação
Em cada nó da árvores executamos uma ramificação
Ramificação de I
Crie instâncias I1, ..., Iℓ tais que:
1. dada solução Si de Ii, existe solução hi(Si) de I
5
![Page 31: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/31.jpg)
Ramificação
Em cada nó da árvores executamos uma ramificação
Ramificação de I
Crie instâncias I1, ..., Iℓ tais que:
1. dada solução Si de Ii, existe solução hi(Si) de Ie {hi(S)}1≤i≤ℓ contém solução ótima;
5
![Page 32: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/32.jpg)
Ramificação
Em cada nó da árvores executamos uma ramificação
Ramificação de I
Crie instâncias I1, ..., Iℓ tais que:
1. dada solução Si de Ii, existe solução hi(Si) de Ie {hi(S)}1≤i≤ℓ contém solução ótima;
2. ℓ é uma função do parâmetro µ(I) somente;
5
![Page 33: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/33.jpg)
Ramificação
Em cada nó da árvores executamos uma ramificação
Ramificação de I
Crie instâncias I1, ..., Iℓ tais que:
1. dada solução Si de Ii, existe solução hi(Si) de Ie {hi(S)}1≤i≤ℓ contém solução ótima;
2. ℓ é uma função do parâmetro µ(I) somente;
3. existe c > 0 tal que µ(Ii) ≤ µ(I)− c para cada i.
5
![Page 34: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/34.jpg)
Limitando a altura
Um algoritmo de ramificação tem altura limitada:
6
![Page 35: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/35.jpg)
Limitando a altura
Um algoritmo de ramificação tem altura limitada:
• se µ(I) < 0, então instância é fácil;
6
![Page 36: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/36.jpg)
Limitando a altura
Um algoritmo de ramificação tem altura limitada:
• se µ(I) < 0, então instância é fácil;
• grau de ramificação ℓ de um nó é limitado;
6
![Page 37: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/37.jpg)
Limitando a altura
Um algoritmo de ramificação tem altura limitada:
• se µ(I) < 0, então instância é fácil;
• grau de ramificação ℓ de um nó é limitado;
• altura é limitada
6
![Page 38: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/38.jpg)
Árvores e FPT
Framework para FPT
7
![Page 39: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/39.jpg)
Árvores e FPT
Framework para FPT
Solução é um subconjunto de algum universo U:
7
![Page 40: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/40.jpg)
Árvores e FPT
Framework para FPT
Solução é um subconjunto de algum universo U:
1. Identificamos S ⊆ U pequeno
7
![Page 41: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/41.jpg)
Árvores e FPT
Framework para FPT
Solução é um subconjunto de algum universo U:
1. Identificamos S ⊆ U pequeno (em tempo polinomial)
7
![Page 42: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/42.jpg)
Árvores e FPT
Framework para FPT
Solução é um subconjunto de algum universo U:
1. Identificamos S ⊆ U pequeno (em tempo polinomial)
2. Adivinhamos qual elemento de S está em uma soluçãoótima
7
![Page 43: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/43.jpg)
Árvores e FPT
Framework para FPT
Solução é um subconjunto de algum universo U:
1. Identificamos S ⊆ U pequeno (em tempo polinomial)
2. Adivinhamos qual elemento de S está em uma soluçãoótima
3. Garantimos que a medida µ(I) diminui
7
![Page 44: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/44.jpg)
Árvores e FPT
Framework para FPT
Solução é um subconjunto de algum universo U:
1. Identificamos S ⊆ U pequeno (em tempo polinomial)
2. Adivinhamos qual elemento de S está em uma soluçãoótima
3. Garantimos que a medida µ(I) diminui(i.e., o “número” de decisões que faltam diminui)
7
![Page 45: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/45.jpg)
Cobertura por vértices
![Page 46: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/46.jpg)
Cobertura por vértices
Recapitulando:
8
![Page 47: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/47.jpg)
Cobertura por vértices
Recapitulando:
• Queremos encontrar X ⊆ V(G) tal que E[G− X] = ∅
8
![Page 48: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/48.jpg)
Cobertura por vértices
Recapitulando:
• Queremos encontrar X ⊆ V(G) tal que E[G− X] = ∅• Núcleo: 2k vértices em tempo O(n
√m)
8
![Page 49: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/49.jpg)
Cobertura por vértices
Recapitulando:
• Queremos encontrar X ⊆ V(G) tal que E[G− X] = ∅• Núcleo: 2k vértices em tempo O(n
√m) (usando técnicas
de LP)
8
![Page 50: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/50.jpg)
Cobertura por vértices
Recapitulando:
• Queremos encontrar X ⊆ V(G) tal que E[G− X] = ∅• Núcleo: 2k vértices em tempo O(n
√m) (usando técnicas
de LP)• Algoritmo exato: O(4kkO(1)) (para k fixo)
8
![Page 51: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/51.jpg)
Cobertura por vértices
Recapitulando:
• Queremos encontrar X ⊆ V(G) tal que E[G− X] = ∅• Núcleo: 2k vértices em tempo O(n
√m) (usando técnicas
de LP)• Algoritmo exato: O(4kkO(1)) (para k fixo)
Observação
Para v ∈ V(G):– ou v está na solução;
8
![Page 52: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/52.jpg)
Cobertura por vértices
Recapitulando:
• Queremos encontrar X ⊆ V(G) tal que E[G− X] = ∅• Núcleo: 2k vértices em tempo O(n
√m) (usando técnicas
de LP)• Algoritmo exato: O(4kkO(1)) (para k fixo)
Observação
Para v ∈ V(G):– ou v está na solução;
– ou N(v) está na solução.
8
![Page 53: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/53.jpg)
Cobertura por vértices
Recapitulando:
• Queremos encontrar X ⊆ V(G) tal que E[G− X] = ∅• Núcleo: 2k vértices em tempo O(n
√m) (usando técnicas
de LP)• Algoritmo exato: O(4kkO(1)) (para k fixo)
Observação
Para v ∈ V(G):– ou v está na solução;
– ou N(v) está na solução.
Observação
Se, para todo v ∈ V(G), d(v) ≤ 1, então Cobertura por vérticesé polinomial.
8
![Page 54: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/54.jpg)
Ramificando
Ramificação
• Escolha v ∈ V(G)
9
![Page 55: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/55.jpg)
Ramificando
Ramificação
• Escolha v ∈ V(G)• Temos S = {v} ∪ N(v) contém elemento de uma solução;
9
![Page 56: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/56.jpg)
Ramificando
Ramificação
• Escolha v ∈ V(G)• Temos S = {v} ∪ N(v) contém elemento de uma solução;
• Ramificamos em:
9
![Page 57: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/57.jpg)
Ramificando
Ramificação
• Escolha v ∈ V(G)• Temos S = {v} ∪ N(v) contém elemento de uma solução;
• Ramificamos em:1. Se v está na solução:
9
![Page 58: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/58.jpg)
Ramificando
Ramificação
• Escolha v ∈ V(G)• Temos S = {v} ∪ N(v) contém elemento de uma solução;
• Ramificamos em:1. Se v está na solução:
1.1 remova v de G;
9
![Page 59: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/59.jpg)
Ramificando
Ramificação
• Escolha v ∈ V(G)• Temos S = {v} ∪ N(v) contém elemento de uma solução;
• Ramificamos em:1. Se v está na solução:
1.1 remova v de G;1.2 faça k← k− 1
9
![Page 60: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/60.jpg)
Ramificando
Ramificação
• Escolha v ∈ V(G)• Temos S = {v} ∪ N(v) contém elemento de uma solução;
• Ramificamos em:1. Se v está na solução:
1.1 remova v de G;1.2 faça k← k− 1
2. Se N(v) está na solução:
9
![Page 61: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/61.jpg)
Ramificando
Ramificação
• Escolha v ∈ V(G)• Temos S = {v} ∪ N(v) contém elemento de uma solução;
• Ramificamos em:1. Se v está na solução:
1.1 remova v de G;1.2 faça k← k− 1
2. Se N(v) está na solução:2.1 remova N[v] de G;
9
![Page 62: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/62.jpg)
Ramificando
Ramificação
• Escolha v ∈ V(G)• Temos S = {v} ∪ N(v) contém elemento de uma solução;
• Ramificamos em:1. Se v está na solução:
1.1 remova v de G;1.2 faça k← k− 1
2. Se N(v) está na solução:2.1 remova N[v] de G;2.2 faça k← k− |N(v)|.
9
![Page 63: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/63.jpg)
Ramificando
Ramificação
• Escolha v ∈ V(G)• Temos S = {v} ∪ N(v) contém elemento de uma solução;
• Ramificamos em:1. Se v está na solução:
1.1 remova v de G;1.2 faça k← k− 1
2. Se N(v) está na solução:2.1 remova N[v] de G;2.2 faça k← k− |N(v)|.
9
![Page 64: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/64.jpg)
Ramificando
Ramificação
• Escolha v ∈ V(G) com grau máximo;
• Temos S = {v} ∪ N(v) contém elemento de uma solução;
• Ramificamos em:1. Se v está na solução:
1.1 remova v de G;1.2 faça k← k− 1
2. Se N(v) está na solução:2.1 remova N[v] de G;2.2 faça k← k− |N(v)|.
9
![Page 65: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/65.jpg)
Tempo de execução
10
![Page 66: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/66.jpg)
Tempo de execução
• cada nó da árvore gasta temo nO(1)
10
![Page 67: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/67.jpg)
Tempo de execução
• cada nó da árvore gasta temo nO(1)
• seja τ(k) o número de nós
10
![Page 68: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/68.jpg)
Tempo de execução
• cada nó da árvore gasta temo nO(1)
• seja τ(k) o número de nós
• TOTAL: τ(k)nO(1).
10
![Page 69: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/69.jpg)
Tempo de execução
• cada nó da árvore gasta temo nO(1)
• seja τ(k) o número de nós
• TOTAL: τ(k)nO(1).
Observação
Dada uma árvore de ramificação T com ℓ folhas, então o númerode nós de T é no máximo 2ℓ− 1.
10
![Page 70: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/70.jpg)
Tempo de execução
• cada nó da árvore gasta temo nO(1)
• seja τ(k) o número de nós
• TOTAL: τ(k)nO(1).
Observação
Dada uma árvore de ramificação T com ℓ folhas, então o númerode nós de T é no máximo 2ℓ− 1.
• Seja T(k) o número de folhas na árvore de ramificação daCobertura por vértices
10
![Page 71: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/71.jpg)
Tempo de execução
• cada nó da árvore gasta temo nO(1)
• seja τ(k) o número de nós
• TOTAL: τ(k)nO(1).
Observação
Dada uma árvore de ramificação T com ℓ folhas, então o númerode nós de T é no máximo 2ℓ− 1.
• Seja T(k) o número de folhas na árvore de ramificação daCobertura por vértices
T(i) =
10
![Page 72: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/72.jpg)
Tempo de execução
• cada nó da árvore gasta temo nO(1)
• seja τ(k) o número de nós
• TOTAL: τ(k)nO(1).
Observação
Dada uma árvore de ramificação T com ℓ folhas, então o númerode nós de T é no máximo 2ℓ− 1.
• Seja T(k) o número de folhas na árvore de ramificação daCobertura por vértices
T(i) =
{
10
![Page 73: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/73.jpg)
Tempo de execução
• cada nó da árvore gasta temo nO(1)
• seja τ(k) o número de nós
• TOTAL: τ(k)nO(1).
Observação
Dada uma árvore de ramificação T com ℓ folhas, então o númerode nós de T é no máximo 2ℓ− 1.
• Seja T(k) o número de folhas na árvore de ramificação daCobertura por vértices
T(i) =
{T(i− 1) + T(i− 2) se i ≥ 2;
10
![Page 74: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/74.jpg)
Tempo de execução
• cada nó da árvore gasta temo nO(1)
• seja τ(k) o número de nós
• TOTAL: τ(k)nO(1).
Observação
Dada uma árvore de ramificação T com ℓ folhas, então o númerode nós de T é no máximo 2ℓ− 1.
• Seja T(k) o número de folhas na árvore de ramificação daCobertura por vértices
T(i) =
{T(i− 1) + T(i− 2) se i ≥ 2;
1 caso contrário.
10
![Page 75: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/75.jpg)
Calculando
Lema
Para todo k ≥ 0, T(k) ≤ 1,6181k.
11
![Page 76: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/76.jpg)
![Page 77: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/77.jpg)
Obtendo a base da exponencial
12
![Page 78: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/78.jpg)
Obtendo a base da exponencial
Ideia: vamos tentar fazer T(k) ≤ cλk.
12
![Page 79: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/79.jpg)
Olhando
Observação: a base impacta muito no tempo de execução
13
![Page 80: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/80.jpg)
Olhando
Observação: a base impacta muito no tempo de execução
Conclusão: tentar melhorar ao máximo o passo deramificação
13
![Page 81: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/81.jpg)
Olhando
Observação: a base impacta muito no tempo de execução
Conclusão: tentar melhorar ao máximo o passo deramificação
Quando ramificamos:
• se v não é parte da solução, então diminuímos k em|N(v)| ≥ 2
13
![Page 82: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/82.jpg)
Olhando
Observação: a base impacta muito no tempo de execução
Conclusão: tentar melhorar ao máximo o passo deramificação
Quando ramificamos:
• se v não é parte da solução, então diminuímos k em|N(v)| ≥ 2;
• mas se |N(v)| > 2?
13
![Page 83: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/83.jpg)
Olhando
Observação: a base impacta muito no tempo de execução
Conclusão: tentar melhorar ao máximo o passo deramificação
Quando ramificamos:
• se v não é parte da solução, então diminuímos k em|N(v)| ≥ 2;
• mas se |N(v)| > 2? a árvore é menor!
13
![Page 84: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/84.jpg)
Olhando
Observação: a base impacta muito no tempo de execução
Conclusão: tentar melhorar ao máximo o passo deramificação
Quando ramificamos:
• se v não é parte da solução, então diminuímos k em|N(v)| ≥ 2;
• mas se |N(v)| > 2? a árvore é menor!
Observação
Cobertura por vértices é polinomial quando d(v) ≤ 2 paratodo v ∈ V(G).
13
![Page 85: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/85.jpg)
Melhorando
Agora resolvemos um nó em tempo polinomial sempre que∆(G) ≤ 2:
14
![Page 86: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/86.jpg)
Melhorando
Agora resolvemos um nó em tempo polinomial sempre que∆(G) ≤ 2:
T(i) =
14
![Page 87: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/87.jpg)
Melhorando
Agora resolvemos um nó em tempo polinomial sempre que∆(G) ≤ 2:
T(i) =
14
![Page 88: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/88.jpg)
Melhorando
Agora resolvemos um nó em tempo polinomial sempre que∆(G) ≤ 2:
T(i) =
T(i− 1) + T(i− 3) se i ≥ 3;
14
![Page 89: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/89.jpg)
Melhorando
Agora resolvemos um nó em tempo polinomial sempre que∆(G) ≤ 2:
T(i) =
T(i− 1) + T(i− 3) se i ≥ 3;
1 caso contrário.
14
![Page 90: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/90.jpg)
Melhorando
Agora resolvemos um nó em tempo polinomial sempre que∆(G) ≤ 2:
T(i) =
T(i− 1) + T(i− 3) se i ≥ 3;
1 caso contrário.
Teorema
Cobertura por vértices pode ser resolvida em tempoO(n
√m+ 1.4656 kO(1)).
14
![Page 91: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/91.jpg)
Recorrências
![Page 92: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/92.jpg)
Limitando árvores de busca por recorrência
Pergunta: Como limitar o tamanho da árvore de busca?
15
![Page 93: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/93.jpg)
Limitando árvores de busca por recorrência
Pergunta: Como limitar o tamanho da árvore de busca?
• representamos o tamanho como uma função T de k
15
![Page 94: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/94.jpg)
Limitando árvores de busca por recorrência
Pergunta: Como limitar o tamanho da árvore de busca?
• representamos o tamanho como uma função T de k
• obtemos uma recorrência
15
![Page 95: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/95.jpg)
Limitando árvores de busca por recorrência
Pergunta: Como limitar o tamanho da árvore de busca?
• representamos o tamanho como uma função T de k
• obtemos uma recorrência
• resolvemos a recorrências
15
![Page 96: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/96.jpg)
Limitando árvores de busca por recorrência
Pergunta: Como limitar o tamanho da árvore de busca?
• representamos o tamanho como uma função T de k
• obtemos uma recorrência
• resolvemos a recorrências
Vetor de ramificaçãoSuponha que:
15
![Page 97: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/97.jpg)
Limitando árvores de busca por recorrência
Pergunta: Como limitar o tamanho da árvore de busca?
• representamos o tamanho como uma função T de k
• obtemos uma recorrência
• resolvemos a recorrências
Vetor de ramificaçãoSuponha que:
• cada nó da arvore tem p subproblemas;
15
![Page 98: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/98.jpg)
Limitando árvores de busca por recorrência
Pergunta: Como limitar o tamanho da árvore de busca?
• representamos o tamanho como uma função T de k
• obtemos uma recorrência
• resolvemos a recorrências
Vetor de ramificaçãoSuponha que:
• cada nó da arvore tem p subproblemas;
• os parâmetros de cada subproblema são k−d1, k− 2, . . . , k−p.
15
![Page 99: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/99.jpg)
Limitando árvores de busca por recorrência
Pergunta: Como limitar o tamanho da árvore de busca?
• representamos o tamanho como uma função T de k
• obtemos uma recorrência
• resolvemos a recorrências
Vetor de ramificaçãoSuponha que:
• cada nó da arvore tem p subproblemas;
• os parâmetros de cada subproblema são k−d1, k− 2, . . . , k−p.
Então o vetor (d1,d2, . . . ,dp) é chamado vetor de ramificação.
15
![Page 100: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/100.jpg)
Recorrência geral
• cada nó tem um número constante p de ramos
16
![Page 101: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/101.jpg)
Recorrência geral
• cada nó tem um número constante p de ramos
• para parâmetro k ≤ p, presumimos que a instância é fácil(polinomial)
16
![Page 102: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/102.jpg)
Recorrência geral
• cada nó tem um número constante p de ramos
• para parâmetro k ≤ p, presumimos que a instância é fácil(polinomial)
Recorrência associada a (d1,d2, . . . ,dp):
16
![Page 103: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/103.jpg)
Recorrência geral
• cada nó tem um número constante p de ramos
• para parâmetro k ≤ p, presumimos que a instância é fácil(polinomial)
Recorrência associada a (d1,d2, . . . ,dp):
T(k) =
16
![Page 104: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/104.jpg)
Recorrência geral
• cada nó tem um número constante p de ramos
• para parâmetro k ≤ p, presumimos que a instância é fácil(polinomial)
Recorrência associada a (d1,d2, . . . ,dp):
T(k) =
16
![Page 105: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/105.jpg)
Recorrência geral
• cada nó tem um número constante p de ramos
• para parâmetro k ≤ p, presumimos que a instância é fácil(polinomial)
Recorrência associada a (d1,d2, . . . ,dp):
T(k) =
T(k− d1) + T(k− d2) + · · ·+ (k− dp) se k ≥ p;
16
![Page 106: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/106.jpg)
Recorrência geral
• cada nó tem um número constante p de ramos
• para parâmetro k ≤ p, presumimos que a instância é fácil(polinomial)
Recorrência associada a (d1,d2, . . . ,dp):
T(k) =
T(k− d1) + T(k− d2) + · · ·+ (k− dp) se k ≥ p;
1 caso contrário.
16
![Page 107: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/107.jpg)
Resolvendo a recorrência
• Usamos indução
17
![Page 108: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/108.jpg)
Resolvendo a recorrência
• Usamos indução
• Tentamos uma solução do tipo T(k) ≤ c · λk
17
![Page 109: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/109.jpg)
Resolvendo a recorrência
• Usamos indução
• Tentamos uma solução do tipo T(k) ≤ c · λk
Obtemos:λd ≥ λd−d1 + λd−d2 + · · ·+ λd−dp ,
onde d = max{d1, . . . ,dp}.
17
![Page 110: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/110.jpg)
Resolvendo a recorrência
• Usamos indução
• Tentamos uma solução do tipo T(k) ≤ c · λk
Obtemos:λd ≥ λd−d1 + λd−d2 + · · ·+ λd−dp ,
onde d = max{d1, . . . ,dp}.Reescrevemos como:
λd − λd−d1 − λd−d2 − · · ·− λd−dp ≥ 0
17
![Page 111: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/111.jpg)
Resolvendo a recorrência
• Usamos indução
• Tentamos uma solução do tipo T(k) ≤ c · λk
Obtemos:λd ≥ λd−d1 + λd−d2 + · · ·+ λd−dp ,
onde d = max{d1, . . . ,dp}.Reescrevemos como:
P(λ) := λd − λd−d1 − λd−d2 − · · ·− λd−dp ≥ 0
P(λ) é o vetor característico de T.
17
![Page 112: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/112.jpg)
Calculando
Seja λ0 solução de P(λ) = 0:
• P(λ) < 0 para 0 < λ < λ0;
• P(λ) > 0 para λ > λ0.
18
![Page 113: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/113.jpg)
Calculando
Seja λ0 solução de P(λ) = 0:
• P(λ) < 0 para 0 < λ < λ0;
• P(λ) > 0 para λ > λ0.
Obtemos T(k) ≤ O(λk0)
18
![Page 114: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/114.jpg)
Conjunto de vértices deretroalimentação
![Page 115: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/115.jpg)
Conjunto de vértices de retroalimentação mínimo
Conjunto de vértices de retroalimentação mínimo
Seja G um grafo. Um subconjunto de vértices X ⊆ V(G) échamado de conjunto de retroalimentação de G se G− X éacíclico.
Decidir: existe conjunto de realimentação com no máximo kvértices?
19
![Page 116: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/116.jpg)
Reduções simples
Consideramos o problema com multigrafos
20
![Page 117: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/117.jpg)
Reduções simples
Consideramos o problema com multigrafos, i.e.:
• podem existir laços
• podem existir arestas múltiplas
20
![Page 118: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/118.jpg)
Reduções simples
Consideramos o problema com multigrafos, i.e.:
• podem existir laços
• podem existir arestas múltiplas
Redução FVS.1: Se houver laça em v, remova v e diminua k.
20
![Page 119: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/119.jpg)
Reduções simples
Consideramos o problema com multigrafos, i.e.:
• podem existir laços
• podem existir arestas múltiplas
Redução FVS.1: Se houver laça em v, remova v e diminua k.
Redução FVS.2: Se houver t > 2 cópias de uma aresta, remova t− 2
cópias.
20
![Page 120: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/120.jpg)
Reduções simples
Consideramos o problema com multigrafos, i.e.:
• podem existir laços
• podem existir arestas múltiplas
Redução FVS.1: Se houver laça em v, remova v e diminua k.
Redução FVS.2: Se houver t > 2 cópias de uma aresta, remova t− 2
cópias.
Redução FVS.3: Se um vértice v tem grau d(v) ≤ 1, remova v.
20
![Page 121: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/121.jpg)
Instância simplificada
Redução FVS.4: Se FVS.1 não se aplica e v tem grau d(v) = 2:
21
![Page 122: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/122.jpg)
Instância simplificada
Redução FVS.4: Se FVS.1 não se aplica e v tem grau d(v) = 2:
• adicione uma aresta entre os vértices N(v);
21
![Page 123: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/123.jpg)
Instância simplificada
Redução FVS.4: Se FVS.1 não se aplica e v tem grau d(v) = 2:
• adicione uma aresta entre os vértices N(v);
• remova v.
21
![Page 124: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/124.jpg)
Instância simplificada
Redução FVS.4: Se FVS.1 não se aplica e v tem grau d(v) = 2:
• adicione uma aresta entre os vértices N(v);
• remova v.
Após as reduções, podemos obter uma instância trivial.
21
![Page 125: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/125.jpg)
Instância simplificada
Redução FVS.4: Se FVS.1 não se aplica e v tem grau d(v) = 2:
• adicione uma aresta entre os vértices N(v);
• remova v.
Após as reduções, podemos obter uma instância trivial.
Redução FVS.5: Se k < 0, devolva não.
21
![Page 126: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/126.jpg)
Instância simplificada
Redução FVS.4: Se FVS.1 não se aplica e v tem grau d(v) = 2:
• adicione uma aresta entre os vértices N(v);
• remova v.
Após as reduções, podemos obter uma instância trivial.
Redução FVS.5: Se k < 0, devolva não.
Propriedades
Após executar exaustivamente as reduções, obtemos G
21
![Page 127: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/127.jpg)
Instância simplificada
Redução FVS.4: Se FVS.1 não se aplica e v tem grau d(v) = 2:
• adicione uma aresta entre os vértices N(v);
• remova v.
Após as reduções, podemos obter uma instância trivial.
Redução FVS.5: Se k < 0, devolva não.
Propriedades
Após executar exaustivamente as reduções, obtemos G
1. sem laços;
21
![Page 128: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/128.jpg)
Instância simplificada
Redução FVS.4: Se FVS.1 não se aplica e v tem grau d(v) = 2:
• adicione uma aresta entre os vértices N(v);
• remova v.
Após as reduções, podemos obter uma instância trivial.
Redução FVS.5: Se k < 0, devolva não.
Propriedades
Após executar exaustivamente as reduções, obtemos G
1. sem laços;
2. somente com arestas simples ou duplas; e
21
![Page 129: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/129.jpg)
Instância simplificada
Redução FVS.4: Se FVS.1 não se aplica e v tem grau d(v) = 2:
• adicione uma aresta entre os vértices N(v);
• remova v.
Após as reduções, podemos obter uma instância trivial.
Redução FVS.5: Se k < 0, devolva não.
Propriedades
Após executar exaustivamente as reduções, obtemos G
1. sem laços;
2. somente com arestas simples ou duplas; e
3. com grau mínimo 3.
21
![Page 130: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/130.jpg)
![Page 131: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/131.jpg)
Vértices pesados
• Considere uma ordenação (v1, v2, . . . , vn) de V(G) tal que:
d(v1) ≥ d(v2) ≥ · · · ≥ d(vn).
22
![Page 132: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/132.jpg)
Vértices pesados
• Considere uma ordenação (v1, v2, . . . , vn) de V(G) tal que:
d(v1) ≥ d(v2) ≥ · · · ≥ d(vn).
• Defina V3 = {v1, . . . , v3k}.
22
![Page 133: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/133.jpg)
Vértices pesados
• Considere uma ordenação (v1, v2, . . . , vn) de V(G) tal que:
d(v1) ≥ d(v2) ≥ · · · ≥ d(vn).
• Defina V3 = {v1, . . . , v3k}.
Lema
Seja G um grafo tal que d(v) ≥ 3 para todo v ∈ V(G). Todoconjunto de retroalimentação de G com tamanho até k tempelo menos um vértice de V3k.
22
![Page 134: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/134.jpg)
![Page 135: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/135.jpg)
![Page 136: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/136.jpg)
![Page 137: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/137.jpg)
FPT para Conjunto de retroalimentação
Teorema
Existe um algoritmo para o Conjunto de vértices deretroalimentação que executa em tempo (3k)k · nO(1).
23
![Page 138: Algoritmos Parametrizadoslehilton/mo829b/anotada-parte3.pdf · Algoritmos Parametrizados Árvores de busca limitadas Lehilton Pedrosa Segundo Semestre de 2016 Instituto de Computação](https://reader034.vdocumento.com/reader034/viewer/2022042915/5f51730427235e330d469f1a/html5/thumbnails/138.jpg)