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

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}$$?

• Why would you expect this to be possible? Sep 11, 2021 at 12:03
• I am not expecting it to be possible. I am asking whether this is possible.
– user136613
Sep 11, 2021 at 12:03

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.