DROPS

Document

DOI: 10.4230/LIPIcs.WG.2026.13

Is Graph Local Complementation Inherently Sequential?

Authors: Pablo Concha-Vega

Published in: LIPIcs, Volume 376, 52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026)

Abstract

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.

Cite as

Pablo Concha-Vega. Is Graph Local Complementation Inherently Sequential?. In 52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 376, pp. 13:1-13:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{conchavega:LIPIcs.WG.2026.13,
  author =	{Concha-Vega, Pablo},
  title =	{{Is Graph Local Complementation Inherently Sequential?}},
  booktitle =	{52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026)},
  pages =	{13:1--13:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-430-7},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{376},
  editor =	{Goedgebeur, Jan and Rz\k{a}\.{z}ewski, Pawe{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WG.2026.13},
  URN =		{urn:nbn:de:0030-drops-261798},
  doi =		{10.4230/LIPIcs.WG.2026.13},
  annote =	{Keywords: Local complementation, P-completeness, vertex-minors, graph transformations}
}

Search Results

Documents authored by Concha-Vega, Pablo

Is Graph Local Complementation Inherently Sequential?

Abstract

Cite as

Thanks for your feedback!

Could not send message