Local complementation in undirected graphs

Question

Problem statement

Let $G=(V,E)$ be an undirected graph whose vertices are either black or white. A local complementation of $G$ with respect to a black vertex $v$ consists in:

1. complementing the subgraph induced by $v$ and its neighbours,
2. flipping the colour of each neighbour of $v$ (i.e. black vertices become white and conversely), and finally
3. removing $v$ from $V$.

The goal is to delete the whole graph using only local complementations.

Questions

Given an ordering $\mathcal O$ of the vertices of $V$, can we characterise cases in which $\mathcal O$ allows us (or not) to delete $G$?

Comments

A lot of work on local complementations (or "vertex eliminations" in some papers) concerns itself with algorithmic issues, especially with finding orderings that will work. Note that this differs from my question, since here you don't get to choose an ordering.

Of course, verifying whether an ordering works is easy: keep complementing until you're done or stuck. Finding necessary or sufficient nontrivial structural conditions on $G$ or $\mathcal O$ seems harder. Does this problem ring any bell?

Example

Two different orderings for the same graph; the first one does not work:

http://homepages.ulb.ac.be/~alabarre/local-complementation-1.png

The second one does:

http://homepages.ulb.ac.be/~alabarre/local-complementation-2.png

References

Hannenhalli and Pevzner, starting from page 14, and Hartman and Verbin. All other authors (e.g. Sabidussi) consider variants like using directed graphs, or non-coloured vertices, or complementations which do not modify edges adjacent to $v$. Other authors whose papers I'm currently looking into are Donald J. Rose, Robert Endre Tarjan and François Genest.

Answer 1

Warning. I just realized that my reduction is not good as if a node has two outputs, their will be new edges created between them, so we would need a more complicated gadget. I suspect this to be doable, but as meanwhile the question turned out to have a different motivation (see Parity below), I did not give it much thought.

No, it is not possible to characterize them. Of course it is possible to find some conditions for special cases but do not hope to find any simple/local dependent rule as this problem is P-complete. Below I give a sketch of how to reduce CVP (Circuit Value Problem) to it.

Before I start one simple observation that you did not mention. For every graph with ordered vertices, there is exactly one coloring that deletes the whole graph. This suggests that in the reduction true variables should correspond to certain edges in our graph rather than to colors.

There will be one main gadget that we use, which I tried to depict here with my humbling artistic laziness.

alt text http://dcg.epfl.ch/webdav/site/dcg/users/184485/public/gadget.JPG

Now I'll try to sketch the reduction. To every node of the circuit we will have a corresponding pair of vertices, $v_1$ and $v_2$, which are next to each other in the order. They will be both black and unconnected before we start deleting them if the node is evaluated as TRUE while $v_1$ will be black, $v_2$ white and they will be connected before we start deleting them if the node is evaluated as FALSE. Thus the above gadget is a negation gate.

Note that the color of 3 changes iff our first variable is true. Thus basically we can modify a later part of the graph arbitrarily by using several copies of this gadget. If we combine two gadgets, we can also simulate an AND gate. For this it is enough to show how to have an edge iff two variables are true. Let A, B, C have this order, at the beginning A being black, A being the "4" in two gadgets, the role of "3" played by B and C in the two gadgets. Then after deleting both variables and A, the color of B and C will be unchanged and there will be an edge between iff both variables were true.

I know that this is a lengthy answer and uses complexity instead of some nice combinatorial observations, but I think it helps to show why there can be no simple characterization. Let me know if you have any questions/would like a more detailed exposition.

Parity. If a graph satisfies that every black vertex has an odd degree and every white vertex has an even degree, then it is not possible to delete it. The proof is by induction on the number of vertices. If there is only one vertex, it must be white, thus we are struck. Otherwise, whenever you delete a black vertex, the parity of the degree of all of its neighbors will change as well as their color, thus we are done by applying the induction hypothesis to this graph.

Answer 2

I am not sure whether you realise this, but the problem you pose is closely related to a problem which has been studied quite widely in connection with measurement based quantum computation (MBQC). I apologize in advance if I do a poor job of explaining MBQC. Let me explain the relationship:

In MBQC a quantum state is initially prepared which acts as a resource for quantum computation. Adaptive measurements are made on local subsystems which drive the computation, with the results eventually appearing in the final measurement outcomes.

By far the most studied class of resource states are known as graph states, because each such state is identified with a graph. The graph state $|\psi_G\rangle$ associated with a graph G=(V,E) is stabilized by $X_j \bigotimes_{k\in Nbgh(j)} Z_k$ $\forall j \in V$. By this I mean that $X_j \bigotimes_{k\in Nbgh(j)} Z_k |\psi_G\rangle = |\psi_G\rangle$. I am using X, Y and Z to denote the two dimensional Pauli operators.

The reason for the relationship is that it has been established that Pauli measurements on graph states yield states locally equivalent to other graph states (see section IIIA in quant-ph/0307130). In particular, the graph identifying the graph state resulting from a Y measurement on vertex j of $|\psi_G\rangle$ is related to G by local complementation with respect to j.

Here local the graphs are not colored (though the coloring will come in later), so the definition of local complementation I use here skips step 2 in your definition.

Let me first note here that we can generate a complete basis for the $2^N$ dimensional Hilbert in which an N vertex graph state $|\psi_G\rangle$ is defined can be generated by simply applying various combinations of local Z operations to $|\psi_G\rangle$. Each such state is orthogonal to the others and to $|\psi_G\rangle$.

When measurements are made on a graph state, they potentially have two outcomes, and these are what I will identify with the coloring. In order to make a measurement pattern deterministic, it is necessary to adapt the measurement basis depending on previous measurement outcomes. The way this is done is fairly simple and since we will only be considering Pauli measurements here we only need to consider flipping measurement outcomes. I'll point you to a paper containing a more detailed description of this at the end.

Now, note that a Y measurement on site j anticommutes with $X_j \bigotimes_{k \in Nbgh(j)} Z_k$, which stabilises the graph state. However, we can note that since we are projecting onto the Y basis on site j, $P_Y^\pm X_j \bigotimes_{k \in Nbgh(j)} Z_k |\psi_G\rangle = P_Y^\pm Z_j \bigotimes_{k \in Nbgh(j)} Z_k |\psi_G\rangle$, where $P^\pm_Y$ are the projectors onto the $\pm 1$ eigenstate of Y. So we can use $Z_j \bigotimes_{k \in Nbgh(j)} Z_k$ to calculate the correction operator (see quant-ph/0702212 for more details). So if the Y measurement result is +1, then by applying the operator $Z_j \bigotimes_{k \in Nbgh(j)} Z_k$ to resultant state yields a state equivalent to the result of a measurement result of -1.

Now for the coloring: Imagine identifying black with sites which give a measurement outcome of -1 and white with sites which will result in a measurement outcome of +1. Thus applying our correction operator $Z_j \bigotimes_{k \in Nbgh(j)} Z_k$ should be equivalent to step 2 in your definition of local complementation. Thus a Y measurement followed by a correction in the MBQC model is equivalent to local complementation as described in your question.

Thus, we can adapt your question as an MBQC problem: Given a graph $G$ with corresponding graph state $|\psi_G\rangle$, generate a set of local measurements $M$ which results in a continuous sequence of local complementations. Which if any partial time orderings on $M$ can be deterministically corrected?

Admittedly your question is slightly different, since it only asks whether one specific measurement result is correctable, but I think this should at least point you in a useful direction.

Generating $M$ should be straight forward, though the local operators relating the result of a Y measurement to a graph state (described in quant-ph/0307130) complicate matters: Assume the graph is k-colourable. For each vertex v of colour i, associate with vertex v a Y measurement if the number of neighbours of colour previously assigned a Y measurement basis is even, and assign an X measurement if the number of neighbours assigned an Y measurement is odd. Flip the colour of v if the number of neighbours previously assigned a Y measurement mod 4 is either 2 or 3. Increment through i.

So now that we can generate such a set of measurements, the question is simply which partial time orderings on $M$ can be deterministically corrected?

As it turns out, this problem has been studied in great detail, with the existence of flow or g-flow shown to be a sufficient (and in some cases necessary condition). I suspect is it is a necessary condition for this particular problem, but I'm not sure. G-flow is defined in quant-ph/0702212, though quant-ph/0611284 may also be of interest to you.

It is of course possible I have made a slip somewhere in my logic, but if not I believe g-flow may be what you are looking for (though may perhaps not be a sufficient).

Since you only care about a specific measurement result being correctable, I believe this simply reduces to considering only flows which commute with the measurement on a site if the site is black, and anticommute with the measurement operator if the site is white.

I hope this is useful, though of course I realise it is a very weird way to look at the problem.