Local complementation

In graph theory, local complementation (also known as vertex inversion) is an operation on a graph that toggles adjacencies among the neighbours of a chosen vertex, while all other adjacencies remain unchanged. Despite its simple definition, it preserves interesting properties and generates a complex equivalence relation. The operation was introduced by Anton Kotzig and later studied in depth by André Bouchet and Von-Der-Flaass.

Formally, the local complementation of a simple undirected graph ${\displaystyle G}$ at a vertex ${\displaystyle v}$ is an operation that produces a new graph, denoted by ${\displaystyle G\star v}$. This operation is defined by replacing the subgraph of ${\displaystyle G}$ induced by ${\displaystyle N_{G}(v)}$ with its complementary subgraph. In other words, two distinct vertices ${\displaystyle x}$ and ${\displaystyle y}$ are adjacent in the graph ${\displaystyle G\star v}$ when exactly one of the following holds:

1. vertices ${\displaystyle x}$ and ${\displaystyle y}$ are adjacent in ${\displaystyle G}$; or
2. both vertices ${\displaystyle x}$ and ${\displaystyle y}$ are neighbours of ${\displaystyle v}$ in ${\displaystyle G}$.

Two graphs are said to be locally equivalent if one can be obtained from the other through a sequence of local complementations. This defines an equivalence relation on graphs, whose equivalence classes are known as local equivalence classes. For example, the star graph and complete graph on ${\displaystyle n}$ vertices are locally equivalent, and they form a local equivalence class. The local equivalence classes on graphs with up to 12 vertices has been computed.^[1] The size of a local equivalence class is at most ${\displaystyle 3^{n}}$, and this collection of graphs can be enumerated efficiently.

The Robertson–Seymour theorem states that the graph minor relation is a well-quasi ordering. It was proved in a series of twenty papers spanning over 500 pages from 1983 to 2004. The algorithmic consequences are vast - together with an efficient algorithm for graph minor testing, the result provides efficient algorithms for solving a range of computational problems where the optimal value is monotonic in the graph minor relation.

Local complementations are central to the vertex-minor relation, which shares many similarities with the graph minor relation. Better understanding of the local complementation operation could extend the Robertson–Seymour theorem to prove that the vertex-minor relation is also a well-quasi ordering.

For a given the graph state ${\displaystyle |G\rangle }$, the action of the local Clifford operation is equivalent^[2] to the local complementation transformation on the graph ${\displaystyle G}$. The study of graph states that are locally equivalent is relevant to building quantum circuits in measurement based quantum computing (MBQC)^[1]

Similarly, local complementation is also related to state preparation in photonic quantum computing (PQC).

1. The local complement operation is self inverse; that is, ${\displaystyle (G\star v)\star v=G}$.
2. Local complementations commute only when vertices are non-adjacent; that is, ${\displaystyle (G\star v)\star w=(G\star w)\star v}$ unless ${\displaystyle vw\in E(G)}$.
3. Connected components are preserved by the local complementation operation, so it is common analyse each component of the graph independently. So without loss of generality, all graphs will be assumed to be connected.
4. All locally equivalent graphs can be reached after a sequence of at most ${\displaystyle \max(n+1,10n/9)}$ local complementations^[3].
5. Locally equivalent trees are isomorphic (Mulder's conjecture), and there exists a simple expression to count such trees.^[4]
6. If a graph is locally equivalent to a tree, it has a subgraph isomorphic to that tree.^[5]
7. If a graph is locally equivalent to the cycle graph, it contains a Hamiltonian cycle.^[5]
8. If a graph is locally equivalent to its complement, it is self-complementary.^[5]
9. The number of essentially different ways of transforming one graph into another via local complementation is ${\displaystyle 0,3,6}$ or ${\displaystyle 2^{k}}$ for some ${\displaystyle k\geq 0}$.^[5]
10. Any class of locally equivalent distance-hereditary graphs is equal to the class of the circle graphs of the Euler tours of some 4-regular graph.
11. Locally equivalent graphs have the same rank-width.
12. Counting locally equivalent graphs is #P-complete.^[6]
13. Determining the minimum degree that can be reached by means of local complementation is NP-complete and APX-hard, and can be computed by an ${\displaystyle {\mathcal {O}}^{*}(1.938^{n})}$ algorithm.^[7][8]
14. Determining the minimum total edge weight by means of local complementation is NP-complete.^[9]
15. Determining the minimum number of edges by means of local complementation is likely NP-complete.

Local complementations do not commute for adjacent vertices, motivating the following operation that performs complementations at adjacent vertices.

For adjacent vertices ${\displaystyle x}$ and ${\displaystyle y}$, the pivot operation (also historically known as an edge complementation) is defined as$${\displaystyle G\wedge xy=G\star x\star y\star x.}$$It can be shown that ${\displaystyle G\star x\star y\star x=G\star y\star x\star y}$, and hence the pivot operation is well defined. Alternatively, the graph ${\displaystyle G\wedge xy}$ can be obtained from ${\displaystyle G}$ by toggling adjacencies between every pair of vertices in two different sets among ${\displaystyle N_{G}(x)-(N_{G}(y)\cup {y})}$, ${\displaystyle N_{G}(x)\cap N_{G}(y)}$ and ${\displaystyle N_{G}(y)-(N_{G}(x)\cup {x})}$ then switching the labels ${\displaystyle x}$ and ${\displaystyle y}$. The pivot operation satisfies the identities ${\displaystyle G\wedge xy\wedge xy=G}$ and ${\displaystyle G\wedge xy\wedge yz=G\wedge xz}$^[10].

Two graphs are said to be pivot equivalent if one can be obtained from the other through a sequence of pivot operations. Since pivot operations consist of local complementation operations, pivot equivalent graphs are locally equivalent. The converse is true for bipartite graphs^[3], but is not generally true. If ${\displaystyle G}$ and ${\displaystyle H}$ are pivot equivalent graphs, there are pairwise disjoint edges ${\displaystyle e_{1},e_{2},\dots ,e_{k}}$ such that ${\displaystyle G\wedge e_{1}\wedge e_{2}\dots \wedge e_{k}=H}$. Fon-Der-Flass proved that if graphs ${\displaystyle G}$ and ${\displaystyle H}$ are locally equivalent, they are pivot equivalent to some ${\displaystyle G'}$ and ${\displaystyle H'}$ respectively such that ${\displaystyle G'*v_{1}v_{2}\dots v_{k}=H'}$ and ${\displaystyle \{v_{1},v_{2},\dots ,v_{k}\}}$ is an independent set in ${\displaystyle G'}$ and ${\displaystyle H'}$^[11].

The size of a pivot equivalence class is at most ${\displaystyle 2^{n}}$, and this collection of graphs can be enumerated efficiently.

Pivot equivalence has been studied using even binary delta-matroids^[12].

As a graph undergoes local complementation, its adjacency matrix changes in a well defined way. In particular, the entries that change are exactly some sub-matrix (excluding the main diagonal). Hence, it may be natural to study the local complementation operation using linear algebra.

For a graph ${\displaystyle G}$ with vertex set ${\displaystyle V}$, the cut-rank function (also historically known as the connectivity function) is denoted ${\textstyle \rho _{G}:{\mathcal {P}}(V)\to \mathbb {N} }$. It is defined over the vertex subsets ${\displaystyle X\subseteq V}$ such that ${\displaystyle \rho _{G}(X)}$ is the rank of the bi-adjacency matrix of the partition ${\displaystyle (X,V-X)}$, defined over the finite field GF(2). That is, the rank of the ${\displaystyle X\times (V-X)}$ binary matrix ${\displaystyle M}$ where ${\displaystyle M_{uv}=1}$ when ${\displaystyle uv}$ is an edge in ${\displaystyle G}$. Intuitively, ${\displaystyle \rho _{G}(X)}$ is a measure of how complex the connectivity is between ${\displaystyle X}$ and the remaining vertices.

Since the rank of a matrix is preserved by elementary row and column operations, a straightforward argument shows that locally equivalent graphs have identical cut-rank functions. However, the converse is not true - a counterexample can be constructed using labelled Petersen graphs. It is known that bipartite graphs with identical cut-rank functions are pivot-equivalent^[13], and so locally equivalent bipartite graphs are also pivot-equivalent.

The cut-rank function is submodular since it can be shown that ${\displaystyle \rho _{G}(X)+\rho _{G}(Y)\geq \rho _{G}(X\cup Y)+\rho _{G}(X\cap Y)}$ for any vertex set ${\displaystyle X}$ and ${\displaystyle Y}$. However, it is not monotone.

The cut-rank can be considered 'most interesting' when it is either rank 1 or full rank. Since the cut-rank is invariant over local complementation, so are the sets with a particular cut-rank. The sets of rank 1 are studied using canonical split decompositions in a later section. Here, we define a local set as a vertex set which does not have full cut-rank.

Define $${\displaystyle \mathrm {Odd} _{G}(X)=\{v\in V(G)\mid |N(v)\cap X|=1{\bmod {2}}\}.}$$A set of vertices ${\displaystyle S}$ is local in ${\displaystyle G}$ if ${\displaystyle S=X\cup \mathrm {Odd} _{G}(X)}$ for some subset ${\displaystyle X\subseteq V(G)}$. Now if ${\displaystyle S}$ is local in ${\displaystyle G}$, it is also local in any graph locally equivalent to ${\displaystyle G}$. Local sets can equivalently be defined as the sets of vertices which do not have full cut-rank (i.e. the sets ${\displaystyle S}$ where ${\displaystyle \rho _{G}(S)<|S|}$). Intuitively, a local set is some linear combination of the closed neighbourhoods of ${\displaystyle G}$. Local sets are used to study the degrees of vertices in ${\displaystyle G}$.^[14]

This invariant may be a helpful tool to quickly show that graphs are not locally equivalent. However, there are graphs with the same local sets which are not locally equivalent, since there are graphs with identical cut-rank functions which are not locally equivalent.^[15]

The richest description of a class of locally equivalent graphs is an extension of the local sets idea, involving a linear algebra structure over the Klein four-group. Each locally equivalent graph, equipped with two specific vectors, corresponds to some graphic presentations of the same totally isotropic subspace.

Let ${\displaystyle K_{4}}$ be the Klein four-group. A vector ${\displaystyle \mathbf {a} \in K_{4}^{n}}$ is said to be complete if ${\displaystyle \mathbf {a} _{i}}$ is nonzero for every ${\displaystyle 1\leq i\leq n}$. Two vectors ${\displaystyle \mathbf {a} ,\mathbf {b} \in K_{4}^{n}}$ are said to be supplementary if ${\displaystyle \mathbf {a} _{i}}$ and ${\displaystyle \mathbf {b} _{i}}$ are nonzero and distinct for every ${\displaystyle 1\leq i\leq n}$. For a set ${\displaystyle S}$, define ${\displaystyle \mathbf {a} [S]}$ as the vector where ${\displaystyle \mathbf {a} [S]_{i}=a_{i}}$ if ${\displaystyle i\in S}$, and ${\displaystyle \mathbf {a} [S]_{i}=0}$ otherwise.

A subspace ${\displaystyle L}$ of ${\displaystyle K_{4}^{n}}$ is called a totally isotropic subspace if ${\displaystyle \dim(L)=\dim(K_{4}^{n})/2=n}$, and every two complete vectors in ${\displaystyle L}$ are not supplementary.

A graphic presentation of a totally isotropic subspace ${\displaystyle L}$ is a triple ${\displaystyle (G,\mathbf {a} ,\mathbf {b} )}$ where ${\displaystyle G}$ is a simple graph on the vertex set ${\displaystyle V=\{1,\dots ,n\}}$ and ${\displaystyle \mathbf {a} }$ and ${\displaystyle \mathbf {b} }$ are supplementary vectors of ${\displaystyle K_{4}^{n}}$, such that ${\displaystyle L}$ is spanned by the set $${\displaystyle \{\mathbf {a} [N(v)]+\mathbf {b} [\{v\}]\mid v\in V\}.}$$For a fixed ${\displaystyle L}$, there is a one-to-one correspondence between every graphic presentation ${\displaystyle (G,\mathbf {a} ,\mathbf {b} )}$ and every complete vector ${\displaystyle \mathbf {a} }$ where ${\displaystyle \mathbf {a} \not \in L}$, the vectors ${\displaystyle \mathbf {a} }$ here are known are Eulerian vectors. Furthermore, if ${\displaystyle (G,\mathbf {a} ,\mathbf {b} )}$ is a graphic presentation of ${\displaystyle L}$, so is $${\displaystyle (G\star v,\mathbf {a} +\mathbf {b} [\{v\}],\mathbf {b} +\mathbf {a} [N(v)])}$$ and $${\displaystyle (G\wedge vw,\mathbf {a} [V\setminus \{v,w\}]+\mathbf {b} [\{v,w\}],\mathbf {a} [\{v,w\}]+\mathbf {b} [V\setminus \{v,w\}]).}$$The fundamental graphs of ${\displaystyle L}$ form a local equivalence class. These facts leads to important results about determining local equivalence and locally equivalent class sizes, which is discussed in the next 2 sections.

This structure can be considered as an extension of the local sets structure, since ${\displaystyle L=\{\mathbf {a} [\mathrm {Odd} _{G}(X)]+\mathbf {b} [X]\mid X\subseteq V\}}$, and when ${\displaystyle \mathbf {a} =\mathbf {b} }$, ${\displaystyle L=\{\mathbf {a} [S]\mid S{\text{ is local in }}G\}}$.^[16]

The following characterisations of locally equivalent graphs are straightforward results using totally isotropic subspaces. This leads to a efficient algorithm to recognise locally equivalent graphs.

Let ${\displaystyle G_{1}}$ and ${\displaystyle G_{2}}$ be simple graphs and fix supplementary vectors ${\displaystyle \mathbf {a} _{1}}$ and ${\displaystyle \mathbf {b} _{1}}$. he graphs ${\displaystyle G_{1}}$ and ${\displaystyle G_{2}}$ are locally equivalent if and only if there are supplementary vectors ${\displaystyle \mathbf {a} _{2}}$ and ${\displaystyle \mathbf {b} _{2}}$ such that ${\displaystyle (G_{1},\mathbf {a} _{1},\mathbf {b} _{1})}$ and ${\displaystyle (G_{2},\mathbf {a} _{2},\mathbf {b} _{2})}$ are graphic presentations of the same totally isotropic subspace. The existence of such vectors ${\displaystyle \mathbf {a} _{2}}$ and ${\displaystyle \mathbf {b} _{2}}$ can be determined in ${\displaystyle {\mathcal {O}}(n^{3})}$ by solving a system of linear equations^[17]. A modification to this algorithm can, with the same time complexity, recover a sequence of at most ${\displaystyle 3n/2}$ local complementations transforming ${\displaystyle G_{1}}$ into ${\displaystyle G_{2}}$^[18].

An equivalent characterisation can be formulated using vertex sets. Let ${\displaystyle N_{1}}$ and ${\displaystyle N_{2}}$ denote the neighbourhood functions of ${\displaystyle G_{1}}$ and ${\displaystyle G_{2}}$ respectively. Then graphs ${\displaystyle G_{1}}$ and ${\displaystyle G_{2}}$ are locally equivalent if and only if there are vertex subsets ${\displaystyle X,Y,Z,T}$ such that for every pair of vertices ${\displaystyle v,w}$, $${\displaystyle |X\cap N_{1}(v)\cap N_{2}(w)|+|Y\cap N_{1}(v)\cap \{w\}|+|Z\cap N_{2}(w)\cap \{v\}|+|T\cap \{v,w\}|\equiv 0{\pmod {2}},}$$and the symmetric difference of ${\displaystyle X\cap T}$ with ${\displaystyle Y\cap Z}$ is the entire vertex set.^[17]

The global interlace polynomial (also known as the Tutte-Martin polynomial), is a polynomial that corresponds to a simple graph ${\displaystyle G}$. It is defined recursively as$${\displaystyle Q(G;x)={\begin{cases}Q(G-u;x)+Q((G*u)-u;x)+Q((G\wedge uv)-u;x)&uv\in E(G)\\x^{n}&G{\text{ has no edges and }}n{\text{ vertices}}\end{cases}}}$$Now if ${\displaystyle G}$ and ${\displaystyle H}$ are locally equivalent, ${\displaystyle Q(G,x)=Q(H,x)}$ for any ${\displaystyle x}$^[15]. Additionally,

• ${\displaystyle Q(G,2)}$ is a multiple of the number of graphs locally equivalent to ${\displaystyle G}$. In particular, if ${\displaystyle G}$ is a fundamental graph of a totally isotropic subspace ${\displaystyle L}$, this gives the number of Eulerian vectors in ${\displaystyle L}$.
• ${\displaystyle Q(G;4)/2^{n}}$ is the number of induced Eulerian subgraphs in ${\displaystyle G}$. (An Eulerian graph contains only vertices of even degree).

The polynomial has closed-form formulas in certain cases:

• The path graphs ${\displaystyle P_{n}}$ have the closed form ${\displaystyle Q(P_{n};x)=\lambda _{1}\left(1+{\sqrt {1+x}}\right)^{n-1}+\lambda _{2}\left(1-{\sqrt {1+x}}\right)^{n-1}}$ where ${\displaystyle \lambda _{1}=x/2+x/{\sqrt {1+x}}}$ and ${\displaystyle \lambda _{2}=x/2-x/{\sqrt {1+x}}}$.
• More generally, a tree ${\displaystyle T}$ has the global interlace polynomial ${\textstyle Q(T;x)=\sum _{k\geq 0}\Phi _{k}(T)2^{n-2k}x^{k}}$, where ${\displaystyle \Phi _{k}(T)}$ is the number of matchings of size ${\displaystyle k}$ in ${\displaystyle T}$.
• The cycle graphs ${\displaystyle C_{n}}$ have the closed form ${\displaystyle Q(C_{n};2)=(1+{\sqrt {3}})^{n}+(1-{\sqrt {3}})^{n}-4(2^{n-1}+(-1)^{n})/3}$^[15].

An equivalent definition of the global interlace polynomial involves a summation over subsets of vertex sets. Let the graph ${\displaystyle G}$ have the adjacency matrix ${\displaystyle A}$ over the binary field. For a vertex set ${\displaystyle S\in V(G)}$, write ${\displaystyle A[S]}$ to denote the ${\displaystyle S\times S}$ sub-matrix of ${\displaystyle A}$. Let ${\displaystyle I_{X}}$ be the ${\displaystyle V(G)\times V(G)}$ diagonal matrix over the binary field such that the ${\displaystyle (v,v)}$-entry is 1 when ${\displaystyle v\in X}$, and 0 otherwise. The global interlace polynomial can equivalently be defined as$${\displaystyle Q(G;x)=\sum _{R\subseteq S\subseteq V(G)}(x-2)^{\mathrm {nullity} ((A+I_{R})[S])}.}$$There are some interesting similarities to the canonical Tutte polynomial. In particular, the recurrence looks similar to the deletion-contraction formula, and both polynomials can be formulated as a sum of terms raised to the power of a matrix rank. Isomorphic graphs have the same Tutte polynomial, while locally equivalent or isomorphic graphs have the same global interlace polynomial.

A split of a graph ${\displaystyle G}$ is a partition of its vertex set ${\displaystyle (X,Y)}$ such that ${\displaystyle |X|,|Y|\geq 2}$ and ${\displaystyle \rho _{G}(X)=1}$. This happens exactly when the connectivity between ${\displaystyle X}$ and ${\displaystyle Y}$ is a complete bipartite graph, and complete bipartite graphs have a simple known structure over local complementation.

If a graph admits a split, it can be built by the 1-join of two graphs. The 1-join of two graphs ${\displaystyle G_{1}}$ and ${\displaystyle G_{2}}$ with marker vertices ${\displaystyle v_{1}\in V(G_{1})}$ and ${\displaystyle v_{2}\in V(G_{2})}$ is defined to be the graph obtained from the disjoint union of ${\displaystyle G_{1}-v_{1}}$ and ${\displaystyle G_{2}-v_{2}}$ by adding an edge between every neighbour of ${\displaystyle v_{1}}$ in ${\displaystyle G_{1}}$ and every neighbour of ${\displaystyle v_{2}}$ in ${\displaystyle G_{2}}$.

The canonical split decomposition can be constructed using the following procedure: Start from a set ${\displaystyle \{G\}}$ consisting of a single graph. Repeatedly pick a graph ${\displaystyle H}$ from this set that admits a split. Then replace ${\displaystyle H}$ with ${\displaystyle 2}$ smaller graphs whose 1-join reconstructs ${\displaystyle H}$. This process is applied only when ${\displaystyle H}$ is neither a complete graph nor a star. The set now contains all induced prime subgraphs of ${\displaystyle G}$ along with some star graphs and cliques. Lastly, associate a tree by having one node for each graph in the resulting set and adding edges between corresponding marker vertices.^[4]

The canonical split decomposition is unique and has preserves important structural properties over local complementation.

1. The rank-width of ${\displaystyle G}$ is the maximum rank-width of all prime induced subgraphs.

Local complementation gives rise to several derived operations that play a central role in graph minor theory. A graph ${\displaystyle H}$ is a vertex-minor (also historically known as l-reduction or i-minor) of a graph ${\displaystyle G}$ if ${\displaystyle H}$ is an induced subgraph of a graph locally equivalent to ${\displaystyle G}$.^[19]

Deciding whether ${\displaystyle H}$ is a vertex-minor of ${\displaystyle G}$ for two input graphs ${\displaystyle G}$ and ${\displaystyle H}$ is NP-complete, even if ${\displaystyle H}$ is a complete graph and ${\displaystyle G}$ is a circle graph.^[20]. However, for each fixed circle graph ${\displaystyle H}$, there is an ${\displaystyle {\mathcal {O}}(n^{3})}$-time algorithm to decide whether an input ${\displaystyle n}$-vertex graph ${\displaystyle G}$ contains a vertex-minor isomorphic to ${\displaystyle H}$^[21]. Every prime graph with at least 6 vertices has a prime vertex-minor with one less vertex.^[19]

Distance-hereditary graphs are exactly the graphs with no vertex-minor isomorphic to ${\displaystyle C_{5}}$^[22], and exactly the graphs which are the vertex-minor of a tree^[23].

A graph ${\displaystyle H}$ is a pivot-minor of a graph ${\displaystyle G}$ if ${\displaystyle H}$ is an induced subgraph of a graph pivot-equivalent to ${\displaystyle G}$. Bipartite graphs with the pivot-minor relation are essentially equivalent to binary matroids with the matroid minor relation.

For a circle graph ${\displaystyle G}$, performing a local complementation at ${\displaystyle v}$ corresponds to an graphical transformation of its chord diagram. In particular, the chord diagram of ${\displaystyle G\star v}$ is obtains from the chord diagram of ${\displaystyle G}$ by cutting the circumference by chord representing ${\displaystyle v}$, then reversing one arc^[17][15]. The class of circle graphs are hence closed under local complementation, and they are also closed under taking vertex-minors.