It seems to me that the running time to make a complement of a graph with $n$ nodes is $n!$. Is there any way to make this running time polynomial? That is, is there any method to construct a complement graph that has polynomial running time?
$\endgroup$ 12 Answers
$\begingroup$I'm going to elaborate on @user35603's answer a little bit. Let $A$ be the adjacency matrix for a simple graph $G$. Then the adjacency matrix for $G$ complement can be easily constructed via: $$ \mathbf{1} - A $$ Where $\mathbf{1}$ is the $n\times n$ matrix of all ones with zeros along its diagonal.
$\endgroup$ $\begingroup$Hint: Use adjacency matrix (it's $n \times n$).
$\endgroup$
