Theoretical Computer Science
- cc.complexity-theory graph-algorithms hypergraphs
- Updated Sat, 18 Jun 2022 10:21:53 GMT
-
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.
Solution
I found the journal version of the preprint by Skums et al. pointed by @mhum; it is here: Discrete Mathematics 309 (2009) 35003517. 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!
External Links
External links referenced by this document: