Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

2 Answers 2

up vote 7 down vote accepted

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!

share|improve this answer
    
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.

share|improve this answer
5  
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
5  
@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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.