Is Graph Local Complementation Inherently Sequential?
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912594744311808 |
|---|---|
| author | Concha-Vega, Pablo |
| author_facet | Concha-Vega, Pablo |
| contents | 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 on can be reached from the other one through local complementation.
It was previously established that recognizing locally equivalent graphs can be done in $\mathcal{O}(n^4)$ time. We sharpen this result by proving it can be decided in $\mathcal{O}(\log^2(n))$ parallel time with $n^{\mathcal{O}(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$. Regardless it simplicity, it is proven to be $\mathsf{P}$-complete, therefore it is unlikely to be efficiently parallelizable.
Finally, it is conjectured that Local Complementation Problem remains $\mathsf{P}$-complete when restricted to circle graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_24144 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Is Graph Local Complementation Inherently Sequential? Concha-Vega, Pablo Computational Complexity Discrete Mathematics 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 on can be reached from the other one through local complementation. It was previously established that recognizing locally equivalent graphs can be done in $\mathcal{O}(n^4)$ time. We sharpen this result by proving it can be decided in $\mathcal{O}(\log^2(n))$ parallel time with $n^{\mathcal{O}(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$. Regardless it simplicity, it is proven to be $\mathsf{P}$-complete, therefore it is unlikely to be efficiently parallelizable. Finally, it is conjectured that Local Complementation Problem remains $\mathsf{P}$-complete when restricted to circle graphs. |
| title | Is Graph Local Complementation Inherently Sequential? |
| topic | Computational Complexity Discrete Mathematics |
| url | https://arxiv.org/abs/2503.24144 |