# Recognizing line graphs of hypergraphs

The line graph of a hypergraph $H$ is the (simple) graph $G$ having edges of $H$ as vertices with two edges of $H$ are adjacent in $G$ if they have nonempty intersection. A hypergraph is an $r$-hypergraph if each of its edges has at most $r$ vertices.

What is the complexity of the following problem: Given a graph $G$, does there exist a $3$-hypergraph $H$ such that $G$ is the line graph of $H$?

It is well-known that recognizing line graphs of $2$-hypergraph is polynomial, and it is known (by Poljak et al., Discrete Appl. Math. 3(1981)301-312) that recognizing line graphs of $r$-hypergraphs is NP-complete for any fixed $r \ge 4$.

Note: In case of simple hypergraphs, i.e. all hyperedges are distinct, the problem is NP-complete as proved in the paper by Poljak et al.

-
It might be worth clarifying that you allow repeated edges in a hypergraph. –  András Salamon Jan 15 '13 at 13:20
@Salamon: Thanks for suggestion, I have edited accordingly. I am sorry, but I have learned that, by definition, hypergraphs may have multi edges! –  user13136 Jan 15 '13 at 17:32

I found the journal version of the preprint by Skums et al. pointed by @mhum; it is here: Discrete Mathematics 309 (2009) 3500–3517. There, the authors corrected their citation as follows:

The situation changes radically if one takes $k \ge 3$ instead of $k = 2$. Lovasz posed the problem of characterizing the class $L_3$, and noted that it has no characterization by a finite list of forbidden induced subgraphs (a finite characterization) [9]. It has been proved that the recognition problems "$G \in L_k$” for “$k \ge 4$” [15], “$G \in L^l_3$” for $k \ge 3$ and the problem of recognition of edge intersection graphs of $3$-uniform hypergraphs without multiple edges [15] are NP-complete.

Reference 15 is the aforementioned Poljak et al. (1981).

So, I think, recognizing line graphs of $3$-hypergraphs (with multiple edges allowed) is an OPEN PROBLEM, and @mhum's answer indeed was helpful in this finding. Thanks!

-
That´s good to know! Thank you for your time. –  user13136 Jan 17 '13 at 9:51

I don't have access to the Poljak et al. paper, but the abstract here seems to indicate that recognizing line-graphs of $r$-hypergraphs is NP-complete for $r \geq 3$, not $4$. Also, the citation in Edge intersection graphs of linear 3-uniform hypergraphs, Skums et al. (pdf) seems to indicate that this is the case:

The situation changes principally if one takes $k=3$ instead of $k=2$. Lovasz posed the problem of characterizing the class $L_3$, and noted that it has no characterization by a finite list of forbidden induced subgraphs (a finite characterization) [10]. It has been proved that recognition problems "$G \in L_3$" [17] and "$G \in L^l_k$" for $k\geq3$ [5] are NP-complete.

Reference 17 in that paper is the aforementioned Poljak et al. (1981). $L_3$ is the class of 3-uniform hypergraphs and $L^l_3$ is the class of linear 3-uniform hypergraphs.

-
The paper Poljak et al. (1981) proves the following special case (Theorem 2.2): Recognizing if a graph is the line graph of a $3$-hypergraph with all hyperedges are distinct is NP-complete. The citation by Skums et al. seems to be incorrect. –  user13136 Jan 13 '13 at 20:45
Ah. I see. It is not always clear to me if the term "hypergraph" includes hypermultigraphs (multihypergraphs?). –  mhum Jan 13 '13 at 20:58
Thank you for reply, and sorry for my loose formulation. –  user13136 Jan 13 '13 at 21:19
@vb le thank you for linking to and investing in my question! –  user13136 Jan 13 '13 at 21:23
@user13136: You're welcome! This is because I know people, including me, who believe that the problem should be NP-complete but cannot find a reference/proof. –  vb le Jan 14 '13 at 13:26