Max-clique no gráfico de linhas do hipergrafo

8

Suponha que tenhamos um multigráfico (mais tarde, um hiperhipógrafo). Um clique de aresta é um conjunto de arestas que se cruzam em pares (com pelo menos um vértice comum). Então, qualquer clique de borda em uma multigráfica sempre cai em uma de duas categorias:C

  • Uma estrela : existe um vértice de modo que todas as arestas de contêmC
  • Um triângulo : existem três vértices, de modo que cada aresta de passa entre dois delesC

Isso leva a um algoritmo fácil de tempo para calcular a maior clique de borda.O(n3)

Tenho certeza de que é possível mostrar de maneira mais geral que, para cada , em multi-hipergráficos com tamanho máximo de aresta , você pode provar um certo teorema de estrutura para hiper-cliques e obter um algoritmo de tempo polinomial para encontrar a camarilha máxima.rr

Existe alguma coisa relacionada a esse resultado conhecida? Além disso, o algoritmo que tenho em mente é um polinômio de alto grau; seria bom obter algo com o tempo de execução ou melhor.npoeuy(r)

Achei isso interessante, já que o clique máximo na borda é um limite inferior no número cromático da borda (também conhecido como índice cromático).

Edit: Na postagem cruzada, a referência sobre kernels leva a um algoritmo de tempo : adivinhe o kernel e adivinhe a restrição da camarilha ao kernel.22exp(r)nexp(r)

daveagp
fonte
Você está quase na teoria dos conjuntos extremais, por exemplo, sistemas que se cruzam. Confira "Combinatorics", de Cameron, e suas referências. Não tenho certeza sobre os algoritmos, no entanto.
RJK
1
Publicação
daveagp

Respostas:

5

Todo gráfico G é um gráfico de linha de algum hipergrafo, por exemplo, aquele que tem as arestas de G como seus vértices e os conjuntos de arestas vizinhas a cada vértice de G como suas hiperedias. Portanto, encontrar cliques em gráficos de linha de hipergrafos não pode ser mais fácil do que encontrar cliques em gráficos arbitrários.

Obviamente, com a limitação do tamanho da aresta , só é possível fazer isso a partir de um gráfico com grau , e o clique máximo em gráficos de graus limitados não é tão difícil, portanto, isso não descarta o algoritmo que você está esperando.rGrnpoeuy(r)

David Eppstein
fonte