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:
- complementing the subgraph induced by $v$ and its neighbours,
- flipping the colour of each neighbour of $v$ (i.e. black vertices become white and conversely), and finally
- 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.
Best Answer
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.