Complexidade do k-clique para hipergráficos

Problema clássico:

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

Dado um gráfico , existe um subconjunto de vértices para que quaisquer dois vértices de sejam adjacentes? $G$ $S$ $k$ $S$

Problema do hipergrafo:

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

Dado um hipergrafo uniforme , existe um conjunto de vértices para que qualquer subconjunto de vértices de forme uma hiper-borda. $c$ $H$ $S$ $k$ $c$ $S$

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.

cc.complexity-theory graph-theory matrices clique fixed-parameter-tractable Michael Wehar
fonte

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 = 2

$c=2$

c

$c$

k

$k$

k

$k$

(\binom{k}{c})

$k\choose c$

c

$c$

Andrew D. King

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).

k

$k$

c

$c$

András Salamon

@ 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

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 > 2

$c>2$

k > 2

$k>2$

(c, k)

$(c,k)$

D T I M E (n^{k - ϵ})

$\mathrm{DTIME}(n^{k-\epsilon})$

k > 2

$k>2$

k

$k$

D T I M E (n^{k - ϵ})

$\mathrm{DTIME}(n^{k-\epsilon})$

Michael Wehar

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:

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: $\varepsilon > 0$ $c > 2$ $k > c$ $(c,k)$ $n^{k-\varepsilon}$ $k \leq c$ $k$

Eu provei há vários anos que resolver em gráficos de nós em tempo implica hiperclique em tempo. Ainda não publicou. $4-cycle$ $n$ $n^{2-\varepsilon}$ $(3,4)$ $n^{4-\varepsilon}$

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)$ $2^n$ $(k,k+1)$ $k$ $(2,3)$

Você pode resolver a hiperclique em , generalizando o artigo Algoritmos eficientes para problemas de clique . $(c,k)$ $n^k/(\log n)^{\Omega(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

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