Local Homophily on Bicolored Graphs is $\mathbf{P}$-complete
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913098405773312 |
|---|---|
| author | Concha-Vega, Pablo |
| author_facet | Concha-Vega, Pablo |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_05047 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Local Homophily on Bicolored Graphs is $\mathbf{P}$-complete Concha-Vega, Pablo Computational Complexity Discrete Mathematics Combinatorics 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. |
| title | Local Homophily on Bicolored Graphs is $\mathbf{P}$-complete |
| topic | Computational Complexity Discrete Mathematics Combinatorics |
| url | https://arxiv.org/abs/2605.05047 |