Local Homophily on Bicolored Graphs is $\mathbf{P}$-complete
This establishes the computational complexity of a natural graph dynamics problem, showing it is as hard as any problem solvable in polynomial time.
The paper introduces a local transformation on bicolored graphs called local homophily and proves that determining whether two vertices become connected under this process is P-complete.
We propose a local transformation on bicolored graphs, which we call local homophily, inspired by adaptive networks and based on majority dynamics and homophily. In this transformation, a vertex updates its color to match the majority of its neighbors, while neighbors of the same color become connected and neighbors of the opposite color become disconnected. We show how to simulate Boolean circuits using local homophily and establish that determining whether a given pair of vertices becomes connected under iterative applications of local homophily is $\mathbf{P}$-complete under logspace reductions.