Coberturas pequenas e a classe FPT

 

For every polynomial algorithm you have,
I have an exponential algorithm that I would rather run
.

Alan Perlis

 

Uma cobertura (= vertex cover) de um grafo é um conjunto de vértices que contém pelo menos uma das pontas de cada aresta. O problema da cobertura mínima foi apresentado em outro capítulo. O presente capítulo trata de um problema aparentemente mais modesto: o da cobertura pequena.

O capítulo serve de introdução à classe FPT (fixed-parameter tractable) de problemas.

Coberturas pequenas

Em vista da dificuldade de calcular uma cobertura mínima de um grafo, parece relevante considerar o seguinte

Problema da cobertura pequena: Dado um grafo $G$ e um número natural $k\text{,}$ encontrar uma cobertura de $G$ que tenha $k$ vértices ou menos.

Diremos que uma cobertura com $k$ ou menos vértices é pequena. (Note que uma cobertura pequena não é necessariamente minimal.)  Se $n(G) \leq k$ então o conjunto $V(G)$ de todos os vértices de $G$ é uma solução do problema. Já uma instância do problema com $n > k$ pode não ter solução alguma.

Este capítulo examina uma sequência de algoritmos progressivamente mais rápidos para o problema da cobertura pequena. Os desempenhos dos sucessivos algoritmos são proporcionais a

$n^{k+2}$,   $2^k\,n^2$   e   $n^2 + 2^k\,k^4$

no pior caso. Os dois últimos algoritmos da sequência mostram que o problema da cobertura pequena pertence à classe FPT de problemas.

Exercícios 1

  1. Escreva um algoritmo muito simples para calcular uma cobertura pequena em um grafo $G$ que tem no máximo $k+1$ vértices.

Algoritmo das combinações

Nosso primeiro algoritmo para o problema da cobertura pequena é de força bruta: ele examina todos os subconjuntos de $V$ que têm exatamente $k$ elementos. O número de tais subconjuntos é o coeficiente binomial \[ \binomial{n}{k} := \frac{n!}{k!\,(n-k)!}. \] Por exemplo, se $k=3$ e $n=5\text{,}$ o algoritmo examina $10$ subconjuntos de $V\text{.}$ Se $k=10$ e $n=50\text{,}$ o algoritmo examina cerca de $10^{10}$ subconjuntos de $V\text{.}$

A ideia do algoritmo é simples: para cada vértice $v\text{,}$ encontre uma cobertura pequena dentre as que contêm $v\text{,}$ depois encontre uma cobertura pequena dentre as que não contêm $v\text{,}$ e finalmente devolva a menor das duas coberturas.

É importante organizar o algoritmo de modo que ele devolva algum conjunto de vértices mesmo quando o problema não tem solução. Nosso algoritmo devolverá $V$ nesse caso.

1Combinações$\,(G, k)$
11 . se $n < k$
12 .ooo então devolva $V$
13 . $X := \text{}$ Comb-Rec$\,(G, k, \emptyset, V)$
14 . devolva $X$

O subalgoritmo recursivo Comb-Rec recebe subconjuntos $R$ e $S$ de $V$ tais que $R \subseteq S$ e $|R| \leq k \leq |S|$ e devolve uma cobertura pequena $X$ tal que \[ R \subseteq X \subseteq S \] se uma tal cobertura existir. Senão, devolve a cobertura trivial $V\text{.}$

1Comb-Rec$\,(G, k, R, S)$
11 . se $|R| = k$
12 .ooo então se $E(G - R)=\emptyset$
13 .oooooo então então devolva $R$
14 .oooooo então senão devolva $V$
15 . se $|S| = k$
16 .ooo então se $E(G - S)=\emptyset$
17 .oooooo então então devolva $S$
18 .oooooo então senão devolva $V$
19 . tome qualquer vértice $v$ em $S \setm R$
10 . $X := \text{}$ Comb-Rec$\,(G, k, R\cup\conj{v}, S)$
11 . $Y := \text{}$ Comb-Rec$\,(G, k, R, S \setm \conj{v})$
12 . devolva $\min\,(X, Y)$

As seguintes observações levam à prova de que o subalgoritmo está correto:

Para melhor entender o subalgoritmo, considere a árvore de recursão que o subalgoritmo percorre ao ser executado. Trata-se de uma árvore binária cada um de cujos nós é rotulado pelos argumentos de uma invocação do subalgoritmo Comb-Rec. Cada nó $(R,S)$ tem filho esquerdo $(R\cup\conj{v},S)$ e filho direito $(R,S\setm\conj{v})\text{.}$ A raiz da árvore é $(\emptyset, V)$ e os nós em que $|R|=k$ ou $|S|=k$ são as folhas. O subalgoritmo percorre essa árvore em pré-ordem (ou seja, em ordem raiz-esquerda-direita) e usa uma pilha para armazenar os argumentos das invocações pendentes.

Consumo de espaço.  Quando Comb-Rec é invocada com argumentos $(G, R, S)\text{,}$ a pilha de recursão tem no máximo $1 + |S\setm R|$ elementos. Quando Comb-Rec é executado com argumentos $(G, k, \emptyset, V)\text{,}$ a pilha tem no máximo $n+1$ elementos.

Cada par $(R,S)$ da pilha ocupa espaço $\Oh(n)\text{.}$ Com isso, o espaço de trabalho usado por Combinações é $\Oh(n^2)\text{.}$

Consumo de tempo.  As operações que mais consomem tempo durante a execução do subalgoritmo Comb-Rec são os testes da forma se $E(G\,-\,?)=\emptyset$ (linhas 2 e 6). Para dar uma delimitação superior do número de tais testes, vamos ignorar a interrupção da execução do algoritmo nas linhas 3–47–8.

Seja $p(i,j)$ o número máximo de testes da forma se $E(G\,-\,?)=\emptyset$ quando $k- |R| = i$ e $|S|-k = j\text{.}$ Então \[ p(i, j) = \begin{array}{ll} 1 \quad \text{se $i=0$ ou $j=0$}\\ % p(i-1,j) + p(i,j-1) \quad \text{caso contrário.} \end{array} \]

A solução dessa recorrência é \[ p(i,j) = \binomial{i+j}{j}, \] uma vez que coeficientes binomiais satisfazem a identidade $\binomial{a}{b} = \binomial{a-1}{b}+\binomial{a-1}{b-1}\text{.}$

Durante a execução do algoritmo principal Combinações, o número máximo de testes da forma se $E(G\,-\,?)=\emptyset$ será \[ p(k,n-k) = \binomial{n}{k}\,. \] Como cada teste consome consome $\Oh(n^2)$ unidades de tempo, o algoritmo Combinações consome \[ \Oh(\binomial{n}{k}\:n^2) \] unidades de tempo.

Parâmetro fixo.  Como se sabe, $\frac{1}{k^k} n^k \leq \binomial{n}{k} \leq \frac{1}{k!} n^k\text{.}$ Assim, para cada valor fixo de $k$, o consumo de tempo do algoritmo Combinações é \[ \Oh(n^{k+2}). \] Em particular, o algoritmo é polinomial em $n$ quando $k$ é fixo.

Mas o grau do polinômio é elevado. Eu não usaria o algoritmo para procurar coberturas de tamanho $\leq 10$ num grafo com $20$ vértices, por exemplo!

Exercícios 2

  1. Prove que a solução da recorrência é $p(i,j) = \binomial{i+j}{j}\text{.}$
  2. Prove que a pilha de recursão de Comb-Rec tem no máximo $1 + |S\setm R|$ elementos.

Algoritmo da aresta

Nosso segundo algoritmo para o problema da cobertura pequena evita testar os candidatos a cobertura que obviamente não são coberturas minimais. O algoritmo tem por base a seguinte observação óbvia:

Para qualquer aresta $uv\text{,}$ toda cobertura de $G$ contém $u$ ou $v\text{.}$

A ideia do algoritmo é simples: para cada aresta $uv\text{,}$ encontre uma cobertura pequena dentre as que contêm $u\text{,}$ depois encontre uma cobertura pequena dentre as que contêm $v\text{,}$ e finalmente devolva a menor das duas coberturas. Diremos que esse é o algoritmo da aresta.

1Aresta$\,(G, k)$
11 . se $n < k$
12 .ooo então devolva $V$
13 . $X := \text{}$ Aresta-Rec$\,(G, k, \emptyset)$
14 . devolva $X$

O subalgoritmo recursivo Aresta-Rec recebe um subconjunto $R$ de $V$ tal que $|R|\leq k$ e devolve uma cobertura pequena $X$ de $G$ tal que \[ X\supseteq R \] ou, se uma tal cobertura não existe, devolve a cobertura trivial $V\text{.}$

1Aresta-Rec$\,(G, k, R)$
11 . se $E(G-R) = \emptyset$
12 .ooo então devolva $R$
13 . se $|R| = k$
14 .ooo então devolva $V$
15 . tome qualquer $uv$ em $E(G-R)$
16 . $X := \text{}$ Aresta-Rec$\,(G, k, R\cup\conj{u})$
17 . $Y := \text{}$ Aresta-Rec$\,(G, k, R\cup\conj{v})$
18 . devolva $\min(X, Y)$

Exemplo A.  Árvore de busca para o grafo que tem vértices $a,b,c,d,e$ e arestas $ab\text{,}$ $ac\text{,}$ $ad\text{,}$ $ae\text{,}$ $bc\text{,}$ $cd\text{,}$ $de\text{,}$ $eb\text{.}$ A árvore é produzida pela algoritmo Aresta-Rec com $k=4\text{.}$ Uma expressão como $abc$ representa o conjunto $\conj{a,b,c}\text{.}$ Nesse exemplo, todas as folhas da árvore são coberturas. Note que nem todos os conjuntos de $4$ vértices são gerados (e alguns são gerados mais de uma vez).

\[ \begin{array}{lllll} & & & & bcde \\ & & & bcd & \\ & & & & bcda \\ & & bc\qquad & & \\ & & & & bcae \\ & & & bca & \\ & & & & bcad \\ & b\qquad\qquad & & & \\ & & & & \\ & & & bad \\ & & & & \\ & & ba & \\ & & & & bace \\ & & & bac & \\ & & & & bacd \\ \emptyset\qquad\qquad\qquad\qquad & & & \\ & & & & \\ & & & ace \\ & & & & \\ & & ac & \\ & & & & acbe \\ & & & acb & \\ & & & & acbd \\ & a & & \\ & & & & \\ & & & abd \\ & & & & \\ & & ab & \\ & & & & abce \\ & & & abc & \\ & & & & abcd \end{array} \]

Consumo de tempo.  Seja $p(i)$ o número máximo de execuções de testes da forma se $E(G-R)=\emptyset$ ao longo da execução do subalgoritmo Aresta-Rec com argumentos $k$ e $R$ tais que $k-|R| = i\text{.}$ Observe que \[ p(i) \ = \ \begin{array}{ll} 1 \quad \text{se $i=0$}\\ 1+ 2\,p(i-1) \quad \text{em caso contrário.} \end{array} \]

Portanto, $p(i) = 2^{i+1}-1\text{.}$ Logo, o número de execuções de testes da forma se $E(G-R)=\emptyset$ ao longo da execução do algoritmo Aresta é \[ 2^{k+1}-1. \]

Esse número é confirmado pela seguinte análise informal. O algoritmo Aresta constrói, implicitamente, uma árvore de busca. Trata-se de uma árvore binária cujos nós são conjuntos de vértices. O filho esquerdo de cada nó $R$ é o nó $R\cup \conj{v}$ e o filho direito é o nó $R\cup\conj{u}\text{.}$ A raiz da árvore é $\emptyset$ e cada nó tem no máximo $k$ vértices. Se somarmos os números de nós em cada nível teremos no máximo $2^0 + 2^1 + \cdots + 2^k = 2^{k+1} - 1\text{.}$  Quando $k=10\text{,}$ por exemplo, o número de nós não passa de $2^{11}\cong 2\times 10^3\text{.}$ Quando $k=30\text{,}$ o número de nós não passa de $2^{31}\cong 2\times 10^{9}\text{.}$

O processamento de cada nó $R$ da árvore consiste em decidir se $R$ é uma cobertura, ou seja, se $E(G-R)=\emptyset\text{.}$ Cada um desses testes consome $\Oh(n^2)$ unidades de tempo. Portanto, o algoritmo Aresta consome \[ \Oh(2^k\,n^2) \] unidades de tempo.

Parâmetro fixo.  Se $k$ é fixo, o algoritmo Aresta é quadrático em $n\text{,}$ e portanto linear no tamanho do grafo.  (Mas é claro que a constante de proporcionalidade $2^k$ cresce muito rapidamente com $k\text{.}$)

Consumo de espaço.  O algoritmo Aresta consome espaço de trabalho para armazenar a pilha de recursão. Cada elemento da pilha pertence a um nível diferente da árvore de busca e assim a pilha tem no máximo $n$ elementos.

Os elementos da pilha de recursão são subconjuntos de $V\text{.}$ Portanto, cada elemento consome espaço $\Oh(n)\text{.}$ Assim, a quantidade total de espaço de trabalho é $\Oh(n^2)\text{.}$

Melhoramentos.  A ideia do algoritmo Aresta pode ser aperfeiçoada para produzir um algoritmo que consome tempo $\Oh(1.5^k\,n^2)$ e até um algoritmo que consome apenas $\Oh(m + 1.5^k\,n)\text{.}$

Exercícios 3

  1. ★ Para qualquer vértice $u$ de um grafo $G\text{,}$ seja $N_G(u)$ o conjunto dos vizinhos de $u\text{.}$ Verifique a seguinte observação: toda cobertura contém $u$ ou inclui $N_G(u)\text{.}$ Use essa observação para escrever um algoritmo que encontre uma cobertura pequena em tempo $\Oh(1.5^k\,n^2)\text{.}$

Algoritmo da núcleo

Nosso terceiro algoritmo para o problema da cobertura pequena envolve o conjunto, digamos $R\text{,}$ de todos os vértices que têm mais que $k$ vizinhos. O ponto de partida do algoritmo é a seguinte observação:

Toda cobertura pequena inclui o conjunto $R\text{.}$

Assim, para obter uma cobertura pequena em $G\text{,}$ basta acrescentar a $R$ uma cobertura suficientemente pequena do grafo $G - R$. Mais exatamente, basta resolver a instância $(G - R, k-|R|)$ do problema da cobertura pequena. Essa instância reduzida é o núcleo (= kernel) da instância original $(G,k)\text{.}$ Podemos dizer que o núcleo é a pedaço difícil da instância $(G,k)\text{.}$

Como os algoritmos anteriores, o algoritmo da redução ao núcleo devolve uma cobertura pequena se tal cobertura existe e devolve a cobertura trivial $V$ em caso contrário.  O pseudocódigo a seguir usa a notação $N_G(r)$ para designar o conjunto dos vizinhos de um vértice $r\text{:}$

1Núcleo$\,(G, k)$
11 . $R := \conj{ r\in V : |N_G(r)| > k}$
12 . $F := G-R$
13 . $j := k-|R|$
14 . se $n(F) > j+j\cdot k$
15 .ooo então devolva $V$
16 . $X := \text{}$ Aresta$\,(F, j)$
17 . se $|X| \leq j$
18 .ooo então devolva $R\cup X$
19 .ooo senão devolva $V$

As seguintes observações mostram que o algoritmo está correto:

Consumo de tempo.  O consumo de tempo do algoritmo Núcleo depende do número de vértices do grafo $F\text{,}$ e esse número depende apenas de $k\text{.}$ De fato, na linha 6 do algoritmo temos \[ n(F) \ \leq \ j + j\cdot k \ \leq \ k^2+k. \] Portanto, a execução do algoritmo Aresta na linha 6 consome tempo \[ \Oh(2^{j}\,{n(F)}^2) = \Oh(2^k (k^2+k)^2) = \Oh(2^k\,k^4)\:. \] Como o consumo de tempo da linha 1 e das demais linhas é $\Oh(n^2)\text{,}$ o consumo total do algoritmo Núcleo é \[ \Oh(n^2 + 2^k\,k^4). \]

O termo exponencial do consumo de tempo não envolve $n$ (como no algorimo Aresta), apenas $k\text{.}$ Assim, o algoritmo Núcleo pode ser útil para resolver instâncias do problema da cobertura pequena em que valor do parâmetro $k$ é modesto.

Melhoramentos.  Existem aperfeiçoamentos do algoritmo Núcleo que consomem tempo $\Oh(kn + 1.5^k k^2)$ e até mesmo $\Oh(kn + 1.3^k)\text{.}$  As diferenças entre $2^k\text{,}$ $1.5^k$ e $1.3^5$ não são desprezíveis. Por exemplo, $2^{30} \cong 10^9$ enquanto $1.5^{30} \cong 2\times 10^5$ e $1.3^{30} \cong 2.6\times 10^{3}\text{.}$

Exercícios 4

  1. Suponha que $|R| > k$ no fim da linha 1 do algoritmo Núcleo. Mostre que $n(F) > j+j\cdot k$ na linha 4.
  2. ★ Seja $R$ o conjunto dos vértices de um grafo $G$ que têm mais de $k$ vizinhos. Seja $X$ uma cobertura de $G\text{.}$ Prove que se $|X|\leq k$ então $X \supseteq R\text{.}$

A classe FPT de problemas

Inspirados pelos algoritmos deste capítulo, Fellows e outros pesquisadores propuseram a classe FPT de complexidade computacional. Um problema está na classe FPT (= fixed-parameter tractable) em relação a um parâmetro $k$ se, para cada $k$ é fixo, o problema está na classe P de complexidade. Mais precisamente, um problema está em FPT se existe uma função $\phi$ (possivelmente exponencial), uma constante $c\text{,}$ e um algoritmo que resolve qualquer instância do problema em tempo $\Oh(\phi(k)\,n^c)\text{,}$ sendo $n$ o tamanho da instância.

Por exemplo, o problema da cobertura pequena está em FPT porque admite um algoritmo que consome tempo $\Oh(2^k\,n^2)$. Muitos outros problemas estão em FPT. Eis alguns exemplos:

Muitos problemas difíceis não estão em FPT. Acredita-se, por exemplo, que o problema do conjunto independente grande não está em FPT.