What is the time to create a complement of a graph?

Question

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?

Answer 1

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.

Answer 2

Hint: Use adjacency matrix (it's $n \times n$).