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.

  • $\begingroup$ 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. $\endgroup$
    – RJK
    Oct 1 '10 at 12:34
  • 1
    $\begingroup$ Cross-post asking for a structure theorem: mathoverflow.net/questions/41123/cliques-of-hyperedges $\endgroup$
    – daveagp
    Oct 5 '10 at 10:28

Every graph G is a line graph of some hypergraph, for instance the one that has the edges of G as its vertices and the sets of edges neighboring each vertex of G as its hyperedges. Therefore, finding cliques in line graphs of hypergraphs can be no easier than finding cliques in arbitrary graphs.

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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