Rozpoznawanie wykresów liniowych hipergraphów

Wykres liniowy hipergrafu jest (prostym) wykresem G mającym krawędzie H, ponieważ wierzchołki o dwóch krawędziach H sąsiadują w G, jeśli mają niepuste przecięcie. Hypergraph to r- hipergraph, jeśli każda jego krawędź ma co najwyżej r wierzchołków.$H$$G$$H$$H$$G$$r$$r$

Jaka jest złożoność następującego problemu: Czy na podstawie wykresu istnieje 3- hipergraph H, taki że G jest wykresem liniowym H ?$G$$3$$H$$G$$H$

Dobrze wiadomo, że rozpoznawanie wykresów liniowych hipergraph jest wielomianowe i wiadomo (według Poljak i in., Discrete Appl. Math. 3 (1981) 301-312), że rozpoznawanie wykresów liniowych r- hypergraph jest NP -kompletny dla dowolnego ustalonego r ≥ 4 . $2$$r$$r \ge 4$

Uwaga: W przypadku prostych hipergraphów, tj. Wszystkie hiperwery są różne, problem jest NP-zupełny, jak udowodniono w pracy Poljak i in.

Znalazłem wersję czasopisma preprint autorstwa Skums i in. wskazane przez @mhum; jest tutaj: Discrete Mathematics 309 (2009) 3500–3517 . Tam autorzy poprawili cytat w następujący sposób:

Sytuacja zmienia się radykalnie, jeśli weźmie się zamiast k = 2 . Lovasz postawił problem charakteryzowania klasy L 3 i zauważył, że nie ma on scharakteryzowania na podstawie skończonej listy zabronionych indukowanych subgrafów ( charakterystyka skończona ) [9]. Udowodniono, że problemy z rozpoznawaniem „ G ∈ L k ” dla „ k ≥ 4 ” [15], „ G ∈ L l 3 ” dla k ≥ 3 oraz problem z rozpoznawaniem wykresów przecięcia krawędzi $k \ge 3$$k = 2$$L_3$$G \in L_k$$k \ge 4$$G \in L^l_3$$k \ge 3$$3$-jednostkowe hipergrrafy bez wielu krawędzi [15] są NP-kompletne.

Odnośnik 15 to wyżej wspomniany Poljak i in. (1981).

Myślę więc, że rozpoznanie wykresów liniowych hipergraphów (z dozwolonymi wieloma krawędziami) jest OTWARTYM PROBLEMEM, a odpowiedź @ mhum rzeczywiście była pomocna w tym odkryciu. Dzięki!$3$

Nie mam dostępu do Poljak i in. papier, ale streszczenie tutaj wydaje się wskazywać, że rozpoznawanie wykresów liniowych hipergraphów jest NP-kompletne dla r ≥ 3 , a nie 4 . Cytowanie w grafach przecięcia krawędzi liniowych hipergraphów 3-jednolitych , Skums i in. (pdf) wydaje się wskazywać, że tak jest:$r$$r \geq 3$$4$

Sytuacja zmienia się zasadniczo, jeśli weźmie się zamiast k = 2 . Lovasz postawił problem charakteryzowania klasy L 3 i zauważył, że nie ma on charakterystyki przez skończoną listę zabronionych indukowanych subgrafów ( charakterystyka skończona ) [10]. Udowodniono, że problemy z rozpoznaniem „ G ∈ L 3 ” [17] i „ G ∈ L l k ” dla k ≥ 3 [5] są NP-całkowite.$k=3$$k=2$$L_3$$G \in L_3$$G \in L^l_k$$k\geq3$

Odnośnik 17 w tym artykule to wspomniany wyżej Poljak i in. (1981). jest klasa 3-jednolitych hipergrafów i L l 3 jest klasa liniowych 3-jednolitych hipergrafów.$L_3$$L^l_3$