Report

Lights Out for Fun and Profit! Parity Domination: Algorithmic and Graph Theoretic Results William F. Klostermeyer University of North Florida Introduction Green Vertex Pushed Introduction cont. • Of the 216 initial configurations of 4 X 4 grid, 212 can be changed to all-off • How many can be changed to alloff in N X N grid? History • • • • • Lights Out! (~ 1995) Button Madness (PC Game) ACM Programming Contest Cellular Automata (1989) Parity Domination (1990’s) Overview • Complete Solvability – Fibonacci Polynomials • Maximization Problems – Complexity – Approximation Algorithm – Fixed Parameter Problems Parity Domination 1 1 0 1 1 p(v) indicated for each v 0 Parity Domination cont. • Even Dominating Set: – Non-empty set of vertices D s.t. each vertex is adjacent to an even number of vertices of D • Odd Dominating Set: – Defined accordingly Parity Domination cont. • Theorem (Sutner): Every graph has an odd dominating set • Theorem (folklore): Every initial configuration of G can be turned off iff G has no even dominating set Even Dominating Sets • If G has even dominating set, D, closed neighborhood matrix is singular • Pushing D and empty set have same effect : no change! • Which graphs have even dominating sets? Even Dominating Set cont. 0 0 0 0 1 0 1 1 1 0 0 0 Nullspace Matrix Basics • Can decide in polynomial time if G has an even dominating set – use Gaussian elimination • If G does not have an even dominating set we say G is completely solvable Basics cont. • If G has an even dominating set: – Can decide in polynomial time if a given configuration can be turned off (use linear algebra methods) 3 X 3 Grid Linear Equations 110100000 111010000 011001000 100110100 010111010 001011001 000100110 000010111 000001011 x1 = 1 x2 = 0 x3 = 0 x4 = 0 x5 = 0 x6 = 1 x7 = 0 x8 = 1 x9 = 0 Grids • 3 X 3 grid completely solvable • 4 X 4 grid not completely solvable (= has even dominating set) • Test if Closed Neighborhood Matrix is singular – O((nm)3) SLOW! Nullspace Matrices 1001 1111 1111 1001 1’s = Even Dominating Set of 4 X 4 Grid “Linearize” this matrix to get a 16 X 1 vector in nullspace of closed neighborhood matrix of 4 X 4 grid Building Nullspace Matrices 000000000 110101011 000101000 111000111 010000010 000000000 • Thus 4 X 9 grid is not completely solvable. • Likewise 9 X 9, 4 X 14, 9 X 14, etc. Nullspace Recurrence 1001 1111 1111 1001 1’s = Even Dominating Set of 4 X 4 Grid r[I, j]=r[I-1,j]+r[I-1,j-1]+r[I-1,j+1]+r[I-2,j] mod 2 Recurrence cont. Theorem: r[I]=fi(B)w • r[I] : ith row of nullspace matrix • fi : ith Fibonacci polynomial • B : Closed Neighborhood Matrix • w : initial non-zero vector Fibonacci Polynomials • Fn(x) is nth Fibonacci polynomial: f0=0, f1=1, f i=x f i-1(x) + fi-2(x) f2=x, f3=x2+1, f4=x3 Example 000 1 0 0 <-- w 110 101= 110 110 100 ( 1 1 1 * 1 1 1 + 0 1 1) * 1 0 0 = w 011 011 011 f3=x2+1 Factored Fibonacci Polynomials • Implemented (randomized) algorithm to factor polynomials over GF(2) in polynomial time Factored cont. • f_2: x (x)^1 • f_3: x^2 +1 (x +1)^2 • f_4: x^3 (x)^3 Fibonacci Polynomials cont. • f_5: x^4 +x^2 +1 (x^2 +x +1)^2 • f_6: x^5 +x (x +1)^4 (x)^1 See my web page for thousands more More on the Recurrence • Period: number of rows until row of 0’s • Recurrence is periodic • Theorem: Maximum period generated by initial vector <1 0 0 0 …> • Theorem: Length of period is less than 3*2n/2 Periods • • • • • • • • n=5 n=6 n=7 n=8 n=9 n=10 n=12 n=13 24, 12, 8, 6, 4, 3, 2 9 12, 6, 3 28, 14, 7, 4, 2 30, 15, 10, 5, 3 31 63 18, 9, 3 More Periods Maximum periods: • n=39 120 • n=40 1,048,575 • n=41 4680 • n=46 over 8 million Divisibility Properties • Theorem: All periods divide the maximum period • Theorem: If fn+1(x) has only one non-trivial factor, then there is only one period for vectors of length n Characterization • Theorem: m x n grid is completely solvable iff GCD(fn+1(x+1), fm+1(x))=1 over GF(2) Fast Algorithm • Can determine if m X n grid is completely solvable in O(n log2 n) time, n >= m • Obvious method: O((nm)3) time Square Grids • Lemma: f2^k+1(x)f2^k-1(x) is equal to square of product of all irred. polynomials with degree dividing k except for x, over GF(2) • Theorem: 2k x 2k and 2k-2 x 2k-2 grids not completely solvable for all k > 3 Maximization Problems • Theorem: Can always get at least mn-m/2 off in m X n grid, n >= m • Theorem: Exist m X n grids for which some initial configurations can get at most mn - (m/log m) off, n >= m Graphs • Play Lights Out! in graph • Closed neighborhood matrix non-singular iff completely solvable iff no even dominating set • Maximization problems in graphs Complexity Results • Theorem: NP-complete to decide if G can be made to have at least k lights out • Also NP-complete for planar graphs • Simple approximation algorithm with performance ratio 2 Max-SNP Hard • Theorem: Exists e > 0 s.t. no approximation algorithm can have performance ratio less than 1+e unless P=NP • Is there a better approximation algorithm for planar graphs? Fixed Parameter Problems • Can decide in polynomial time if a configuration can be made to have n-c off, for constant c –Gaussian elimination + brute force Fixed Parameter cont. • Can decide in polynomial time if all configurations can be made to have n-c off, for a constant c –Treat all-off state as codeword of binary code –Test if covering radius of code is at most c •Large grids, 5 by 5 and larger: Theorem. (Counting argument). Unsolvable implies not all initial configurations can be made to have at most one light on. Trees: always at most leaves/2 on. Conjecture • Let fn+1 equal square of irred. Polynomial and m be maximum period of n. Then all initial configurations of m X n grid can be made to have at most 2 vertices on. – Verified for 8 X 6, 30 X 10, 62 X 12, 512 X 18 using Coding Theory algorithm Publications • Characterizing Switch-Setting Problems, Lin. and Mult. Alg. 1997 • Maximization Versions of Lights Out …, Cong. Num. 1998 • Fibonacci Polynomials…, Graphs and Combinatorics, to appear Related Work • “The Odd Domination Number of a Graph” Y. Caro and W. Klostermeyer, to appear in J. Comb. Math. & Comb. Comput. • Study size of smallest odd dominating set in graph