Max-clique no gráfico de linhas do hipergrafo

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êm$C$
• Um triângulo : existem três vértices, de modo que cada aresta de passa entre dois deles$C$

Isso leva a um algoritmo fácil de tempo para calcular a maior clique de borda.$O(n^3)$

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

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.$n^{\mathrm{poly}(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.$2^{2^{\mathrm{exp}(r)}}n^{\mathrm{exp}(r)}$

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.$r$$G$$r$$n^{poly(r)}$