Complejidad de k-clique para hipergrafías

Problema clásico:

Deje que se dé un número . El problema -clique es el siguiente. $k$ $k$

Dado un gráfico , ¿existe un subconjunto de vértices para que dos vértices de sean adyacentes? $G$ $S$ $k$ $S$

Problema de hipergrafía:

Deje que se den los números y . El problema -hiperclique es el siguiente. $c$ $k$ $(c,k)$

Dada una hipergrafía -uniforme , ¿existe un conjunto de vértices para que cualquier subconjunto de vértices de forme una hiperedificación? $c$ $H$ $S$ $k$ $c$ $S$

Preguntas:

(1) ¿Cuál es el algoritmo más conocido para resolver -hiperclique? $(c,k)$

(2) ¿Cuál es su complejidad temporal?

(3) ¿Existe alguna conexión entre -hiperclique y la multiplicación de matrices? $(c,k)$

Por lo que sé, este podría ser un problema bien estudiado. Cualquier referencia que investigue este problema es muy apreciada.

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

Puede valer la pena señalar lo obvio: dado que entendemos el caso , el problema es NP completo y no FPT en términos de (pero es FPT en términos de ). Además (aún obvio), podría reformular el problema como la selección de filas de la matriz de incidencia de modo que en la submatriz en estas filas, columnas tengan suma .

c = 2

$c=2$

c

$c$

k

$k$

k

$k$

(\binom{k}{c})

$k\choose c$

c

$c$

Andrew D. King

Esto suele expresarse en términos de encontrar un conjunto independiente de en una hipergrafía uniforme. Vea el artículo de Yuster 2006 research.haifa.ac.il/~raphy/papers/counthyper.pdf para algunos consejos útiles (incluidos los enlaces con la multiplicación de matrices).

k

$k$

c

$c$

András Salamon

@ AndrewD.King, no entiendo qué quieres decir con "pero es FPT en términos de k", k-clique es W [1] -duro en términos de k. Y OP: K-Clique ya es w [1] difícil, pero su pregunta no es una pregunta de nivel de investigación, ya que se compara con problemas polinómicos.

Saeed

Gracias por la información. Estoy más interesado en saber si hay o no algunos y tal manera que -hiperclique esté en . Sabemos que para , -clique se puede resolver en .

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

Entonces sabes que no hay n ^ o (k) para la camarilla y, en relación con la multiplicación de matrices, no te refieres a la reducción de AP sino solo a la reducción del tiempo de ejecución, ahora es más claro para mí, no tengo idea al respecto, pero tal vez necesites para incluir c en el exponente también.

Saeed

Respuestas:

No se sabe si hay un , y manera que hiperclique esté en el tiempo . Tenga en cuenta que el caso de es trivial. Durante años he comunicado este problema a muchas personas, y lo enseñé en cs266 en Stanford, debido a su conexión para resolver -Sat. (Varias sesiones de problemas abiertos en los talleres probablemente registraron esto). Aquí hay algunas cosas que sé: $\varepsilon > 0$ $c > 2$ $k > c$ $(c,k)$ $n^{k-\varepsilon}$ $k \leq c$ $k$

Probé hace varios años que resolver gráficos de en nodos en tiempo implica hiperclique en tiempo. No lo he publicado. $4-cycle$ $n$ $n^{2-\varepsilon}$ $(3,4)$ $n^{4-\varepsilon}$

ACTUALIZAR (agosto de 2019) el resultado mencionado y algunas generalizaciones ahora aparecen en el documento

Andrea Lincoln, Virginia Vassilevska Williams, R. Ryan Williams: dureza ajustada para los ciclos y caminos más cortos en gráficos dispersos . SODA 2018: 1236-1252

Si puede resolver la hiperclique como se indicó anteriormente, entonces Max-3-Sat puede resolverse en menos de tiempo. De manera similar, resolver la hiperclique produciría un algoritmo -Sat más rápido . Entonces, si crees en Strong ETH, entonces hay un límite obvio aquí. La reducción es una generalización natural de la reducción de Max-2-Sat a la búsqueda de triángulos ( camarilla) de ICALP'04 y mi tesis doctoral. $(3,4)$ $2^n$ $(k,k+1)$ $k$ $(2,3)$

Puede resolver la hiperclique en tiempo generalizando los Algoritmos eficientes de papel para problemas de camarilla . $(c,k)$ $n^k/(\log n)^{\Omega(k)}$

Ryan Williams
fuente

Gracias Ryan! Agradezco su respuesta y comparto el documento sobre el problema de la camarilla. :)

Michael Wehar

¿5 ciclos es más difícil que 4 ciclos?

Michael Wehar

Hasta donde sabemos, 3 ciclos es más difícil. El caso impar en general toma aproximadamente O (n ^ {2.373}) tiempo, el caso par toma O (n ^ 2) para ciclos de longitud fija. Ver, por ejemplo, Yuster y Zwick, Encontrar incluso ciclos incluso más rápido.

Ryan Williams

¡Oh wow! Eso es muy interesante Ok, gracias. :)

Michael Wehar

¡Frio! Gracias por la referencia actualizada.

Michael Wehar