- 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 minor error that appears in the published version: namely
the parameters of the gap-presverving reduction]
- Pushing Vertices and Orienting Edges;
W. Klostermeyer, to appear in 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