<p>I don't have access to the Poljak et al. paper, but the <a href="http://www.sciencedirect.com/science/article/pii/0166218X8190007X">abstract here</a> seems to indicate that recognizing line-graphs of $r$-hypergraphs is NP-complete for $r \geq 3$, not $4$. Also, the citation in <a href="http://www.bsu.by/Cache/pdf/89683.pdf"><em>Edge intersection graphs of linear 3-uniform hypergraphs</em>, Skums et al. (pdf)</a> seems to indicate that this is the case:</p>

<blockquote>
  <p>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 (<em>a finite characterization</em>) [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.</p>
</blockquote>

<p>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.</p>

CC BY-SA 3.0
2013-01-13T20:45:43.183Z
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
CC BY-SA 3.0
2013-01-13T20:58:05.270Z
Ah. I see. It is not always clear to me if the term "hypergraph" includes hypermultigraphs (multihypergraphs?).
mhum
CC BY-SA 3.0
2013-01-13T21:19:43.360Z
Thank you for reply, and sorry for my loose formulation.
user13136
CC BY-SA 3.0
2013-01-13T21:23:00.627Z
@vb le 
    thank you for linking to and investing in my question!
user13136
CC BY-SA 3.0
2013-01-14T13:26:48.767Z
@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
CC BY-SA 3.0
2013-01-13T19:23:17.333Z
2013-01-13T19:23:17.333Z
mhum
<p>I found the journal version of the preprint by Skums et al. pointed by @mhum; it is here: 
<a href="http://www.sciencedirect.com/science/article/pii/S0012365X07010539">Discrete Mathematics 309 (2009) 3500–3517</a>. 
There, the authors corrected their citation as follows: </p>

<blockquote>
  <p>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 (<em>a finite characterization</em>) [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.</p>
</blockquote>

<p>Reference 15 is the aforementioned Poljak et al. (1981). </p>

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

CC BY-SA 3.0
2013-01-17T09:51:15.607Z
That´s good to know! Thank you for your time.
user13136
CC BY-SA 3.0
2013-01-16T22:47:11.503Z
2013-01-16T22:47:11.503Z
vb le
<p>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. </p>

<p>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$?</p>

<p>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$.    </p>

<p>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.</p>

CC BY-SA 3.0
2013-01-15T13:20:59.370Z
It might be worth clarifying that you allow repeated edges in a hypergraph.
András Salamon
CC BY-SA 3.0
2013-01-15T17:32:00.887Z
@Salamon: Thanks for suggestion, I have edited accordingly. I am sorry, but I have learned that, by definition, hypergraphs may have multi edges!
user13136
<cc.complexity-theory><graph-algorithms><hypergraphs>
Recognizing line graphs of hypergraphs
user13136
# Recognizing line graphs of hypergraphs

(Asked by: username_0 on 2013-01-03)

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.

**Tags:** cc.complexity-theory, graph-algorithms, hypergraphs

> **Comments:**
> **username_1**: It might be worth clarifying that you allow repeated edges in a hypergraph.  
> **username_0**: @Salamon: Thanks for suggestion, I have edited accordingly. I am sorry, but I have learned that, by definition, hypergraphs may have multi edges!  

---

## 2 answers

### Answer by username_3 on 2013-01-16. Score: 9 | Accepted answer

I found the journal version of the preprint by Skums et al. pointed by @username_2; it is here:
[Discrete Mathematics 309 (2009) 3500–3517](http://www.sciencedirect.com/science/article/pii/S0012365X07010539).
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 @username_2's answer indeed was helpful in this finding. Thanks!

> **Comments:**
> **username_0**: That´s good to know! Thank you for your time.  

---

### Answer by username_2 on 2013-01-13. Score: 9

I don't have access to the Poljak et al. paper, but the [abstract here](http://www.sciencedirect.com/science/article/pii/0166218X8190007X) 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)](http://www.bsu.by/Cache/pdf/89683.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.

> **Comments:**
> **username_0**: 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.  
> **username_2**: Ah. I see. It is not always clear to me if the term "hypergraph" includes hypermultigraphs (multihypergraphs?).  
> **username_0**: Thank you for reply, and sorry for my loose formulation.  
> **username_0**: @username_3      thank you for linking to and investing in my question!  
> **username_3**: @username_0: 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.  

---

