- Part (ii) of Proposition 18 of "Graphs with Equal Vertex Cover and
Eternal Domination Numbers" [Disc. Math 311 (2011)], should state that the
eternal vertex cover number of the graph in question is greater than
or equal to n-1 (rather than equal to n-1). Thanks to Mike Fisher for
pointing this out.
- In "Complexity of Eternal Security" it is claimed that the eternal
domination problem is in co-NP^NP. The proof is incorrect and the problem
of determining the best class the problem is in remains open. (The
eternal domination problem is hard for co-NP^NP).
The error is related to the claim that the distance between any two guard
configurations D1 and D2 is at most n^2. Though this is true, it may take
an adversary an exponential number of attacks to move the guards from one
initial configuration Di to another (non-dominating) configuration Df. As
a simple example, the Hamming distance between 0000 and 1111 is 4, but the
number of strings between then is 15. That the problem of determining if
Di is an eternal dominating set is decidable is not at first evident,
until one realizes that an adversary can guess, as it simulates the
behavior of a defense strategy, each subsequent guard configuration (from
amongst the possible guard configurations that the defense strategy might
take for that attack). Thus at most 2^n attacks must be
simulated. Furthermore, the algorithm must also guess a
defense algorithm, but this can be done since there are only a finite
number of ways of responding to the at most exponential number (i.e., 2^n)
of attacks that nust be considered. Hence the problem lies in the
complement of a class such as EXP^NP (since we must verify that all of
the defense strategies lead to configurations of guards that are not
dominating sets). Since EXP is closed under complement, and EXP^NP = EXP,
the problem is in EXP. It remains open as to the precise class that
either the problem "Is D an eternal dominating set of G?" or the problem
"Is the eternal domination domniation number of G at most k?" belong.
It seems plausible that they are in PSPACE, by a similar argument, but I
have not checked the details.
- Maximization Versions of 'Lights Out' Games in Grids and Graphs; J. Goldwasser and
W. Klostermeyer, Congressus Numerantium, vol. 126, 1997, pp. 99-111
[The online version here corrects a typo that appears in the parameters of the gap-presverving reduction]
- Pushing Vertices and Orienting Edges;
W. Klostermeyer, Ars Combinatoria.

The proof that deciding if a digraph can be pushed to be acyclic is NP-complete is in error. The result is correct, however, as the following proof shows.

As in the paper, we do a transformation from NAE-3SAT instance S with m clauses.

Assume without loss of generality that u, not u do not appear as a pair in any clause (else the clause is trivially NAE satisfied).

We use the following gadget (one for each variable in each clause, so we have 3m gadgets, and we number the gadgets from 1 to 3m in a left to right fashion, i.e. the gadgets corresponding to the variables in clause i will be numbered 3(i-1)+1, 3(i-1)+2, and 3(i-1)+3):

u, not u, x, y on a 4-cycle u -> x -> not u -> y -> u, where u, not u correspond to boolean variable u and its negation. Create two additional vertices w, z for each variable appearing in each clause where x, y are dominated by z and x, y dominate w. u and not u are called variable vertices. Other edges in the gadget are shown in the figure below. Note that we must push exactly one of u, not u to make the gadget acyclic.

A gadget is shown here:

At this point we have 3m*6=18m vertices. It is easy to show that exactly one of u, not u must be pushed to make gadget acyclic.

Connect each three literals in each clause on a 3-cycle, called a clause cycle (so we have m vertex disjoint 3-cycles). Thus either 1 or 2 literals must be pushed in each of these clause cycles to make each of them acyclic.

To ensure consistency, we construct consistency components:

each u vertex also dominates the u in the next hightest number gadget in which u/not u appears (say these are numbered as u_i, u_j, i less than j). We create four new vertices for each such pair, a_i, b_i, e_i, f_i and let a_i dominate both u_i and u_j and let u_i and u_j both dominate b_i. We let a_i dominate e_i, e_i dominate u_i, f_i dominate u_i, u_j dominate e_i, f_i dominate u_i, f_i dominate b_i.

Note that we are re-using the same variable vertices from the gadgets here.

Likewise each not u vertex dominates the not u vertex in the next hightest number gadget in which u/not u appear. We create four new vertices for each such pair, c_i, d_i, g_i, and h_i and let c_i dominate both not u_i and not u_j and let not u_i and not u_j both dominate d_i. We let c_i dominate g_i, g_i dominate not u_i, h_i dominate not u_i, not u_j dominate g_i, h_i dominate not u_i, h_i dominate d_i.

A consistency component is shown here:

Observe that if we push u_i and do not push u_j, then we must push a_i to avoid a 3-cycle. Pushing a_i then means we must push e_i to avoid a 3-cycle. but this means we must push u_j, a contradiction. Similarly if we push u_j and do not push u_i.

By transitvity, this ensures consistency, since pushing a vertex corresponds to it evaluating "true."

If we have a consistent truth assignment for S, we push u_i if the corresponding variable is assigned true and push not u_i otherwise. We also push e_i, f_i if u_i is not pushed and push a_i, b_i pair otherwise, i.e if u_i is pushed. Likewise, if we push not u_i, we will push c_i and d_i and otherwise push g_i and h_i. It is now not hard to see that there can be no cycles in the graph.

Suppose we push vertices corresponding to a consistent (and NAE satisfying) truth assignment and we push the appropriate e, f,g, h, vertices. Then all clause 3-cycles and all gadget cycles are broken as described above as well as all cycles that can be contained within any single consistency component, since:

i) if we pushed e_i and f_i (or g_i and h_i) then u_i and u_j (not u_i and not u_j) are a source and sink vertex within the consistency component and b_i is also a sink.

ii) if we pushed u_i and u_j (and thus also pushed a_i and b_i) then the effect is the same as i).

It is clear that there can be no other cycles in the graph, since all edges of the form u_iu_j will be directed from "left to right."

It now follows that S has a NAE truth assignment if and only if the digraph can be made acyclic, since we cannot make a consistency component acyclic without pushing a variable vertex, nor can we make a clause or gadget component acyclic with pushing variable vertices.

Thanks to Gary MacGillivray and Kathryn Wood for pointing out this error.

Gary MacGillivray informs me that determining if a bipartite graph can be made acyclic using pushes is also NP-complete. - The paper "On the Least Deviant Path in a Graph" contains a typo regarding the running time of the algorithm on page 154. The correct analysis should have m=|E| in which case the running time is O(E^(2.586)). It should be noted that an O(E log E) algorithm is given in "A Faster Algorithm for Least Deviant Path," R. Dutton and W. Klostermeyer, JCMCC, 1999