Análise de Algoritmos | Aulas | Dicionário | Índice

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.

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.

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{.}$

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

• No linha 3, $R$ é uma solução do problema. Na linha 4, não existe solução alguma pois todo superconjunto próprio de $R$ tem mais que $k$ vértices.
• Na linha 7, $S$ é uma cobertura e portanto uma solução. Na linha 8, não existe solução pois nenhum subconjunto de $S$ é cobertura.
• Na linha 9, temos $|R| < k < |S|$ e portanto $S \setm R$ não é vazio.
• No fim da linha 9, toda cobertura pertence a um de dois tipos: ou ela contém $v$ ou ela não contém $v\text{.}$
• No início da linha 10, as condições de aplicabilidade de Comb-Rec estão satisfeitas. No fim da linha 10, $X$ é uma cobertura pequena tal que $R\cup\conj{v} \subseteq X \subseteq S$ a menos que tal cobertura não exista, e nesse caso $X=V\text{.}$
• No início da linha 11, as condições de aplicabilidade de Comb-Rec estão satisfeitas. No fim da linha 11, $Y$ é uma cobertura pequena tal que $R \subseteq Y \subseteq S \setm \conj{v}$ a menos que tal cobertura não exista, caso em que $Y = V\text{.}$
• Na linha 12, se $G$ tem uma cobertura pequena então o menor de $X$ e $Y$ é uma cobertura pequena. Caso contrário, $X = Y = V\text{.}$

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–4 e 7–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!

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.

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{.}$

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{.}$

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{:}$

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

• Depois da linha 3, as instâncias $(G, k)$ e $(F, j)$ do problema são equivalentes no seguinte sentido: $G$ tem cobertura de tamanho $\leq k$ se e somente se $F$ tem cobertura de tamanho $\leq j\text{.}$
• Depois da linha 3, todo vértice de $F$ tem no máximo $k$ vizinhos. Portanto, se $F$ tem uma cobertura de tamanho $\leq j$ então \[ n(F) \leq j+j\cdot k. \] Assim, na linha 5, $G$ não tem cobertura de tamanho $\leq k\text{.}$
• No fim da linha 6, $R\cup X$ é uma cobertura de $G\text{.}$
• Na linha 8, $|R\cup X| \leq k\text{.}$ Na linha 9, $G$ não tem cobertura de tamanho $\leq k\text{.}$

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{.}$

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:

• Encontrar um circuito de comprimento $\geq k$ num grafo.
• Encontrar uma conjunto de $\leq k$ cliques que contenha todas as arestas do grafo.
• Encontrar uma árvore de Steiner com $\leq k$ terminais num grafo com pesos não negativos nas arestas. (Dado um conjunto $T\subseteq V$ de terminais, uma árvore de Steiner é uma subárvore de peso mínimo dentre as que incluem $T\text{.}$)
• Encontrar um conjunto de realimentação com $\leq k$ arcos num torneio. (Um torneio é um digrafo tal que, para cada par $(u,v)$ de vértices, exatamente um de $uv$ e $vu$ é um arco. Um conjunto de realimentação (= feedback arc set) é um conjunto de arcos que contém pelo menos um arco de cada ciclo do digrafo.)

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.