Local complementation of a graph G on vertex v is an operation that results in a new graph G*v, where the neighborhood of v is complemented. Two graph are locally equivalent if one can be reached from the other one through local complementation. It was previously established that recognizing locally equivalent graphs can be done in 𝒪(n⁴) time. We sharpen this result by proving it can be decided in 𝒪(log²(n)) parallel time with n^{𝒪(1)} processors. As a second contribution, we introduce the Local Complementation Problem, a decision problem that captures the complexity of applying a sequence of local complementations. Given a graph G, a sequence of vertices s, and a pair of vertices u,v, the problem asks whether the edge (u,v) is present in the graph obtained after applying local complementations according to s. Despite its simplicity, it is proven to be {𝐏}-complete, therefore it is unlikely to be efficiently parallelizable. Finally, it is conjectured that Local Complementation Problem remains {𝐏}-complete when restricted to circle graphs.

In this article we investigate the computational complexity of predicting two dimensional freezing majority cellular automata with states { − 1 , + 1 } , where the local interactions are based on an L-shaped neighborhood structure. In these automata, once a cell reaches state + 1 , it remains fixed in that state forever, while cells in state − 1 update to the most represented state among their neighborhoods. We consider L-shaped neighborhoods, which mean that the vicinity of a given cell c consists in a subset of cells in the north and east of c . We focus on the prediction problem, a decision problem that involves determining the state of a given cell after a given number of time-steps. We prove that when restricted to the simplest L-shaped neighborhood, consisting of the central cell and its nearest north and east neighbors, the prediction problem belongs to NC , meaning it can be solved efficiently in parallel. We generalize this result for any L-shaped neighborhood of size two. On the other hand, for other L-shaped neighborhoods, the problem becomes P -Complete, indicating that the problem might be inherently sequential.