1
$\begingroup$

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

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

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

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