Algoritmos Parametrizados
Árvores de busca limitadas
Lehilton Pedrosa
Segundo Semestre de 2016
Instituto de Computação – Unicamp
Roteiro
1. Ramificação
2. Cobertura por vértices
3. Recorrências
4. Conjunto de vértices de retroalimentação
1
Ramificação
Árvore de busca
Ideia: backtracking
2
Árvore de busca
Ideia: backtracking
• Fazer uma sequência de decisões
2
Árvore de busca
Ideia: backtracking
• Fazer uma sequência de decisões
• Em cada decisão, obter um subproblema
2
Á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
Á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
Árvore de busca
3
Árvore de busca
P
3
Árvore de busca
P
Decisão A?
3
Árvore de busca
a1
P
P | a1
Decisão A?
3
Árvore de busca
a2 a1
P
P | a1 P | a2
Decisão A?
3
Árvore de busca
al a2 a1
P
P | a1 P | a2 P | al
Decisão A?
3
Árvore de busca
al a2 a1
P
P | a1
Decisão B?
P | a2 P | al
Decisão A?
3
Árvore de busca
al a2 a1
P
b1
P | a1
Decisão B?
P | a2 P | al
P | a1,b1
Decisão A?
3
Á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
Á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
Á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
Á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
Árvores limitadas
Pergunta: Como usar árvores de busca para obter FPT?
4
Árvores limitadas
Pergunta: Como usar árvores de busca para obter FPT?
• Tamanho da árvore é pequeno
4
Árvores limitadas
Pergunta: Como usar árvores de busca para obter FPT?
• Tamanho da árvore é pequeno (função de k)
4
Á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
Á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
Á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
Á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
Ramificação
Em cada nó da árvores executamos uma ramificação
5
Ramificação
Em cada nó da árvores executamos uma ramificação
Ramificação de I
Crie instâncias I1, ..., Iℓ tais que:
5
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
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
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
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
Limitando a altura
Um algoritmo de ramificação tem altura limitada:
6
Limitando a altura
Um algoritmo de ramificação tem altura limitada:
• se µ(I) < 0, então instância é fácil;
6
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
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
Árvores e FPT
Framework para FPT
7
Árvores e FPT
Framework para FPT
Solução é um subconjunto de algum universo U:
7
Árvores e FPT
Framework para FPT
Solução é um subconjunto de algum universo U:
1. Identificamos S ⊆ U pequeno
7
Árvores e FPT
Framework para FPT
Solução é um subconjunto de algum universo U:
1. Identificamos S ⊆ U pequeno (em tempo polinomial)
7
Á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
Á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
Á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
Cobertura por vértices
Cobertura por vértices
Recapitulando:
8
Cobertura por vértices
Recapitulando:
• Queremos encontrar X ⊆ V(G) tal que E[G− X] = ∅
8
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
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
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
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
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
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
Ramificando
Ramificação
• Escolha v ∈ V(G)
9
Ramificando
Ramificação
• Escolha v ∈ V(G)• Temos S = {v} ∪ N(v) contém elemento de uma solução;
9
Ramificando
Ramificação
• Escolha v ∈ V(G)• Temos S = {v} ∪ N(v) contém elemento de uma solução;
• Ramificamos em:
9
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
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
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
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
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
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
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
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
Tempo de execução
10
Tempo de execução
• cada nó da árvore gasta temo nO(1)
10
Tempo de execução
• cada nó da árvore gasta temo nO(1)
• seja τ(k) o número de nós
10
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
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
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
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
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
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
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
Calculando
Lema
Para todo k ≥ 0, T(k) ≤ 1,6181k.
11
Obtendo a base da exponencial
12
Obtendo a base da exponencial
Ideia: vamos tentar fazer T(k) ≤ cλk.
12
Olhando
Observação: a base impacta muito no tempo de execução
13
Olhando
Observação: a base impacta muito no tempo de execução
Conclusão: tentar melhorar ao máximo o passo deramificação
13
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
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
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
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
Melhorando
Agora resolvemos um nó em tempo polinomial sempre que∆(G) ≤ 2:
14
Melhorando
Agora resolvemos um nó em tempo polinomial sempre que∆(G) ≤ 2:
T(i) =
14
Melhorando
Agora resolvemos um nó em tempo polinomial sempre que∆(G) ≤ 2:
T(i) =
14
Melhorando
Agora resolvemos um nó em tempo polinomial sempre que∆(G) ≤ 2:
T(i) =
T(i− 1) + T(i− 3) se i ≥ 3;
14
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
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
Recorrências
Limitando árvores de busca por recorrência
Pergunta: Como limitar o tamanho da árvore de busca?
15
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
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
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
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
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
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
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
Recorrência geral
• cada nó tem um número constante p de ramos
16
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
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
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
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
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
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
Resolvendo a recorrência
• Usamos indução
17
Resolvendo a recorrência
• Usamos indução
• Tentamos uma solução do tipo T(k) ≤ c · λk
17
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
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
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
Calculando
Seja λ0 solução de P(λ) = 0:
• P(λ) < 0 para 0 < λ < λ0;
• P(λ) > 0 para λ > λ0.
18
Calculando
Seja λ0 solução de P(λ) = 0:
• P(λ) < 0 para 0 < λ < λ0;
• P(λ) > 0 para λ > λ0.
Obtemos T(k) ≤ O(λk0)
18
Conjunto de vértices deretroalimentação
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
Reduções simples
Consideramos o problema com multigrafos
20
Reduções simples
Consideramos o problema com multigrafos, i.e.:
• podem existir laços
• podem existir arestas múltiplas
20
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
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
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
Instância simplificada
Redução FVS.4: Se FVS.1 não se aplica e v tem grau d(v) = 2:
21
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
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
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
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
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
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
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
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
Vértices pesados
• Considere uma ordenação (v1, v2, . . . , vn) de V(G) tal que:
d(v1) ≥ d(v2) ≥ · · · ≥ d(vn).
22
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
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
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