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.