Editorial for Mock CCC '21 S5 - Clique and Independent Set


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Imagine that the graph is complete and each edge is either red or blue, and now we wish to count the number of ways to 2-color the graph such that the red and blue vertices are cliques if you look at the red and blue edges respectively.

Let r(v) be the number of red edges incident on v. If v is red, then we can prove that all nodes w with r(w) > r(v) must also be red. This gives an \mathcal O(N) solution.

Note that this means the problem is solvable with only the degrees of the nodes - the actual graph is irrelevant otherwise.


Comments

There are no comments at the moment.