frame|direita|Dominating sets (red vertices).
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 . 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 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 :
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, 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 .
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 . 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 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 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 = {S1, S2, ..., Sn} tal que Sv 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 = {Sv : v ∈ D} é uma solução viável do problema de cobertura do conjunto, com |C| = |D|. Por outro lado, se C = {Sv : 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.
right 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 S1 = {1, 2, 5}, S2 = {1, 2, 3, 5}, S3 = {2, 3, 4, 6}, S4 = {3, 4}, S5 = {1, 2, 5, 6}, and S6 = {3, 5, 6}. Neste exemplo, D = {3, 5} é um conjunto dominante para G – esta corresponde à um conjunto de cobertura C = {S3, S5}. Por exemplo, o vértice 4 ∈ V é dominado pelo vértice 3 ∈ D, e o elemento 4 ∈ U está contido no conjunto S3 ∈ 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 = {Si : 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 ∈ Si. Isto é, G é um split graph: I é um clique e U é um conjunto independente.
Agora, se C = {Si : 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 ∈ Si, 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 = {Si : i ∈ X} é uma solução viável do problema de conjunto de com |C| = |X| ≤ |D|.
right A ilustração do lado direito mostra a construção de U = {a, b, c, d, e}, I = {1, 2, 3, 4}, S1 = {a, b, c}, S2 = {a, b}, S3 = {b, c, d}, e S4 = {c, d, e}.
Neste exemplo, C = {S1, S4} é 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 = {S1, S3, S4}.
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 . Um conjunto dominante mínimo pode ser encontrado em tempo linear com grafos séries-paralelo .
Algoritmos exatos Um conjunto dominante mínimo de um grafo de n-vértices pode ser encontrado em tempo O(2nn) inspecionando todos os subconjuntos de vértices. mostram como encontrar um conjunto dominante mínimo no tempo O(1.5137n) e espaço exponencial, e em tempo O(1.5264n) e espaço polinomial. Um algoritmo rápido, utilizando tempo O(1.5048n) foi encontrado por , 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.7159n e todos os tais conjuntos podem ser listadas em tempo O(1.7159n) .
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 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)nO(1) para qualquer função f existe a menos que a hierarquia W reduz a FPT=W. 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 , 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 .
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.