# Max-clique in line graph of hypergraph

Suppose we have a multigraph (later, a multihypergraph). An edge-clique is a set of edges which all pairwise intersect (have at least one common vertex). Then any edge-clique $C$ in a multigraph always falls into one of two categories:

• A star: there is a vertex such that every edge of $C$ contains it
• A triangle: there are three vertices such that every edge of $C$ goes between two of them

This leads to an easy $O(n^3)$-time algorithm to compute the largest edge-clique.

I am pretty sure one can show more generally, that for every $r$, in multihypergraphs with maximum edge size $r$, you can prove a certain structure theorem for hyperedge-cliques, and get a polynomial time algorithm to find the maximum clique.

Is there anything related to this result known? Also, the algorithm I have in mind is extremely high degree polynomial; it would be nice to get something with running time $n^{\mathrm{poly}(r)}$ or better.

I found this interesting since the maximum edge-clique is a lower bound on the edge-chromatic number (a.k.a chromatic index).

Edit: In the cross-post, the reference about kernels leads to a $2^{2^{\mathrm{exp}(r)}}n^{\mathrm{exp}(r)}$-time algorithm: guess the kernel and guess the restriction of the clique to the kernel.

• You are almost at extremal set theory, e.g. intersecting systems. Check out Cameron's "Combinatorics" and references therein. I'm not sure about the algorithmics, though.
– RJK
Oct 1, 2010 at 12:34
• Cross-post asking for a structure theorem: mathoverflow.net/questions/41123/cliques-of-hyperedges Oct 5, 2010 at 10:28

Of course with your limitation of edge size $r$, one can only do this starting from a graph $G$ with degree $r$, and max clique in bounded degree graphs is not so hard, so this doesn't rule out the $n^{poly(r)}$ algorithm you're hoping for.