Conjunto dominante
![](http://upload.wikimedia.org/wikipedia/commons/thumb/e/e1/Dominating-set.svg/150px-Dominating-set.svg.png)
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.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/5/51/Dominating-set-2.svg/115px-Dominating-set-2.svg.png)
- 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|.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/2/2c/Dominating-set-reduction.svg/120px-Dominating-set-reduction.svg.png)
- 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
- ↑ 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
- ↑ 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
- ↑ «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
- Set cover problem
- Bondage number