Complexidade do k-clique para hipergráficos

9

Problema clássico:

Seja dado um número . O problema da classe é o seguinte.kk

Dado um gráfico , existe um subconjunto de vértices para que quaisquer dois vértices de sejam adjacentes?GSkS

Problema do hipergrafo:

Seja dado os números e . O problema -hiperclique é o seguinte.ck(c,k)

Dado um hipergrafo uniforme , existe um conjunto de vértices para que qualquer subconjunto de vértices de forme uma hiper-borda.cHSkcS

Questões:

(1) Qual é o algoritmo mais conhecido para resolver a hiperclique ?(c,k)

(2) Qual é a sua complexidade temporal?

(3) Existe alguma conexão entre hiperclique e multiplicação de matrizes?(c,k)

Pelo que sei, esse pode ser um problema bem estudado. Todas as referências que investigam esse problema são muito apreciadas.

Michael Wehar
fonte
2
Vale ressaltar o óbvio: como entendemos o caso , o problema é NP-completo e não o FPT em termos de (mas é o FPT em termos de ). Além disso (ainda óbvio), você poderia reformular o problema como a seleção de linhas da matriz de incidência, de modo que na submatriz nessas linhas, colunas tenham a soma . c=2ckk(kc)c
Andrew D. King
4
Isso geralmente é redigido em termos de encontrar um conjunto independente de em um hipergrafo uniforme. Veja o artigo de Yuster em 2006 research.haifa.ac.il/~raphy/papers/counthyper.pdf para alguns indicadores úteis (incluindo links com multiplicação de matrizes). kc
András Salamon
5
@ AndrewD.King, não entendo o que você quer dizer com "mas é FPT em termos de k", k-clique é W [1] -hard em termos de k. E o OP: K-Clique já é muito difícil, mas sua pergunta não é bem uma questão de nível de pesquisa, pois a compara com problemas polinomiais.
Saeed
2
Obrigado pela informação. Estou mais interessado em saber se existe ou não e modo que -hyperclique esteja em . Sabemos que para , -clique pode ser resolvido em . c>2k>2(c,k)DTIME(nkϵ)k>2kDTIME(nkϵ)
Michael Wehar
2
Então, você sabe que não há n ^ o (k) para clique e, em relação à multipulação da matriz, você não quer dizer redução de ap, mas apenas redução do tempo de execução, agora é mais claro para mim, não tenho ideia, mas talvez você precise para incluir c no expoente também.
Saeed

Respostas:

12

Não se sabe se existe um , e tal que hiperclique está em . Observe que o caso de é trivial. Durante anos, comuniquei esse problema a muitas pessoas e o ensinei no CS266 em Stanford, devido à sua conexão com a solução de -Sat. (Várias sessões de problemas abertos em workshops provavelmente registraram isso.) Aqui estão algumas coisas que eu sei:ε>0c>2k>c(c,k)nkεkck

Eu provei há vários anos que resolver em gráficos de nós em tempo implica hiperclique em tempo. Ainda não publicou.4cyclenn2ε(3,4)n4ε

ATUALIZAR (ago 2019) o resultado mencionado e algumas generalizações agora aparecem no artigo

Andrea Lincoln, Virginia Vassilevska Williams, R. Ryan Williams: Dureza apertada para ciclos e caminhos mais curtos em gráficos esparsos . SODA 2018: 1236-1252

Se você puder resolver hiperclique como indicado acima, o Max-3-Sat poderá ser resolvido em menos de tempo. Da mesma forma, resolver a hiperclique produziria um algoritmo -Sat mais rápido . Então, se você acredita em ETH forte, há um limite óbvio aqui. A redução é uma generalização natural da redução de Max-2-Sat para descoberta de triângulo ( clique) do ICALP'04 e minha tese de doutorado.(3,4)2n(k,k+1)k(2,3)

Você pode resolver a hiperclique em , generalizando o artigo Algoritmos eficientes para problemas de clique .(c,k)nk/(logn)Ω(k)

Ryan Williams
fonte
Obrigado Ryan! Agradeço sua resposta e compartilhei o artigo sobre o problema da camarilha. :)
Michael Wehar
O ciclo 5 é mais difícil que o ciclo 4?
Michael Wehar
3
Tanto quanto sabemos, o ciclo 3 é mais difícil. O caso ímpar em geral leva cerca de O (n ^ {2.373}) tempo, o caso par leva O (n ^ 2) para ciclos de comprimento fixo. Veja, por exemplo, Yuster e Zwick, Encontrar ciclos ainda mais rápidos.
Ryan Williams
Uau! Isso é bem interessante. Ok, obrigada. :)
Michael Wehar
Legal! Obrigado pela referência atualizada.
Michael Wehar 28/08/19