# Conjunto dominante

Em teoria dos grafos, um conjunto dominante para um grafo G = (V, E) é um subconjunto D de V de tal modo que cada vértice que não está em D é adjacente a pelo menos um membro de D. O número de dominação γ(G) é o número de vértices em um menor conjunto dominante de G.
O problema do conjunto dominante refere-se a testar se γ(G) ≤ K para um dado grafo G e entrada K; É um clássico problema de decisão NP-completo em teoria de complexidade computacional (Garey & Johnson 1979). Portanto, acredita-se que não existe um algoritmo eficiente que encontre um menor conjunto dominante para um dado grafo.
As figuras (a)-(c) à direita mostram exemplos de árvores para conjuntos dominantes de um grafo. Em cada exemplo, cada vértice branco é adjacente a pelo menos um vértice vermelho, e dizemos que o vértice branco é dominado pelo vértice vermelho. O número de dominação do grafo é 2: Os exemplos (b)-(c) mostram que cada conjunto dominante possui dois vértices, e que pode ser verificado que não há conjunto dominante com apenas um vértice.

## História

Como Hedetniemi & Laskar (1990) mostra, o problema de dominação foi estudado a partir da década de 1950, mas a taxa de pesquisas aumentou significativamente em meados de 1970. Sua lista de bibliografias inclui mais de 300 artigos relacionados à dominação em grafos.

## Limites

Seja G um grafo com n ≥ 1 vertices e seja Δ o grau máximo do grafo. Os seguintes limitantes sobre γ(G) são conhecidos (Haynes, Hedetniemi & Slater 1998a, Chapter 2):
* Um vértice pode dominar a maioria dos outros Δ vértices; Portanto, γ(G) ≥ n/(1 + Δ).
* O conjunto de todos os vértices é um conjunto dominante sobre qualquer grafo; Portanto, γ(G) ≤ n.
* Se não há vértices isolados em G, então há dois conjuntos dominantes disjuntos em G; Veja domatic partition para detalhes. Portanto, em qualquer grafo sem vértices isolados é válido que γ(G) ≤ n/2.

## Dominação independente

Conjuntos dominantes estão intimamente relacionados a conjuntos independentes: um conjunto independente é também um conjunto dominante se, e somente se, é um conjunto independente máximo, de modo que qualquer conjunto independente máximo em um grafo é necessariamente também um conjunto dominante mínimo. Assim, o menor conjunto independente máximo também é o menor conjunto dominante independente. O número de dominação independente i(G) de um grafo G é o tamanho do menor conjunto independente (ou, de forma equivalente, o tamanho do menor conjunto independente máximo).
O conjunto dominante mínimo num grafo não será necessariamente independente, mas o tamanho do conjunto dominante mínimo é sempre inferior ou igual ao tamanho de um máximo conjunto independente mínimo, isto é, γ(G) ≤ i(G).
Há famílias de grafos em que um maior conjunto independente mínimo é um conjunto mínimo de dominação. Por exemplo, Allan & Laskar (1978) mostram que γ(G) = i(G) se G é um claw-free graph, grafo claw-free.
Um grafo G é dito um grafo de dominação-perfeita se γ(H) = i(H) em cada induced subgraph | subrafo induzido] de H em G. Uma vez que um subgrafo induzido de um grafo claw-free é também claw-free, segue-se que a cada grafo claw-free é também de dominação-perfeito (Faudree, Flandrin & Ryjáček 1997).

### Exemplos

As figuras (a) e (b) são conjuntos dominantes independentes, enquanto que a figura (c) ilustra um conjunto dominante que não é um conjunto independente.
Para qualquer grafo G, seu line graph, grafo de linha, L(G) é claw-free, e portanto, um maior conjunto independente mínimo é também um conjunto dominante mínimo em L(G). Um conjunto independente em L(G) corresponde a um acoplamento em G, e um conjunto dominante em L(G) corresponde a um conjunto de arestas dominantes em G. Portanto, um máximo acoplamento mínimo tem o mesmo tamanho que um conjunto de arestas dominantes.

## Algoritmo e complexidade computacional

Existe um par de L-reduções de tempo polinomial entre o problema do conjunto dominante mínimo e o problema de cobertura de um conjunto (Kann 1992, pp. 108–109). Essas reduções mostram que um algoritmo eficiente para o problema do conjunto dominante mínimo iria fornecer um algoritmo eficiente para o problema da conjunto de cobertura e vice-versa. Além disso, as reduções mantém o algoritmo de aproximação: para qualquer α, um algoritmo α-aproximação em tempo polinomial para conjuntos dominantes mínimos proporcionaria um algoritmo de α-aproximação em tempo polinomial para o problema do conjunto de cobertura e vice-versa. Ambos os problemas são, na verdade Log-APX-complete.
O problema do conjunto de cobertura é um problema NP-difícil — a versão de decisão do conjunto de cobertura foi um dos 21 problemas da lista de Karp, que foram mostrados NP-completos já em 1972. Daí as reduções para mostrar que o problema do conjunto dominante é NP-difícil também.
A aproximabilidade do conjunto de cobertura também é bem conhecida: um fator de aproximação logarítmica pode ser encontrado usando um algoritmo guloso simples, e encontrar um fator de aproximação sublogaritmico é NP-difícil. Mais especificamente, o algoritmo guloso fornece um fator 1 + log |V| de aproximação para um conjunto dominante mínimo, e Raz & Safra (1997) mostram que nenhum algoritmo pode alcançar um fator de aproximação melhor do que c log |V| para algum c > 0 a menos que P = NP.

### L-reduções

O seguinte par de reduções (Kann 1992, pp. 108–109) mostra que o problema do conjunto dominante mínimo e o problema de conjunto de cobertura são equivalentes sob L-reduções: dado um exemplo de um problema, podemos construir uma instância equivalente de outro problema.
Do conjunto dominante para o conjunto de cobertura Dado um grafo G = (V, E) com V = {1, 2, ..., n}, construir uma instância para conjunto de cobertura (S, U) da seguinte forma: o universo U é V, e é da família S = {S$_1$, S$_2$, ..., S$_n$} tal que S$_v$ consiste no vértice v e todos os vértices adjacentes a v em G.
Agora, se D é um conjunto dominante de G, então C = {S$_v$ : v ∈ D} é uma solução viável do problema de cobertura do conjunto, com |C| = |D|. Por outro lado, se C = {S$_v$ : v ∈ D} é uma solução viável do problema de conjunto de cobertura, então D é um conjunto dominante para G, com |D| = |C|.
Portanto, o tamanho mínimo de um conjunto dominante para G é igual ao tamanho mínimo da cobertura por conjunto para (S, U). Além do mais, existe um algoritmo simples que mapeia o conjunto dominante em uma cobertura por conjunto do mesmo tamanho, e vice versa. Em particular, a existência de uma α-aproximação eficiente para cobertura de conjuntos possibilita a existência de uma α-aproximação para o problema de minimizar o conjunto dominante.
       Por exemplo, dado o grafo G exibido à direita, nós construiremos uma instância de um conjunto de cobertura com o universo U = {1, 2, ..., 6} e os subconjuntos S$_1$ = {1, 2, 5}, S$_2$ = {1, 2, 3, 5}, S$_3$ = {2, 3, 4, 6}, S$_4$ = {3, 4}, S$_5$ = {1, 2, 5, 6}, and S$_6$ = {3, 5, 6}. Neste exemplo, D = {3, 5} é um conjunto dominante para G – esta corresponde à um conjunto de cobertura C = {S$_3$, S$_5$}. Por exemplo, o vértice 4 ∈ V é dominado pelo vértice 3 ∈ D, e o elemento 4 ∈ U está contido no conjunto S$_3$ ∈ C.
Do conjunto de cobertura para o conjunto dominante Seja (S, U) uma instância do problema do conjunto de cobertura com o universo U e a família de subconjuntos S = {S$_i$ : i ∈ I}; Supomos que U e o índice definido I são disjuntos. Construir um grafo G = (V, E) como segue: o conjunto de vértices é V = I ∪ U, existe uma aresta {i, j} ∈ E entre cada par i, j ∈ I, e também existe uma aresta {i, u} para cada i ∈ I e u ∈ S$_i$. Isto é, G é um split graph: I é um clique e U é um conjunto independente.
Agora, se C = {S$_i$ : i ∈ D} é uma solução viável do problema do conjunto de cobertura para um subconjunto D ⊆ I, então D é um conjunto dominante para G, com |D| = |C|: Em primeiro lugar, para cada u ∈ U existe um i ∈ D tal que u ∈ S$_i$, e por construção, u e i são adjacentes em G; Portanto, u é dominado por i. Em segundo lugar, uma vez que D deve ser não-vazia, cada i ∈ I é adjacente a um vértice no ponto D.
Por outro lado, seja D um conjunto dominante de G. Em seguida, é possível construir outro conjunto dominante X tal que |X| ≤ |D| e X ⊆ I: basta substituir cada u ∈ D ∩ U por um vizinho i ∈ I de u. Então, C = {S$_i$ : i ∈ X} é uma solução viável do problema de conjunto de com |C| = |X| ≤ |D|.
       A ilustração do lado direito mostra a construção de U = {a, b, c, d, e}, I = {1, 2, 3, 4}, S$_1$ = {a, b, c}, S$_2$ = {a, b}, S$_3$ = {b, c, d}, e S$_4$ = {c, d, e}.
       Neste exemplo, C = {S$_1$, S$_4$} é um conjunto de cobertura; isto corresponde ao conjunto dominante D = {1, 4}.
       D = {a, 3, 4} é um outro conjunto dominante para o grafo G. Dado D, podemos construir um conjunto dominante X = {1, 3, 4} que não é maior do que D e que é um subconjunto de I. O conjunto dominante Xcorresponde à cobertura conjunto C = {S$_1$, S$_3$, S$_4$}.

### Casos especiais

Se o grafo apresentar um grau máximo Δ, então o algoritmo de aproximação ganancioso encontra uma O(log Δ)-aproximação de um conjunto dominante mínimo. Para Δ fixo, está apto para o conjunto dominante para adesão APX; Na verdade, é APX-completo.
O problema admite um PTAS para casos especiais tais como grafos de unidade de disco e grafos planares (Crescenzi et al. 2000). Um conjunto dominante mínimo pode ser encontrado em tempo linear com grafos séries-paralelo (Takamizawa, Nishizeki & Saito 1982).

### Algoritmos exatos

Um conjunto dominante mínimo de um grafo de n-vértices pode ser encontrado em tempo O(2$^n$n) inspecionando todos os subconjuntos de vértices. Fomin, Grandoni & Kratsch (2009) mostram como encontrar um conjunto dominante mínimo no tempo O(1.5137$^n$) e espaço exponencial, e em tempo O(1.5264$^n$) e espaço polinomial. Um algoritmo rápido, utilizando tempo O(1.5048$^n$) foi encontrado por van Rooij, Nederlof & van Dijk (2009), que também mostram que o número de conjuntos de mínimos dominantes pode ser calculado neste momento. O número de conjuntos dominantes mínimo é no máximo 1.7159$^n$ e todos os tais conjuntos podem ser listadas em tempo O(1.7159$^n$) (Fomin et al. 2008) .

### Complexidade parametrizada

Encontrar um conjunto dominante de tamanho k desempenha um papel central na teoria da complexidade parametrizada. É o problema completo mais conhecido para a classe W[2] e usado em muitas reduções para mostrar a indecidibilidade de outros problemas. Em particular, o problema não é tratável com parâmetro fixo no sentido de que nenhum algoritmo com o funcionamento de tempo f(k)n$^{O(1)}$ para qualquer função f existe a menos que a hierarquia W reduz a FPT=W[2]. Por outro lado, se o grafo de entrada é plana, o problema permanece NP-Difícil, mas um algoritmo de parâmetro fixo é conhecido. Na verdade, o problema tem um kernel de tamanho linear em k (Alber, Fellows & Niedermeier 2004), e tempos de execução que são exponencial √k e cúbico em n pode ser obtido através da aplicação de programação dinâmica para uma branch decomposition do kernel (Fomin & Thilikos 2006).

## Variantes

A conjectura de Vizing relaciona o número de dominação de um produto cartesiano de grafos para o número de dominação de seus fatores.
Tem havido muito trabalho em conjuntos dominantes conexos. Se S é um conjunto dominante conexo, pode-se formar uma árvore geradora de G na qual S forma o conjunto de vértices não-folhas da árvore; reciprocamente, se T é qualquer árvore geradora em um gráfico com mais de dois vértices, os vértices não-folha de T formam um conjunto dominante conexo. Portanto, encontrar conjuntos dominantes mínimos ligados é equivalente a encontrar árvores geradoras com o maior número possível de folhas.
Um conjunto total dominante é um conjunto de vértices de tal forma que todos os vértices no grafo (incluindo os vértices no dominante ajustados entre si) têm um vizinho no conjunto dominante. A figura (c) acima mostra que o conjunto dominante que é conectado e um conjunto dominante total; Os exemplos nas figuras (a) e (b) não são.
Uma k-tupla de um conjunto dominante é um conjunto de vértices tal que cada vértice no grafo tem pelo menos k vizinhos do conjunto Uma (1+log n)-aproximação de um conjunto mínimo k-tupla dominante pode ser encontrada em tempo polinomial (Klasing & Laforest 2004). Da mesma forma, um k-conjunto dominante é um conjunto de vértices tal que cada vértice que não está no conjunto tem pelo menos k vizinhos do conjunto. Enquanto todo grafo admite um k-conjunto dominante, apenas grafos com grau mínimo k-1 admitem um conjunto dominante com k-tupla. No entanto, mesmo se o grafo admite um conjunto dominante com k-tupla, um conjunto dominante mínimo com k-tupla pode ser k vezes maior do que um conjunto mínimo dominante k para o mesmo grafo (Förster 2013); Uma (1.7+log Δ)-aproximação de um K-conjunto mínimo dominante pode ser encontrado em tempo polinomial.
Uma partição domática, domatic partition, é uma partição dos vértices em conjuntos disjuntos dominantes. O número domático é o tamanho máximo de uma partição domática.
Um conjunto dominante eterno é uma versão dinâmica de dominação em que um vértice v em um conjunto dominante D é escolhido e substituído por um vizinho u (u is not in D) tal que o D modificado é um conjunto dominante e este processo pode ser repetido sobre qualquer sequência infinita de opções de vértices v.

## Software para procura do conjunto dominante mínimo

| Name (alphabetically) | License | API language | Brief info |
| OpenOpt | BSD | Python | Utiliza grafos NetworkX, pode utilizar solucionadores gratuitos e comerciais, vértices incluídos / excluídos |