Dimensão bipartida

Nas áreas da matemática de Teoria dos Grafos e Otimização Combinatória, a Dimensão Bipartida ou Número de Cobertura Biclique de um grafo G = (V, E) é o número mínimo de bicliques (que são subgrafos bipartidos completos), necessários para cobrir todas as arestas em E. Uma coleção de bicliques cobrindo todas as arestas em G é chamada de cobertura de arestas biclique, ou também cobertura biclique. A dimensão bipartida de G é frequentemente denotada pelo símbolo d(G).

Exemplo

Um exemplo de uma cobertura de arestas biclique é mostrado nos seguintes diagramas:

• Exemplos de coberturas de aresta biclique
• 
  Um grafo bipartido...
• 
  ...e uma cobertura com quatro bicliques
• 
  o biclique vermelho da cobertura
• 
  o biclique azul da cobertura
• 
  o biclique verde da cobertura
• 
  o biclique preto da cobertura

Fórmulas de Dimensão Bipartida para alguns grafos

A dimensão biclique de um grafo completo de n vértices, $K_{n}$ é $\lceil \log _{2}n\rceil$.

A dimensão bipartida de um grafo coroa (Crown Graph) de 2n vértices vale $\sigma (n)$, onde

$\sigma (n)=\min \left\{\,k\mid n\leq {\binom {k}{\lfloor k/2\rfloor }}\,\right\}$

é a função inversa do coeficiente binomial central (de Caen, Gregory & Pullman 1981). Fishburn & Hammer (1996) determinaram a dimensão bipartida para alguns grafos especiais. Por exemplo, o caminho $P_{n}$ tem $d(P_{n})=\lfloor n/2\rfloor$ e o ciclo $C_{n}$ tem $d(C_{n})=\lceil n/2\rceil$.

Computando Dimensão Bipartida

A tarefa computacional de determinar a dimensão bipartida para um dado grafo G é um problema de otimização. O problema de decisão para Dimensão Bipartida pode ser definido como segue:

INSTÂNCIA: Um grafo $G=(V,E)$ e um inteiro positivo $k$.

PROBLEMA: G admite uma cobertura de arestas biclique contento no máximo $k$ bicliques?

Esse problema aparece como o problema GT18 no livro clássico de Garey and Johnson sobre NP-Completude, e é uma reformulação bastante simples de outro problema de decisão da família dos conjuntos finitos.

O problema do conjunto base aparece como o problema SP7 no livro de Garey e Johnson. Nele, para o grupo ${\mathcal {S}}=\{S_{1},\ldots ,S_{n}\}$ de subconjuntos de um conjunto finito ${\mathcal {U}}$, um conjunto base para ${\mathcal {S}}$ é outro grupo de subconjuntos ${\mathcal {B}}=\{B_{1},\ldots ,B_{\ell }\}$ de ${\mathcal {U}}$, tal que, todo conjunto $S_{i}$ pode ser descrito como a união de alguns elementos base de ${\mathcal {B}}$. O problema do conjunto base é então definido como segue:

INSTÂNCIA: Um conjunto finito ${\mathcal {U}}$, um grupo ${\mathcal {S}}=\{S_{1},\ldots ,S_{n}\}$ de subconjuntos de ${\mathcal {U}}$, e um inteiro positivo k.

PROBLEMA: Existe um conjunto base de tamanho no máximo $k$ para ${\mathcal {S}}$?

Em sua antiga formulação, o problema foi provado ser NP-completo por Orlin (1977), mesmo para grafos bipartidos. A formulação, como um problema de conjunto base, foi provado ser NP-completo mais cedo por Stockmeyer (1975). O problema permanece NP-difícil mesmo se nós restringirmos seu foco para grafos bipartidos cuja dimensão bipartida é garantida ser no máximo $O(\log \,\!n)$, com n denotando o tamanho da instância do problema (Gottlieb, Savage & Yerukhimovich 2005). Pelo lado positivo, o problema é solúvel em tempo polinomial nos grafos bipartidos de livres de dominós (bipartite domino-free graphs) (Amilhastre, Janssen & Vilarem 1997).

No que diz respeito à existência de algoritmos de aproximação, Simon (1990) provou-se que o problema não pode ter uma boa aproximação (assumindo P ≠ NP). Em virtude disso, a Dimensão Bipartida é NP-dificil em relação a aproximação dentro de $|V|^{1/3-\epsilon }$ para qualquer $\epsilon >0$ fixo, mesmo para grafos bipartidos (Gruber & Holzer 2007).

Em contra-partida, provar que o problema é tratável com parâmetro fixo é um trabalho de projetistas de algorítimos de kernelização, o qual aparece no livro texto de Downey & Fellows (1999). Fleischner, Mujuni & Szeider (2009) também prova um limitante concreto em relação ao tamanho do kernel resultante, que foi, entretanto, melhorado por Nor et al. (2010). Na verdade, para um grafo bipartido com n vértices, ele pode ser decidido em tempo $O(f(k))+n^{3}$ com $f(k)=2^{k2^{k-1}+3k}$ se sua dimensão bipartida é no máximo k (Nor et al. 2010)

Aplicações

O problema de se determinar a dimensão de um gráfico bipartido aparece em vários contextos de computação. Por exemplo, em sistemas computacionais, diferentes utilizadores de um sistema podem ser liberados ou não, a acessar vários recursos. Em um sistema de controle de acesso baseado em papéis, um papel fornece os direitos de acesso a um conjunto de recursos. Um usuário pode possuir várias funções, e ele tem permissão para acessar todos os recursos concedidos por seus papéis. Além disso, um papel pode pertencer a vários usuários. O problema de Mineração de Papeis é encontrar um conjunto mínimo de funções, de modo que, para cada usuário, seus papéis, tomados em conjunto, garantam acesso a todos os recursos especificados. O conjunto de usuários, juntamente com o conjunto de recursos no sistema, induzem naturalmente um grafo bipartido, cujas bordas são permissões. Cada biclique neste gráfico é um papel em potencial, e as melhores soluções para o problema de mineração de papel são precisamente as coberturas de aresta biclique mínimas (Ene et al. 2008).

Um cenário semelhante é conhecido na área de segurança computacional, mais especificamente em secure broadcasting (transmissão segura). Na instalação, várias mensagens precisam ser enviadas, cada uma para um conjunto de receptores, ao longo de um canal inseguro. Cada mensagem tem de ser criptografada usando alguma chave criptográfica que é conhecida apenas pelos destinatários pretendidos. Cada receptor pode possuir várias chaves de criptografia, e cada chave será distribuída para vários receptores. O problema da geração de chave ideal é encontrar um conjunto mínimo de chaves de criptografia para garantir a transmissão segura. Como acima, o problema pode ser modelado utilizando um gráfico cujas coberturas de aresta biclique mínimas coincidam com as soluções para o problema da geração de chave ideal.

Uma diferente aplicação reside na biologia, onde as coberturas de arestas biclique mínimas são usadas em modelos matemáticos de antígenos leucocitários humanos (HLA), sorologia.(Nau et al. 1978).

Veja também

• Lista de problemas NP-Completos
• Numero da interseção (Teoria dos Grafos), o número mínimo de cliques necessários para cobrir as arestas de um grafo.

References

• Amilhastre, Jérôme; Janssen, Philippe; Vilarem, Marie-Catherine (1997), «Computing a minimum biclique cover is polynomial for bipartite domino-free graphs», Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 5–7 January 1997, New Orleans, Louisiana., ACM/SIAM, pp. 36–42 
• de Caen, Dominique; Gregory, David A.; Pullman, Norman J. (1981), «The Boolean rank of zero-one matrices», in: Cadogan, Charles C., 3rd Caribbean Conference on Combinatorics and Computing, Department of Mathematics, University of the West Indies, pp. 169–173, MR 0657202 .
• Downey, Rod; Fellows, Michael R. (1999), Parameterized complexity, ISBN 0-387-94883-X, Springer .
• Ene, Alina; Horne, William G.; Milosavljevic, Nikola; Rao, Prasad; Schreiber, Robert; Tarjan, Robert Endre (2008), «Fast exact and heuristic methods for role minimization problems», in: Ray, Indrakshi; Li, Ninghui, 13th ACM Symposium on Access Control Models and Technologies (SACMAT 2008), ACM, pp. 1–10 .
• Fishburn, Peter C.; Hammer, Peter L. (1996), «Bipartite dimensions and bipartite degrees of graphs», Discrete Mathematics, 160 (1–3): 127–148, doi:10.1016/0012-365X(95)00154-O .
• Fleischner, Herbert; Mujuni, Egbert; Paulusma, Daniël; Szeider, Stefan (2009), «Covering graphs with few complete bipartite subgraphs», Theoretical Computer Science, 410 (21-23): 2045–2053, doi:10.1016/j.tcs.2008.12.059 .
• Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, ISBN 0-7167-1045-5, W.H. Freeman .
• Gottlieb, Lee-Ad J.; Savage, John E.; Yerukhimovich, Arkady (2005), «Efficient data storage in large nanoarrays», Theory of Computing Systems, 38 (4): 503–536, doi:10.1007/s00224-004-1196-9 .
• Gruber, Hermann; Holzer, Markus (2007), «Inapproximability of Nondeterministic State and Transition Complexity Assuming P <> NP.», in: Harju, Terjo; Karhumäki, Juhani; Lepistö, Arto, 11th Conference on Developments in Language Theory (DLT 2007), LNCS, 4588, Turku, Finland: Springer, pp. 205–216, doi:10.1007/978-3-540-73208-2_21 .
• Monson, Sylvia D.; Pullman, Norman J.; Rees, Rolf (1995), «A survey of clique and biclique coverings and factorizations of (0,1)-matrices», Bulletin of the ICA, 14: 17–86, MR 1330781 .
• Nau, D. S.; Markowsky, G.; Woodbury, M. A.; Amos, D. B. (1978), «A mathematical analysis of human leukocyte antigen serology» (PDF), Mathematical Biosciences, 40: 243–270, doi:10.1016/0025-5564(78)90088-3 .
• Nor, Igor; Hermelin, Danny; Charlat, Sylvain; Engelstadter, Jan; Reuter, Max; Duron, Olivier; Sagot, Marie-France (2010). «Mod/Resc Parsimony Inference». arXiv:1002.1292 [cs.DS] 
• Orlin, James (1977), «Contentment in graph theory: covering graphs with cliques», Indagationes Mathematicae, 80 (5): 406–424, doi:10.1016/1385-7258(77)90055-5 .
• Shu, Guoqiang; Lee, David; Yannakakis, Mihalis (2006), «A note on broadcast encryption key management with applications to large scale emergency alert systems.», 20th International Parallel and Distributed Processing Symposium (IPDPS 2006), IEEE .
• Simon, Hans-Ulrich (1990), «On Approximate Solutions for Combinatorial Optimization Problems», SIAM Journal on Discrete Mathematics, 3 (2): 294–310, doi:10.1137/0403025 .
• Stockmeyer, Larry J. (1975), The set basis problem is NP-complete, Technical Report RC-5431, IBM .

Ligações externas

• blog entry about bipartite dimension by David Eppstein