Finding maximum clique given, for each edge, union of all cliques containing it

Question

For every edge $e\in E$ of a graph $G=(V,E)$ we know the union $U_{e}$ of the edges of all cliques that contain $e$.

Can we determine, in polynomial time, for a given edge $e_{0}\in E$, the size of the maximum clique that contains $e_{0}$?

Answer 1

The sets $U_e$ can be computed in polynomial time. In fact, if $e = \{x,y\}$, then $U_e$ consists of the following edges:

• $\{x,y\}$
• For each $z$ such that $x,y,z$ is a clique, the edges $\{x,z\},\{y,z\}$.
• For each $z,w$ such that $x,y,z,w$ is a clique, the edge $\{z,w\}$.

To see this, note first that $U_e$ contains all of these edges by definition. Conversely, let $e'$ be some edge in $U_e$. There are three possibilities:

• $e' = \{x,y\}$.
• $e' = \{x,z\}$ for some $z \neq y$ (the case $e' = \{y,z\}$ for some $z \neq x$ is similar). In this case, there is some clique containing both edges $\{x,y\}$ and $\{x,z\}$. This clique contains the vertices $x,y,z$, and in particular, $x,y,z$ is a clique.
• $e' = \{z,w\}$ for some $z,w \neq x,y$. In this case, there is some clique containing both edges $\{x,y\}$ and $\{z,w\}$. The clique contains the vertices $x,y,z,w$, and in particular, $x,y,z,w$ is a clique.

Finally, notice that the size of the maximum clique containing the edge $\{x,y\}$ is the two plus size of the maximum clique in the subgraph of $G$ induced by the common neighbors of $x$ and $y$. Conversely, given a graph $H$, we can adjoin two new vertices $x$ and $y$ connected to one another and to the rest of the vertices, obtaining a graph $G$ in which the size of the maximum clique containing $x$ and $y$ is two plus the size of the original graph $H$.

Putting everything together, we see that your problem is solvable in polynomial time iff P=NP.