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 dá uma solução aproximada
do problema.
O capítulo serve de introdução ao conceito de algoritmo de aproximação e à classe APX de problemas.
Dada a dificuldade de encontrar um algoritmo rápido para o problema da cobertura mínima, parece relevante procurar por um algoritmo rápido que produza uma cobertura próxima da mínima. Surpreendentemente, o seguinte algoritmo guloso faz isso. O algoritmo recebe um grafo $G$ e devolve uma cobertura $Y$ de $G$ que tem no máximo duas vezes mais vértices que uma cobertura mínima:
| 1Cobertura-Gulosa$\,(G)$ |
| 11 . $Y := \emptyset$ |
| 12 . $M := \emptyset$ |
| 13 . enquanto $E(G-Y) \neq \emptyset$ |
| 14 .ooo tome uma aresta $vw$ em $E(G-Y)$ |
| 15 .ooo $Y := Y\cup\conj{v, w}$ |
| 16 .ooo $M := M\cup\conj{vw}$ |
| 17 . devolva $Y$ |
É claro que $E(G-Y) = \emptyset$ na linha 3 se e somente se $Y$ é uma cobertura. Para entender o algoritmo é preciso considerar os invariantes do processo iterativo nas linhas 3 a 6. No início de cada iteração,
(O invariante 1 poderia ser enunciado assim: todo vértice de $G$ é ponta de no máximo uma aresta de $M$. Qualquer conjunto $M$ com essa propriedade é conhecido como emparelhamento.)
Na linha 7, o conjunto $Y$ é uma cobertura. Ademais, de acordo com os invariantes 2 e 3, se $X$ é uma cobertura mínima então \[ |Y| \ \leq \ 2\,|X|\,. \] Dizemos que $Y$ é uma 2-aproximação de uma cobertura mínima.
É natural perguntar se não é possível aperfeiçoar o algoritmo para obter uma 1.9-aproximação ou até, quem sabe, uma 1.5-aproximação.
Consumo de tempo. É fácil implementar o algoritmo Cobertura-Gulosa de modo que ele consuma $\Oh(mn)$ unidades de tempo, sendo $m$ o número de arestas e $n$ o número de vértices do grafo. Como $m < n^2\text{,}$ podemos dizer que o algoritmo consome $\Oh(n^3)$ unidades de tempo.
Suponha que $\mathbf{C}$ é uma coleção de conjuntos de vértices de um grafo $G\text{.}$ Um problema de minimização sobre $\mathbf{C}$ consiste em encontrar um elemento mínimo de $\mathbf{C}\text{.}$ Em outras palavras, o problema consiste em encontrar um elemento $X$ de $\mathbf{C}$ tal que \[ |X| \ \leq \ |C| \] para todo $C$ em $\mathbf{C}\text{.}$ (O problema da cobertura mínima, por exemplo, é um tal problema de minimização.) Um algoritmo de aproximação para um problema de minimização sobre $\mathbf{C}$ é um algoritmo polinomial em $n(G)$ que devolve um elemento $Y$ de $\mathbf{C}$ tal que \[ |Y| \ \leq \ c\cdot |X| \] sendo $c \geq 1$ uma constante e $X$ uma solução do problema de minimização. A constante $c$ é o fator de aproximação do algoritmo. (É claro que $c$ não depende de $G\text{.}$) O fator de aproximação do algoritmo Cobertura-Gulosa, por exemplo, é $2\text{.}$
A classe de problemas de minimização para os quais existem algoritmos de aproximação é conhecida como APX (= approximable). Alguns problemas admitem toda uma família de algoritmos de aproximação: para cada número racional $\varepsilon \geq 0\text{,}$ existe um algoritmo com fator de aproximação $1+\varepsilon\text{.}$ Os problemas desse tipo constituem a subclasse PTAS (= polinomial-time approximation scheme) de APX.
Definições análogas às que acabamos de apresentar valem para problemas de maximização. É claro que o fator de aproximação de um algoritmo para um problema de maximização deve ser $\leq 1$. Veja, por exemplo, o algoritmo de aproximação para o problema da mochila booleana no capítulo Mochila booleana aproximada.
A propósito, veja o livro Uma Introdução Sucinta a Algoritmos de Aproximação do XXIII Colóquio Brasileiro de Matemática. Veja também a versão corrigida do livro.