Cobertura de vértices (teoria dos grafos)

Na matemática, na disciplina de teoria dos grafos, uma cobertura de vertices de um grafo é um conjunto de vértices tal que cada aresta do grafo é incidente a pelo menos um vértice do conjunto. Ou seja, É um conjunto de vértices que contém pelo menos uma das pontas de cada aresta. Em outras palavras, uma cobertura de vértices é um conjunto V de vértices dotado da seguinte propriedade: toda aresta do grafo tem pelo menos uma ponta em V.

O problema de encontrar uma cobertura de vértices mínima é um clássico problema de otimização em ciência da computação e é um exemplo típico de um problema de otimização NP-difícil que tem um algoritmo de aproximação. Esta versão de problema de decisão, o problema da cobertura de vértices, foi um dos 21 problemas NP-completos de Karp e, portanto, um problema NP-completo clássico da teoria da complexidade computacional. Além disso, o problema de cobertura de vértices é tratável em parâmetros fixos e um problema central na teoria da complexidade parametrizada.

O problema da cobertura de vértices mínima pode ser formulado como um semi-integral programa linear cujo programa linear dual é o problema do acoplamento máximo.

Definição

Formalmente, uma cobertura de vértices de um grafo G é um conjunto C de vértices tal que cada aresta de G é incidente em pelo menos um vértice em C. O conjunto C é dito que cobre as arestas de G. A figura a seguir mostra exemplos de coberturas de vértice em dois grafos (o conjunto C está marcado em vermelho).

Uma cobertura de vértices mínima é uma cobertura de vértice de menor tamanho possível. O número de cobertura de vértice $\tau$ é o tamanho de uma cobertura de vértices mínima. A figura a seguir mostra exemplos de coberturas de vértices mínima, em dois grafos.

Exemplos

• O conjunto de todos os vértices é uma cobertura de vértices.
• As extremidades de qualquer acoplamento máximo formam uma cobertura de vértices.
• O grafo bipartido completo $K_{m,n}$ tem uma cobertura de vértices mínima de tamanho $\tau (K_{m,n})=\min(m,n)$.

Propriedades

• Um conjunto de vértices é uma cobertura de vértices, se e somente se seu complemento é um conjunto independente. Uma conseqüência imediata é:
• O número de vértices de um grafo é igual ao número de sua cobertura de vértices acrescido do tamanho do conjunto independente máximo (Gallai 1959).

Problema computacional

O problema da cobertura de vértices mínima é um problema de otimização que consiste em encontrar a menor cobertura de vértices em um grafo dado.

INSTÂNCIA: Grafo $G$

SAÍDA: Menor número $k$ da tal forma que $G$ tem uma cobertura de vértices de tamanho $k$.

Se o problema é enunciado como um problema de decisão, é chamado de o problema da cobertura de vértices:

INSTÂNCIA: Grafo $G$ e um inteiro positivo $k$.

QUESTÃO: Tem $G$ uma cobertura de vértices de tamanho máximo de $k$?

O problema da cobertura de vértices é um problema NP-completo: foi um dos Problemas NP-completos de Karp. Ele é frequentemente usado em teoria da complexidade computacional como ponto de partida para provas de pertinência a classe de problemas NP-difícil.

Formulação PLI

Suponha que cada vértice está associado um custo de $c(v)\geq 0$. O (ponderado) problema de cobertura vértices mínima pode ser formulado como o seguinte programa linear inteiro (PLI).

minimize	$\sum _{v\in V}c(v)x_{v}$			(minimiza o custo total)
sujeito a	$x_{u}+x_{v}\geq 1$	para todo $\{u,v\}\in E$		(cobre todas as arestas do grafo)
	$x_{v}\in \{0,1\}$	para todo $v\in V$.		(cada vértice está na cobertura de vértice ou não)

Este PLI pertence à classe mais geral de PLIs para problemas de cobertura. O gap de integralidade da PLI é $2$, pelo que o seu relaxamento dá um algoritmo de aproximação de fator de $2$ para o problema da cobertura mínima de vértices. Além disso, o relaxamento de programação linear do que a PLI é semi-integral, isto é, existe uma solução ótima para que cada entrada $x_{v}$ seja 0, 1/2, ou 1.

Avaliação exata

A decisão variante do problema de cobertura de vértices é NP-completo, o que significa que é pouco provável que exista um algoritmo eficiente para resolvê-lo exatamente. NP-completude pode ser comprovada pela redução de 3-satisfatibilidade, ou, como Karp fez, pela redução do problema de clique. A cobertura de vértices permanece NP-completo, mesmo em grafos cúbicos e mesmo em grafos planares de grau máximo de 3.

Para grafos bipartidos, a equivalência entre a cobertura de vértice e a máxima correspondência descrita pelo teorema de König permite que o problema da cobertura de vértices bipartida possa ser resolvido em tempo polinomial.

Tratabilidade por parâmetro-fixo

Um algoritmo de pesquisa de busca exaustiva pode resolver o problema em tempo 2^O(k)n^O(1). A cobertura de vértices é, portanto, tratável por parâmetros fixos, e se estamos interessados apenas em pequenos k, podemos resolver o problema em tempo polinomial. Uma técnica algorítmica que funciona aqui é chamada de algoritmo de pesquisa em árvores delimitadas, e sua idéia é repetidamente escolher algum vértice e recursivamente seu ramo, com dois casos em cada passo: coloque tanto o vértice atual ou todos os seus vizinhos na cobertura de vértices. Sob hipóteses razoáveis de complexidade teórica, a saber, a Hipótese do tempo exponencial, este tempo de funcionamento não pode ser melhorado para 2^o(k)n^O(1).

Contudo, para grafos planares, e, mais geralmente, para grafos excluindo-se alguns grafos fixos como menores, uma cobertura de vértices de tamanho k pode ser encontrada em tempo $2^{O({\sqrt {k}})}n^{O(1)}$, i.e., o problema é subexponencial tratável por parâmetros fixos. Este algoritmo é de novo ótimo, no sentido de que, sob a hipótese de tempo exponcencial, nenhum algoritmo pode resolver a cobertura de vértices em grafos planares em tempo $2^{o({\sqrt {k}})}n^{O(1)}$.

Avaliação aproximada

Pode-se encontrar uma aproximação de fator-2 por repetidamente, tomando-se ambas as extremidades de uma aresta em uma cobertura de vértices, e, em seguida, removendo-as do grafo. Dito de outro modo, encontramos um acoplamento máximo M com um algoritmo guloso e construimos uma cobertura de vértices C, que consiste em todos os terminais das arestas em M. Na figura a seguir, a correspondência máxima M está marcada com vermelho, e a cobertura de vértices C está marcada com azul.

O conjunto C construído desta forma é uma cobertura de vértices: suponhamos que uma aresta e não está coberta por C; então M ∪ {e} é uma correspondência e e ∉ M que é uma contradição com o pressuposto de que M é máxima. Além disso, se e = {u, v} ∈ M, então qualquer cobertura de vértices - incluindo uma cobertura de vértices ótima - deve conter u ou v (ou ambos); caso contrário, a aresta e não é coberta. Ou seja, uma cobertura ideal contém pelo menos uma extremidade de cada aresta emM; no total, o conjunto C é, no máximo, duas vezes maior que a cobertura de vértices ótima.

Este algoritmo simples foi descoberto independentemente por Fanica Gavril e Yannakakis Mihalis.

Mais técnicas envolvidas mostram que existem algoritmos de aproximação com um factor de aproximação um pouco melhor. Por exemplo, um algoritmo de aproximação com um factor de aproximação de $2-\Theta \left(1/{\sqrt {\log |V|}}\right)$ é conhecido.

Inaproximabilidade

Nenhum algoritmo de aproximação com fatores constantes melhor que o visto acima é conhecido. O problema da cobertura de vértices mínima é APX-completo, isto é, não pode ser aproximado arbitrariamente bem salvo se P = NP. Dinur e Safra provaram, utilizando técnicas do teorema PCP, que a cobertura de vértices mínima não pode ser aproximada dentro de um fator de 1,3606 para qualquer grau de vértice suficientemente grande, a menos que P = NP. Além disso, se a conjectura dos jogos únicos é verdadeira, então a cobertura de vértices mínima não pode ser aproximada dentro de um fator constante superior a 2.

Embora a encontrar a cobertura de vértices de tamanho mínimo seja equivalente a encontrar o conjunto independente de tamanho máximo, conforme descrito acima, os dois problemas não são equivalentes em uma forma de preservação da aproximação: O problema dos conjuntos independentes não tem aproximação a fator constante a menos que P = NP.

Cobertura de vértices em hipergrafos

Dada uma coleção de conjuntos, um conjunto que intersecta todos os conjuntos na coleção em pelo menos um elemento é chamado de hitting set, e um simples problema NP-completo é encontrar um hitting set de menor dimensão ou hitting set mínimo. Pelo mapeamento dos conjuntos da coleção em hiperarestas, isso pode ser entendido como uma generalização natural do problema da cobertura de vértices para hipergrafos, que é muitas vezes chamado apenas de cobertura de vértices para hipergrafos e, em um contexto mais combinatorial, transversal. As noções de hitting set e cobertura de conjuntos são equivalentes.

Formalmente, seja H = (V, E) um hipergrafo com um conjunto de vértices V e um conjunto de hiperarestas E. Então um conjunto S ⊆ V é chamado de hitting set de H se, para todas arestas e ∈ E, ele tem S ∩ e ≠ ∅. Os problemas computacionais hitting set mínimo e hitting set são definidos como no caso dos grafos. Note-se que nós recebemos de volta o caso das coberturas de vértice para grafos simples, se o tamanho máximo das hiperaretsas é 2.

Se esse tamanho é limitado a d, o problema de encontrar um hitting set d mínimo permite um algoritmo de d-aproximação. Assumindo a conjectura dos jogos originais, este é o melhor algoritmo de fator constante que é possível e caso contrário, existe a possibilidade de melhorar a aproximação com d- 1.

Tratabilidade de parâmetro-fixo

Para o problema do "hitting set", diferentes parametrizações fazem sentido. O problema do hitting set é W[2]-completo para o parâmetro OPT, ou seja, é provável que exista um algoritmo que executa em tempo f(OPT)n^O(1) onde OPT é a cardinalidade do menor hitting set. O problema hitting set é tratável por parâmetro fixo para o parâmetro OPT + d, onde d é o tamanho da maior aresta do hipergrafo. Mais especificamente, há um algoritmo hitting set que funciona em tempo d^OPTn^O(1).

Hitting set e a cobertura de vértices

O problema do "hitting set" é equivalente ao problema da cobertura de vértices: Um exemplo de cobertura de vértices pode ser visto como um grafo bipartido arbitrário, com conjuntos representados por vértices do lado esquerdo, o universo representado por vértices à direita, e as arestas que representam a inclusão de elementos nos conjuntos. A tarefa é, então, encontrar um subconjunto de cardinalidade mínima de vértices da esquerda que cobrem todos os vértices da direita. No problema "hitting set", o objetivo é cobrir os vértices da esquerda usando um subconjunto mínimo dos vértices da direita. A conversão de um problema para o outro é, portanto, alcançada trocando os dois conjuntos de vértices.

Aplicações

Um exemplo de uma aplicação prática envolvendo o problema do "hitting set" surge na detecção dinâmica eficiente de condições de corrida. Neste caso, cada vez que a memória global é escrita, a thread atual e um conjunto de bloqueios mantidos nesse segmento são armazenados. Sob detecção lockset-based, se mais tarde uma outra thread escreve neste local e não é uma corrida, deve ser porque ele tem pelo menos um bloqueio em comum com cada uma das escritas anteriores. Assim, o tamanho do hitting set representa o tamanho de conjunto mínimo de bloqueio para ser uma corrida livre. Isso é útil na eliminação de eventos de escrita redundantes, uma vez que grandes conjuntos de bloqueio são considerados improváveis na prática.

Ligações externas

• cobertura de vértices