Maximal Independent Set is an algorithm that finds the maximal set of vertices that have no adjacent between each other. For this vertices set, there is no edge connecting any of the two, and the size of the vertex set is different by different method.