<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2011-08-21T16:02:36.617Z
2011-08-21T16:02:36.617Z
David Eppstein
<p>Suppose we have a multigraph (later, a multihypergraph). An <i>edge-clique</i> 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:</p>

<ul>
<li>A <i>star</i>: there is a vertex such that every edge of $C$ contains it</li>
<li>A <i>triangle</i>: there are three vertices such that every edge of $C$ goes between two of them</li>
</ul>

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

<p>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.</p>

<p>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.</p>

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

<p>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.</p>

CC BY-SA 2.5
2010-10-01T12:34:48.697Z
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
CC BY-SA 2.5
2010-10-05T10:28:31.313Z
Cross-post asking for a structure theorem: http://mathoverflow.net/questions/41123/cliques-of-hyperedges
daveagp
<ds.algorithms><graph-theory><hypergraphs><graph-algorithms><clique>
Max-clique in line graph of hypergraph
daveagp
# Max-clique in line graph of hypergraph

(Asked by: username_0 on 2010-10-01)

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.

**Tags:** ds.algorithms, graph-theory, hypergraphs, graph-algorithms, clique

> **Comments:**
> **username_1**: 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.  
> **username_0**: Cross-post asking for a structure theorem: http://mathoverflow.net/questions/41123/cliques-of-hyperedges  

---

## 1 answers

### Answer by username_2 on 2011-08-21. Score: 6

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.


---

