Problema de cobertura de pico

Na teoria dos grafos e na ciência da computação teórica , o problema da cobertura mínima por vértices (ou problema da transversal mínima , Vertex Cover em inglês) é um problema algorítmico clássico. Consiste, dado um gráfico, em encontrar um conjunto mínimo de vértices para cobrir todas as arestas.

O problema de decisão associado a este problema de otimização é NP-completo e é um dos 21 problemas NP-completos de Karp . É frequentemente usado na teoria da complexidade para provar que outros problemas mais complicados são NP-completos.

Cobertura de pico

Definição

Um vértice ou cobertura transversal de um grafo G é um conjunto C de vértices tal que cada aresta de G = ( V , E ) incide em pelo menos um vértice de C , ou seja, um subconjunto de vértices tal que para cada aresta de um tem ou . É que disse conjunto C abrange as bordas do G . A figura a seguir mostra exemplos de cobertura dos vértices de dois gráficos (o conjunto C é formado pelos vértices vermelhos). $S \ subseteq V$ $(u, v)$ $G$ $u \ in S$ $v \ in S$

Uma cobertura mínima de vértice é uma cobertura de tamanho mínimo de picos. A figura a seguir mostra exemplos de coberturas mínimas de vértices nos mesmos gráficos acima.

Propriedades combinatórias

Se um conjunto de vértices é transversal, seu complemento é um conjunto estável (ou independente ). Portanto, um gráfico com n vértices tem um transversal de tamanho k se e somente se ele tem um estábulo de tamanho n - k . Deduzimos imediatamente o seguinte resultado: $S$ ${\ bar S} = V \ setminus S$

Gallai 's teorema (1959) - De qualquer gráfico , α (G) + τ (L) = n. $G$

onde α (G) denota o tamanho de um estábulo máximo , τ (G) denota o tamanho de um transversal mínimo e . $n = | V |$

Problema de algoritmo

Descrição

O problema de otimização, chamado de problema de cobertura mínima do vértice, é o seguinte:

Entrada: um gráfico G Pergunta: qual é o menor inteiro k , de forma que haja uma cobertura de vértice de G de tamanho k ?

e o problema de decisão:

Entrada: um gráfico G e um inteiro k Pergunta: há uma cobertura por vértice de G de tamanho k ?

Programa linear

O programa de otimização linear inteiro associado é:

minimizar	${\ displaystyle \ sum _ {v \ in V} x_ {v}}$		(minimizar o custo total)
tal como	$x_ {u} + x_ {v} \ geq 1$	para tudo $\ {u, v \} \ in E$	(todas as bordas são cobertas)
	$x_ {v} \ in \ {0,1 \}$	para tudo . $v \ in V$	(cada vértice está no cobertor ou não)

A relaxação linear deste sistema é o dual da relaxação do programa de otimização para o problema de acoplamento máximo .

Complexidade

O problema de decisão associado a este problema de otimização é NP-completo e é um dos 21 problemas NP-completos de Karp . Sua dureza NP é demonstrada por uma redução do problema de clique a ele. O problema da cobertura de vértices é freqüentemente usado na teoria da complexidade para provar que outros problemas mais complicados são NP-completos.

O problema ainda é NP-completo se nos restringirmos a grafos cúbicos ou a grafos planares de grau no máximo 3. Em grafos bipartidos, ele é resolvido em tempo polinomial com um algoritmo de acoplamento máximo, pela aplicação do teorema de Kőnig .

Aproximação

O seguinte algoritmo de aproximação dá uma solução no máximo duas vezes maior que a ótima: calcule um acoplamento máximo e coloque cada par de vértices na solução.

Se assumirmos que P é diferente de NP , o problema não pode ser abordado com uma razão melhor do que 1,3606. Supondo a conjectura de jogos únicos , o problema não pode ser abordado com uma proporção melhor do que 2.

Notas e referências

O problema de tradução da cobertura por vértices está notavelmente presente no capítulo 14 da tradução de N. Schabanel da obra de referência: (en) Vijay Vazirani , algoritmos de aproximação , Springer Verlag , 2001 (então 2003), 380 p. ( ISBN 978-3-540-65367-7 ). Veja a planta do livro online .
Tibor Gallai, “ Über extreme Punkt- und Kantenmengen. », Ann. Univ. Sci. Budapeste, seita Eötvös Matemática. , vol. 2, 1959, p. 133-138.
Ola Svensson (escriba: Mateusz Golebiewski, Maciej Duleba), “ Tópicos em Ciência da Computação Teórica, Aula 5: Compreendendo e usando a Programação Linear ” , na Escola Politécnica Federal de Lausanne , março de 2015.
(em) Richard M. Karp , "reducibility Between Combinatorial Problems" em Raymond E. Miller e James W. Thatcher, Complexity of Computer Computations , Plenum,1972( ISBN 978-1-4684-2003-6 , DOI 10.1007 / 978-1-4684-2001-2_9 , ler online ) , p. 85-103
(em) Michael Garey e David S. Johnson , Computers and Intratability: A Guide to the Theory of NP-Completeness , WH Freeman,1979( ISBN 0-7167-1045-5 )
(in) Vijay Vazirani , algoritmos de aproximação , Springer Verlag , 2001 (e 2003), 380 p. ( ISBN 978-3-540-65367-7 ) , cap. 1.1.1 ("Um algoritmo de aproximação para cobertura de vértice de cardinalidade").
Irit Dinur e Shmuel Safra , “ Sobre a dureza da aproximação da cobertura de vértice mínima ”, Annals of Mathematics , 2005, p. 439-485
Subhash Khot e Oded Regev , “A cobertura do vértice pode ser difícil de aproximar dentro de 2-ε ”, Journal of Computer and System Sciences , vol. 74, n o 3,2008, p. 335-349 ( DOI 10.1016 / j.jcss.2007.06.019 )

links externos

(pt) Viggo Kann, " Minimum Vertex Cover " , sobre um compêndio de problemas de otimização NP ,20 de março de 2000(acessado em 6 de agosto de 2014 )
(pt) " PACE 2019 (Track Vertex Cover Exact) " , no desafio de algoritmos parametrizados e experimentos computacionais ,2019