Local Homophily on Bicolored Graphs is $\mathbf{P}$-complete

Pablo Concha-Vega

arxiv: 2605.05047 · v2 · submitted 2026-05-06 · 💻 cs.CC · cs.DM· math.CO

Local Homophily on Bicolored Graphs is P-complete

Pablo Concha-Vega This is my paper

Pith reviewed 2026-05-08 15:14 UTC · model grok-4.3

classification 💻 cs.CC cs.DMmath.CO

keywords local homophilybicolored graphsP-completenessBoolean circuit simulationmajority dynamicsgraph connectivitylogspace reductionsadaptive networks

0 comments

The pith

Local homophily on bicolored graphs can simulate arbitrary Boolean circuits, rendering vertex-connectivity questions P-complete under logspace reductions.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The authors define a local homophily rule on bicolored graphs in which each vertex adopts the majority color of its neighbors and then forms edges only to same-color neighbors while removing edges to opposite-color neighbors. They construct initial graphs whose evolution under repeated applications of this rule exactly reproduces the input-output behavior of any Boolean circuit. Because circuit value problems are P-complete, the question of whether two designated vertices end up connected after the dynamics run to completion is therefore also P-complete under logspace reductions. A sympathetic reader sees this as evidence that simple, local, majority-based rewiring rules on networks are already expressive enough to embed universal computation.

Core claim

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 P-complete under logspace reductions.

What carries the argument

The local homophily transformation: a vertex recolors to the majority of its current neighbors, then adds edges between same-color neighbors and deletes edges between opposite-color neighbors.

If this is right

Any logspace reduction from a P-complete circuit problem to the local-homophily connectivity question immediately yields a P-completeness result for that question.
Local majority recoloring combined with homophily rewiring is sufficient to implement AND, OR, and NOT gates.
The long-term connectivity pattern produced by the dynamics is computationally as hard as evaluating arbitrary Boolean circuits.
Logspace reductions suffice to transfer hardness from circuit problems to the graph-evolution problem.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Similar local rewiring rules on larger classes of graphs may also embed universal computation and therefore inherit P-hardness for their prediction problems.
If real-world networks evolve by approximate versions of this rule, forecasting their eventual connectivity structure is at least as hard as solving P-complete problems.
One could test the robustness of the simulation by adding small amounts of noise to the majority rule and checking whether the P-completeness threshold survives.

Load-bearing premise

Initial bicolored graphs can be chosen so that the local-homophily dynamics faithfully reproduce the gate logic and wiring of any Boolean circuit without introducing extra connections or losing required ones.

What would settle it

A concrete small Boolean circuit together with a proof that no finite initial bicolored graph exists whose local-homophily evolution makes the designated output vertices connect exactly when the circuit evaluates to true.

Figures

Figures reproduced from arXiv: 2605.05047 by Pablo Concha-Vega.

**Figure 1.** Figure 1: Example of local homophily. Left: the original bicolored graph B. Right: the bicolored graph after applying the transformation at vertex 1, i.e., Φ1(B). tive networks are often studied from a dynamical or statistical perspective, we investigate them from the viewpoint of computational complexity. 2 Preliminaries We consider finite, simple graphs. Let G be a graph. The set of vertices of G is denoted V (G),… view at source ↗

**Figure 2.** Figure 2: Example of a flower graph. Left: the flower graph F6,8. Right: a succinct representation of F6,8. 4. For all i < k, vertex i has no edges to any central vertex > k. 5. The subgraph induced by [k, n] is Kn−k+1. Proof. We proceed by induction on k. Vertex 1 flips its color when applying Φ1, because in the central clique it has n − 1 neighbors of its initial color +1, while in its petal it is connected to m ≥… view at source ↗

**Figure 3.** Figure 3: OR and AND gadgets. Dashed lines indicate the positions of the inputs. view at source ↗

**Figure 4.** Figure 4: Duplicator gadget. 3.3 Simulating Boolean Circuits Given a monotone Boolean circuit, we construct a corresponding network of gadgets as follows. For each circuit input, we introduce a duplicator gadget. If an input is TRUE, the corresponding input edge of its duplicator is added to the initial configuration. For each AND and OR gate, we introduce the corresponding logical gadget and connect it to a duplica… view at source ↗

**Figure 5.** Figure 5: a) The duplicator with input set to TRUE. b)–i) Evolution of the gadget under ΦwD . The transition from c) to d) follows from Lemma 1 view at source ↗

**Figure 6.** Figure 6: a) The duplicator with input set to FALSE. b)–i) Evolution of the gadget under ΦwD . The transition from c) to d) follows from Lemma 1 view at source ↗

**Figure 7.** Figure 7: Behavior of the OR gadget: a) OR gadget with one input TRUE and one input FALSE. b)–e) Evolution according to w∨. f) OR gadget with both inputs TRUE. g)–j) Evolution according to w∨. The case with both inputs FALSE is trivial. The case with inputs FALSE and TRUE is symmetrical to TRUE and FALSE. 8. Nguyen, V.X., Xiao, G., Xu, X.J., Wu, Q., Xia, C.Y.: Dynamics of opinion formation under majority rules on c… view at source ↗

**Figure 8.** Figure 8: Behavior of the AND gadget: a) AND gadget with one input TRUE and one input FALSE. b)–f) Evolution according to w∧. g) AND gadget with both inputs TRUE. h)–l) Evolution according to w∧. The case with both inputs FALSE is trivial. The case with inputs FALSE and TRUE is symmetrical to TRUE and FALSE view at source ↗

read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper defines local homophily on bicolored graphs and reduces circuit value to connectivity after iterations, establishing P-completeness, though the construction must keep gate subgraphs isolated under global synchronous steps.

read the letter

The main point is that this work introduces a local homophily rule—vertices flip to the majority neighbor color, then connect to same-color neighbors and disconnect from opposite-color ones—and proves that asking whether two designated vertices end up connected after repeated steps is P-complete under logspace reductions. The reduction works by encoding arbitrary Boolean circuits into an initial bicolored graph so that the dynamics compute the circuit output as connectivity between a pair of nodes. This is a direct application of the standard technique for showing hardness of iterative graph processes. The paper does well by keeping the model simple and grounded in adaptive-network ideas while using a familiar logspace reduction from circuit value, which makes the argument easy to follow once the construction is laid out. The citation pattern looks standard and does not rely on self-referential tricks. The soft spot is exactly the isolation question raised in the stress test. Because every vertex updates color and every edge rewires in each global round, it is possible for color flips or new edges to leak across intended gate boundaries and create shortcuts or extra stabilizations that do not correspond to the circuit. The construction therefore has to include explicit separation—fixed-color buffers, layered timing, or initial edge patterns that prevent cross-talk—while still remaining logspace-constructible. If the full proof supplies those mechanisms and verifies they survive the simultaneous updates, the reduction is fine; if the details are thin or rely on the dynamics magically staying local, the claim weakens. This paper is aimed at researchers who study computational complexity of network dynamics and local iterative processes. A reader already comfortable with P-completeness reductions on graphs will extract the technique and the new process definition. It deserves a serious referee because the claim is precise, the method is standard, and the only real question is whether the isolation holds in the explicit construction.

Referee Report

2 major / 2 minor

Summary. The paper defines a local homophily transformation on bicolored graphs in which each vertex adopts the majority color among its neighbors while edges are added between same-color neighbors and removed between opposite-color neighbors. It claims to encode arbitrary Boolean circuits as initial bicolored graphs such that iterative application of the transformation makes a designated pair of vertices connected precisely when the circuit evaluates to true, and proves that deciding this connectivity question is P-complete under logspace reductions.

Significance. If the simulation is valid, the result supplies a new natural P-complete problem arising from a local majority-plus-homophily dynamics, extending the catalog of P-complete graph processes and linking adaptive-network models to complexity theory. The logspace reduction from a standard P-complete problem (presumably CVP) is a positive feature when the construction is fully verified.

major comments (2)

[Section 3] The reduction construction (Section 3 on circuit simulation): the manuscript must supply an explicit argument that simultaneous majority updates and global rewiring do not create cross-talk or shortcuts between intended gate subgraphs. Because every vertex and edge can change in each global step, color flips or new same-color edges could propagate across gate boundaries and alter the final connectivity of the output pair independently of the circuit value; without a lemma isolating the subgraphs (e.g., via fixed-color buffers, timing layers, or asynchronous scheduling), the claimed equivalence between circuit evaluation and connectivity fails.
[Section 4] The logspace reduction (Section 4): the initial bicolored graph must be shown to be logspace-constructible from the circuit description, including the precise placement of vertices, initial colors, and edges that encode gates. The paper should also clarify whether connectivity is checked after a polynomial number of steps, at stabilization, or for some existential number of iterations, and prove that the process remains polynomial-time overall.

minor comments (2)

[Abstract] The abstract states that the simulation and reduction exist but supplies no high-level sketch of the graph encoding; a single sentence describing the key isolation technique would improve readability.
[Section 2] Notation for the transformation (Definition 2.1 or equivalent): the update rule for colors and edges should be stated with a single formal equation or pseudocode block rather than prose only, to facilitate verification of the dynamics.

Simulated Author's Rebuttal

2 responses · 0 unresolved

Thank you for the referee's thorough review and insightful comments on our manuscript. We appreciate the opportunity to clarify and strengthen our arguments. Below, we address each major comment point by point, indicating the revisions we will make.

read point-by-point responses

Referee: [Section 3] The reduction construction (Section 3 on circuit simulation): the manuscript must supply an explicit argument that simultaneous majority updates and global rewiring do not create cross-talk or shortcuts between intended gate subgraphs. Because every vertex and edge can change in each global step, color flips or new same-color edges could propagate across gate boundaries and alter the final connectivity of the output pair independently of the circuit value; without a lemma isolating the subgraphs (e.g., via fixed-color buffers, timing layers, or asynchronous scheduling), the claimed equivalence between circuit evaluation and connectivity fails.

Authors: We acknowledge that the current manuscript lacks an explicit isolation lemma, which is essential for rigorously proving that the circuit simulation is not affected by unintended interactions. In the revised manuscript, we will introduce a dedicated lemma in Section 3 that demonstrates the isolation of gate subgraphs. This will be achieved by incorporating fixed-color buffer vertices and layered timing mechanisms that prevent color propagation and edge rewiring from crossing gate boundaries. We will prove that under these constructions, the dynamics within each gate subgraph proceed independently, preserving the intended Boolean computation. revision: yes
Referee: [Section 4] The logspace reduction (Section 4): the initial bicolored graph must be shown to be logspace-constructible from the circuit description, including the precise placement of vertices, initial colors, and edges that encode gates. The paper should also clarify whether connectivity is checked after a polynomial number of steps, at stabilization, or for some existential number of iterations, and prove that the process remains polynomial-time overall.

Authors: We agree that additional details are needed to fully establish the logspace reduction. In the revision, we will explicitly describe the logspace construction: vertices and edges are placed according to a systematic enumeration of the circuit's gates and wires, which can be done by a logspace transducer since it involves only local copying and indexing of the input circuit description. Initial colors are assigned based on gate types in a straightforward manner. Regarding the timing, connectivity between the designated pair is checked after a polynomial number of steps, specifically after O(depth of the circuit) iterations, which suffices for the signal to propagate through the simulated circuit. We will add a proof that the overall decision procedure is in P, as the graph size is polynomial in the circuit size, each transformation step is computable in polynomial time, and the number of steps is polynomial. revision: yes

Circularity Check

0 steps flagged

No circularity: standard logspace reduction from known P-complete problem via explicit circuit simulation construction

full rationale

The paper's central result is a P-completeness proof obtained by exhibiting a logspace-constructible family of bicolored graphs that encode arbitrary Boolean circuits such that the iterative local homophily process (majority-color update plus homophily rewiring) connects a designated pair of vertices exactly when the circuit evaluates to true. This is a conventional reduction technique that does not rely on any self-definitional equations, fitted parameters renamed as predictions, or load-bearing self-citations. The derivation chain consists of (1) defining the local homophily operator, (2) constructing the encoding graph from the circuit instance, and (3) proving that the dynamics preserve the circuit semantics; none of these steps reduces to the target claim by construction. The result is therefore self-contained against external benchmarks (the standard Circuit Value Problem) and receives the default non-circularity finding.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The central claim rests on the newly introduced local homophily process and the standard complexity fact that Boolean circuit evaluation is P-complete; no free parameters are fitted and no new entities beyond the process definition are postulated.

axioms (1)

standard math Boolean circuit evaluation is P-complete under logspace reductions
Standard result in complexity theory invoked as the source problem for the reduction.

invented entities (1)

local homophily transformation no independent evidence
purpose: A local update rule on bicolored graphs combining majority color adoption with color-dependent edge addition and removal
Newly defined process in the paper with no independent empirical or prior theoretical validation provided in the abstract.

pith-pipeline@v0.9.0 · 5384 in / 1235 out tokens · 66197 ms · 2026-05-08T15:14:51.071357+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

10 extracted references · 10 canonical work pages

[1]

In: Proceedings of the 22nd International Conference on Distributed Computing and Networking

Cruciani, E., Mimun, H.A., Quattropani, M., Rizzo, S.: Phase transitions of the k- majority dynamics in a biased communication model. In: Proceedings of the 22nd International Conference on Distributed Computing and Networking. pp. 146–155 (2021)

work page 2021
[2]

Oxford university press (1995)

Greenlaw, R., Hoover, H.J., Ruzzo, W.L.: Limits to parallel computation: P- completeness theory. Oxford university press (1995)

work page 1995
[3]

Journal of the Royal Society Interface5(20), 259–271 (2008)

Gross, T., Blasius, B.: Adaptive coevolutionary networks: a review. Journal of the Royal Society Interface5(20), 259–271 (2008)

work page 2008
[4]

Physical Re- view E-Statistical, Nonlinear, and Soft Matter Physics77(1), 016102 (2008)

Kozma, B., Barrat, A.: Consensus formation on adaptive networks. Physical Re- view E-Statistical, Nonlinear, and Soft Matter Physics77(1), 016102 (2008)

work page 2008
[5]

ACM Sigact News7(1), 18–20 (1975)

Ladner, R.E.: The circuit value problem is log space complete for p. ACM Sigact News7(1), 18–20 (1975)

work page 1975
[6]

In: Proceedings of the 2025 SIAM International Conference on Data Mining (SDM)

Loveland, D., Koutra, D.: Unveiling the impact of local homophily on gnn fair- ness: In-depth analysis and new benchmarks. In: Proceedings of the 2025 SIAM International Conference on Data Mining (SDM). pp. 608–617. SIAM (2025)

work page 2025
[7]

McPherson, M., Smith-Lovin, L., Cook, J.M.: Birds of a feather: Homophily in social networks. Annual review of sociology27(1), 415–444 (2001) Local Homophily on Bicolored Graphs isP-complete 13 1 2 3 4 5 6 a) 1 2 3 4 5 6 b) 1 2 3 4 5 6 c) 1 2 3 4 5 6 d) 1 2 3 4 5 6 e) 1 2 3 4 5 6 f) 1 2 3 4 5 6 g) 1 2 3 4 5 6 h) 1 2 3 4 5 6 i) 1 2 3 4 5 6 j) Fig.7: Behavi...

work page 2001
[8]

Scientific reports10(1), 456 (2020)

Nguyen, V.X., Xiao, G., Xu, X.J., Wu, Q., Xia, C.Y.: Dynamics of opinion for- mation under majority rules on complex social networks. Scientific reports10(1), 456 (2020)

work page 2020
[9]

Computers & Mathematics with Applications65(10), 1645–1664 (2013)

Sayama, H., Pestov, I., Schmidt, J., Bush, B.J., Wong, C., Yamanoi, J., Gross, T.: Modeling complex systems with adaptive networks. Computers & Mathematics with Applications65(10), 1645–1664 (2013)

work page 2013
[10]

Talaga, S., Nowak, A.: Homophily as a process generating social networks: In- sights from social distance attachment model. Journal of Artificial Societies and So- cial Simulation23(2), 6 (2020).https://doi.org/10.18564/jasss.4252,http: //jasss.soc.surrey.ac.uk/23/2/6.html A Full Behavior of the Gates This appendix provides figures illustrating the full b...

work page doi:10.18564/jasss.4252 2020

[1] [1]

In: Proceedings of the 22nd International Conference on Distributed Computing and Networking

Cruciani, E., Mimun, H.A., Quattropani, M., Rizzo, S.: Phase transitions of the k- majority dynamics in a biased communication model. In: Proceedings of the 22nd International Conference on Distributed Computing and Networking. pp. 146–155 (2021)

work page 2021

[2] [2]

Oxford university press (1995)

Greenlaw, R., Hoover, H.J., Ruzzo, W.L.: Limits to parallel computation: P- completeness theory. Oxford university press (1995)

work page 1995

[3] [3]

Journal of the Royal Society Interface5(20), 259–271 (2008)

Gross, T., Blasius, B.: Adaptive coevolutionary networks: a review. Journal of the Royal Society Interface5(20), 259–271 (2008)

work page 2008

[4] [4]

Physical Re- view E-Statistical, Nonlinear, and Soft Matter Physics77(1), 016102 (2008)

Kozma, B., Barrat, A.: Consensus formation on adaptive networks. Physical Re- view E-Statistical, Nonlinear, and Soft Matter Physics77(1), 016102 (2008)

work page 2008

[5] [5]

ACM Sigact News7(1), 18–20 (1975)

Ladner, R.E.: The circuit value problem is log space complete for p. ACM Sigact News7(1), 18–20 (1975)

work page 1975

[6] [6]

In: Proceedings of the 2025 SIAM International Conference on Data Mining (SDM)

Loveland, D., Koutra, D.: Unveiling the impact of local homophily on gnn fair- ness: In-depth analysis and new benchmarks. In: Proceedings of the 2025 SIAM International Conference on Data Mining (SDM). pp. 608–617. SIAM (2025)

work page 2025

[7] [7]

McPherson, M., Smith-Lovin, L., Cook, J.M.: Birds of a feather: Homophily in social networks. Annual review of sociology27(1), 415–444 (2001) Local Homophily on Bicolored Graphs isP-complete 13 1 2 3 4 5 6 a) 1 2 3 4 5 6 b) 1 2 3 4 5 6 c) 1 2 3 4 5 6 d) 1 2 3 4 5 6 e) 1 2 3 4 5 6 f) 1 2 3 4 5 6 g) 1 2 3 4 5 6 h) 1 2 3 4 5 6 i) 1 2 3 4 5 6 j) Fig.7: Behavi...

work page 2001

[8] [8]

Scientific reports10(1), 456 (2020)

Nguyen, V.X., Xiao, G., Xu, X.J., Wu, Q., Xia, C.Y.: Dynamics of opinion for- mation under majority rules on complex social networks. Scientific reports10(1), 456 (2020)

work page 2020

[9] [9]

Computers & Mathematics with Applications65(10), 1645–1664 (2013)

Sayama, H., Pestov, I., Schmidt, J., Bush, B.J., Wong, C., Yamanoi, J., Gross, T.: Modeling complex systems with adaptive networks. Computers & Mathematics with Applications65(10), 1645–1664 (2013)

work page 2013

[10] [10]

Talaga, S., Nowak, A.: Homophily as a process generating social networks: In- sights from social distance attachment model. Journal of Artificial Societies and So- cial Simulation23(2), 6 (2020).https://doi.org/10.18564/jasss.4252,http: //jasss.soc.surrey.ac.uk/23/2/6.html A Full Behavior of the Gates This appendix provides figures illustrating the full b...

work page doi:10.18564/jasss.4252 2020