Reconociendo gráficos lineales de hipergrafías

El gráfico lineal de una hipergrafía es el gráfico (simple) G que tiene bordes de H ya que los vértices con dos bordes de H son adyacentes en G si tienen una intersección no vacía. Una hipergrafía es un r- hiperígrafo si cada uno de sus bordes tiene como máximo r vértices.$H$$G$$H$$H$$G$$r$$r$

¿Cuál es la complejidad del siguiente problema? Dado un gráfico , ¿existe un 3 -hígrafo H tal que G sea ​​el gráfico lineal de H ?$G$$3$$H$$G$$H$

Es bien sabido que el reconocimiento de gráficos de líneas de -hypergraph es polinomio, y se sabe (por Poljak et al., Discrete Appl.. Math 3 (1981) 301-312) que el reconocimiento de gráficos de líneas de r -hypergraphs es NP -completo para cualquier r ≥ 4 fijo . $2$$r$$r \ge 4$

Nota: en caso de hipergrafías simples, es decir, todas las hiperedificaciones son distintas, el problema es NP completo, como lo demuestra Poljak et al.

Encontré la versión del diario de la preimpresión de Skums et al. señalado por @mhum; está aquí: Discrete Mathematics 309 (2009) 3500–3517 . Allí, los autores corrigieron su cita de la siguiente manera:

La situación cambia radicalmente si se toma lugar de k = 2 . Lovasz planteó el problema de caracterizar la clase L 3 , y señaló que no se caracteriza por una lista finita de subgrafías inducidas prohibidas ( una caracterización finita ) [9]. Se ha demostrado que los problemas de reconocimiento " G ∈ L k ” para “ k ≥ 4 ” [15], “ G $k \ge 3$$k = 2$$L_3$$G \in L_k$$k \ge 4$ ” para k ≥ 3 y el problema de reconocimiento de gráficos de intersección de bordes de$G \in L^l_3$$k \ge 3$$3$hipergráficas uniformes sin bordes múltiples [15] son ​​NP completas.

La referencia 15 es la mencionada Poljak et al. (1981).

Entonces, creo que reconocer gráficos de líneas de hiperpráficos (con múltiples bordes permitidos) es un PROBLEMA ABIERTO , y la respuesta de @ mhum fue útil en este hallazgo. ¡Gracias!$3$

No tengo acceso a Poljak et al. artículo, pero el resumen aquí parece indicar que reconocer gráficos lineales de hiperígrafos es NP-completo para r ≥ $r$$r \geq 3$ , no . Además, la cita en gráficos de intersección de bordes de hipergrafías lineales de 3 uniformes , Skums et al. (pdf) parece indicar que este es el caso:$4$

La situación cambia principalmente si se toma lugar de k = 2 . Lovasz planteó el problema de caracterizar la clase L 3 , y señaló que no se caracteriza por una lista finita de subgrafías inducidas prohibidas ( una caracterización finita ) [10]. Se ha demostrado que los problemas de reconocimiento " G ∈ L 3 " [17] y " G ∈ L l $k=3$$k=2$$L_3$$G \in L_3$$G \in L^l_k$ " para [5] son ​​NP-completos.$k\geq3$

La referencia 17 en ese documento es Poljak et al. (1981). es la clase de hypergraphs 3-uniformes y L l 3 es la clase de hypergraphs 3-uniformes lineales.$L_3$$L^l_3$