Conjunto dominante

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 (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.[1]

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 = {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.

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|.

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.[2]

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(2nn) inspecionando todos os subconjuntos de vértices. Fomin, Grandoni & Kratsch (2009) 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 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.7159n e todos os tais conjuntos podem ser listadas em tempo O(1.7159n) (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)nO(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[3]

Referências

  1. ↑ Escoffier, Bruno; Paschos, Vangelis Th. (2006). «Completeness in approximation classes beyond APX». Theoretical Computer Science. 359 (1-3): 369–377. doi:10.1016/j.tcs.2006.05.023 
  2. ↑ Papadimitriou, Christos H.; Yannakakis, Mihailis (1991). «Optimization, Approximation, and Complexity Classes». Journal of Computer and Systems Sciences. 43 (3): 425–440. doi:10.1016/0022-0000(91)90023-X 
  3. ↑ «Dominating set problem (DSP)». Consultado em 8 de julho de 2015. Arquivado do original em 10 de julho de 2015 

Bibliografia

  • Alber, Jochen; Fellows, Michael R; Niedermeier, Rolf (2004), «Polynomial-time data reduction for dominating set», Journal of the ACM, 51 (3): 363–384, doi:10.1145/990308.990309 .
  • Allan, Robert B.; Laskar, Renu (1978), «On domination and independent domination numbers of a graph», Discrete Mathematics, 23 (2): 73–76, doi:10.1016/0012-365X(78)90105-X .
  • Crescenzi, Pierluigi; Kann, Viggo; Halldórsson, Magnús; Karpinski, Marek; Woeginger, Gerhard (2000), «Minimum dominating set», A Compendium of NP Optimization Problems .
  • Faudree, Ralph; Flandrin, Evelyne; Ryjáček, Zdeněk (1997), «Claw-free graphs — A survey», Discrete Mathematics, 164 (1–3): 87–147, MR 1432221, doi:10.1016/S0012-365X(96)00045-3 .
  • Fomin, Fedor V.; Grandoni, Fabrizio; Kratsch, Dieter (2009), «A measure & conquer approach for the analysis of exact algorithms», Journal of the ACM, 56 (5): 25:1–32, doi:10.1145/1552285.1552286 .
  • Fomin, Fedor V.; Grandoni, Fabrizio; Pyatkin, Artem; Stepanov, Alexey (2008), «Combinatorial bounds via measure and conquer: Bounding minimal dominating sets and applications», ACM Transactions on Algorithms, 5 (1): 9:1–17, doi:10.1145/1435375.1435384 .
  • Fomin, Fedor V.; Thilikos, Dimitrios M. (2006), «Dominating sets in planar graphs: branch-width and exponential speed-up», SIAM Journal on Computing, 36 (2): 281, doi:10.1137/S0097539702419649 .
  • Förster, Klaus-Tycho. (2013), «Approximating Fault-Tolerant Domination in General Graphs», Proc. of the Tenth Workshop on Analytic Algorithmics and Combinatorics ANALCO, ISBN 978-1-61197-254-2, SIAM, pp. 25–32, doi:10.1137/1.9781611973037.4 .
  • Predefinição:Garey-Johnson, p. 190, problem GT2.
  • Grandoni, F. (2006), «A note on the complexity of minimum dominating set», Journal of Discrete Algorithms, 4 (2): 209–214, doi:10.1016/j.jda.2005.03.002 .
  • Guha, S.; Khuller, S. (1998), «Approximation algorithms for connected dominating sets», Algorithmica, 20 (4): 374–387, doi:10.1007/PL00009201 .
  • Haynes, Teresa W.; Hedetniemi, Stephen; Slater, Peter (1998a), Fundamentals of Domination in Graphs, ISBN 0-8247-0033-3, Marcel Dekker, OCLC 37903553 .
  • Haynes, Teresa W.; Hedetniemi, Stephen; Slater, Peter (1998b), Domination in Graphs: Advanced Topics, ISBN 0-8247-0034-1, Marcel Dekker, OCLC 38201061 .
  • Hedetniemi, S. T.; Laskar, R. C. (1990), «Bibliography on domination in graphs and some basic definitions of domination parameters», Discrete Mathematics, 86 (1–3): 257–277, doi:10.1016/0012-365X(90)90365-O .
  • Klasing, Ralf; Laforest, Christian (2004), «Hardness results and approximation algorithms of k-tuple domination in graphs», Information Processing Letters, 89 (2): 75–83, doi:10.1016/j.ipl.2003.10.004 .
  • Kann, Viggo (1992), On the Approximability of NP-complete Optimization Problems (PDF). PhD thesis, Department of Numerical Analysis and Computing Science, Royal Institute of Technology, Stockholm .
  • Raz, R.; Safra, S. (1997), «A sub-constant error-probability low-degree test, and sub-constant error-probability PCP characterization of NP», Proc. 29th Annual ACM Symposium on Theory of Computing, ISBN 0-89791-888-6, ACM, pp. 475–484, doi:10.1145/258533.258641 .
  • Takamizawa, K.; Nishizeki, T.; Saito, N. (1982), «Linear-time computability of combinatorial problems on series-parallel graphs», Journal of the ACM, 29 (3): 623–641, doi:10.1145/322326.322328 .
  • van Rooij, J. M. M.; Nederlof, J.; van Dijk, T. C. (2009), «Inclusion/Exclusion Meets Measure and Conquer: Exact Algorithms for Counting Dominating Sets», Proc. 17th Annual European Symposium on Algorithms, ESA 2009, ISBN 978-3-642-04127-3, Lecture Notes in Computer Science, 5757, Springer, pp. 554–565, doi:10.1007/978-3-642-04128-0_50 .

Ligações externas