21
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ It might be worth clarifying that you allow repeated edges in a hypergraph. $\endgroup$ Commented Jan 15, 2013 at 13:20
  • $\begingroup$ @Salamon: Thanks for suggestion, I have edited accordingly. I am sorry, but I have learned that, by definition, hypergraphs may have multi edges! $\endgroup$
    – user13136
    Commented Jan 15, 2013 at 17:32

2 Answers 2

9
$\begingroup$

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!

$\endgroup$
1
  • $\begingroup$ That´s good to know! Thank you for your time. $\endgroup$
    – user13136
    Commented Jan 17, 2013 at 9:51
9
+50
$\begingroup$

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.

$\endgroup$
5
  • 5
    $\begingroup$ 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. $\endgroup$
    – user13136
    Commented Jan 13, 2013 at 20:45
  • $\begingroup$ Ah. I see. It is not always clear to me if the term "hypergraph" includes hypermultigraphs (multihypergraphs?). $\endgroup$
    – mhum
    Commented Jan 13, 2013 at 20:58
  • $\begingroup$ Thank you for reply, and sorry for my loose formulation. $\endgroup$
    – user13136
    Commented Jan 13, 2013 at 21:19
  • $\begingroup$ @vb le thank you for linking to and investing in my question! $\endgroup$
    – user13136
    Commented Jan 13, 2013 at 21:23
  • 5
    $\begingroup$ @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. $\endgroup$
    – vb le
    Commented Jan 14, 2013 at 13:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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