Complete Graph Identification in Population Protocols

We consider the population protocol model where indistinguishable state machines, referred to as agents, communicate in pairs. The communication graph specifies potential interactions ( communication) between agent pairs. This paper addresses the complete graph identification problem, requiring agents to determine if their communication graph is a clique or not. We evaluate various settings based on: (i) the fairness preserved by the adversarial scheduler -- either global fairness or weak fairness, and (ii) the knowledge provided to agents beforehand -- either the exact population size n, a common upper bound P on n, or no prior information. Positively, we show that O(n²) states per agent suffice to solve the complete graph identification problem under global fairness without prior knowledge. With prior knowledge of n, agents can solve the problem using only $O(n)$ states under weak fairness. Negatively, we prove that complete graph identification remains unsolvable under weak fairness when only a common upper bound P on the population size n is known.