algoritmos parametrizadoslehilton/mo829b/anotada-parte3.pdf · algoritmos parametrizados Árvores...

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