Local complementation in undirected graphs

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$?

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.

• Does the initial condition for the color of the vertices makes any difference? – Hsien-Chih Chang 張顯之 Feb 26 '10 at 17:19
• Yes, because at any given step, you can only select black vertices. So graphs with only white vertices are examples of graphs that cannot be deleted. – Anthony Labarre Feb 26 '10 at 17:53
• Could you give some references to the papers? – domotorp Feb 26 '10 at 22:31
• It would help if you were clear on the relationship of the order to the process. For example, I do not know if O is total or partial. I also do not know if O means start with the least or the greatest vertex in doing local complementation. Further, it seems that the coloring of the vertices has as much or more to do with the problem than the adjacency, so you may only get characterizations of pairs (O,C), unless the coloring C is strongly tied to the graph. Also, a conjecture on what characterization you think might hold would help. Gerhard "Ask Me About System Design" Paseman, 2010.02.26 – Gerhard Paseman Feb 27 '10 at 0:40
• Indeed, I forgot about that. But let me ask another stupid question (I promise to delete these comments once I got it) - What if A is a single vertex and B is on edge? In this case calling the vertices according to their order, 1 is connected to both 2 and 3 and the black vertices are 1 and 3. Seems to me that the whole graph gets deleted. – domotorp Feb 28 '10 at 7:42

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.

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.

• Thanks for the time you've taken to sketch this, I'm not sure I got everything but I guess going through it some more should get me there. I still wonder however if the conjecture we discussed above (with the parity condition) can be proved either way or if I should give up hope because of your proof. I'm still new to this website, so I don't know if I should start a new thread to ask that or just append the conjecture to my first message. – Anthony Labarre Mar 2 '10 at 19:36
• In fact now I realized that nothing follows from this proof to your conjecture. Could you give me an example where the degrees satisfy your parity conditions and can be deleted? I guess you can just edit your original question and add this to the questions section. Or if you want more people to notice it, then it makes more sense to ask a new question, maybe also pointing to this question. – domotorp Mar 2 '10 at 21:40
• Hey, I just realized that what you ask is impossible! I will append the proof to my answer. – domotorp Mar 2 '10 at 21:43
• Indeed, thanks for settling that issue. Since I was trying to rely on that to find a proof of something else, I might be asking a similar question soon. – Anthony Labarre Mar 2 '10 at 23:37

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.

• No, I had absolutely no idea it could be seen that way. You use a lot of concepts I've never heard of (must be because I'm a computer scientist), so it will take me some time to get it all, but thanks a lot for suggesting a direction I would never have considered by myself, I'll definitely take a look at that. – Anthony Labarre Feb 28 '10 at 9:08