Approximation Algorithm of Minimum All-Ones Problem for Arbitrary Graphs
Chen Wang Chao Wang Gregory Z. Gutin Xiaoyan Zhang
































1]Chen Wang
2120220677@mail.nankai.edu.cn

2]Chao Wangcor1
wangchao@nankai.edu.cn


3]Gregory Z. Gutin
gutin@cs.rhul.ac.uk


4]Xiaoyan Zhang
xiaoyanice@aliyun.com

[1]Address: College of Software, Nankai University
[2]Address: College of Software, Nankai University
[3]Address: Royal Holloway, University of London
[4]School of Mathematical Science, Institute of Mathematics, Nanjing Normal University, Jiangsu 210023, China

[cor1]Corresponding author.















	
	Let G=(V, E) be a graph and let each vertex of G has a lamp and a button. Each button can be of σ^+-type or σ-type.
	Assume that initially some lamps are on and others are off. The button on vertex x is of σ^+-type (σ-type, respectively) if pressing the button
	changes the lamp states on x and on its neighbors in G (the lamp states on the neighbors of x only, respectively). Assume that there is a set X⊆ V such that pressing buttons on vertices of X lights all lamps on vertices of G. In particular, it is known to hold when initially all
	lamps are off and all buttons are of σ^+-type. 
	
	Finding such a set X of the smallest size is NP-hard even if initially all
	lamps are off and all buttons are of σ^+-type. Using a linear algebraic approach we design a polynomial-time approximation algorithm for the problem such that for the set X constructed by the algorithm, we have |X|≤min{r,(|V|+ opt)/2}, where r is the rank of a (modified) adjacent matrix of G and opt is the size of an optimal solution to the problem. 
	To the best of our knowledge, this is the first polynomial-time approximation algorithm for the problem with a nontrivial approximation guarantee. 



	
	
	
	
	
	
	lamp lighting problem
	minimum all-ones problem
	approximation algorithm
	complexity
	












§ INTRODUCTION 


The all-ones problem is a fundamental problem in applied mathematics, first proposed by Sutner in 1988 <cit.>. This problem has applications in linear cellular automata, as discussed in <cit.> and the references therein. To illustrate the problem, consider an n× n grid with each area having a light lamp and a switch, and every lamp is initially off. Turning the switch on in some area lights the lamp in the area and the lamps in neighboring areas. 
Is there a set X of areas such that turning the switches on in X will turn on all the lamps? This problem can be extended to all graphs and we will call it the all-ones problem. 
Sutner <cit.> proved that a solution X exists for every graph. 
Later, several simple proofs of this result were given or rediscovered <cit.>. 


Many variants of the all-ones problem have been introduced and studied <cit.> over years. There are two important generalizations of the all-ones problem: (i) the initial state of lamps and switches can be arbitrary, i.e., some are on and the others are off, and (ii) every switch can be either of σ^+-type which changes the states of the lamp on its vertex and the lamps on the neighbors of its vertex or σ-type which changes the states of the lamps on the neighbors of its vertex only. As a result of these two generalizations, the generalized all-ones problem may not have a solution X which lights all lamps. This generalized problem is studied in this paper. Under the condition that such a solution X exists for the generalized all-ones problem, it is natural to ask for X of minimum size. 

Unfortunately, this minimization problem is NP-hard even for all-ones problem <cit.>; we will call the minimization all-ones problem the min all-ones problem. Galvin and Lu both proved that the min all-ones problem of trees can be solved in linear time <cit.>. Building on this, Chen proposed an algorithm for solving the min generalized all-ones problem on trees, with linear complexity <cit.>.  Manuel et al. provided solutions for some of the widely studied architectures, such as binomial trees, butterfly, and benes networks <cit.>. Fleischer and Yu provided a detailed survey of the generalized all-ones problem <cit.>. More recently, Zhang extended the all-ones problem to the all-colors problem, in which each lamp had other states besides being on and off, and obtained additional findings on the all-colors problem <cit.>.




Although significant research has been conducted on the all-ones problem on special graphs, such as trees, resulting in efficient algorithms, no polynomial-time approximation algorithms have been designed for the min all-ones problem on general graphs. Trees and cyclic graphs only represent a fraction of general graphs. In practical engineering scenarios, complex graphs are more common. In this paper, we design a polynomial-time approximation algorithm for the min generalized all-ones problem. If the problem has a solution, our algorithm outputs a solution X such that |X|≤min{r,(|V|+ opt)/2}, where the rank of a (modified) adjacent matrix of G and opt is the size of an optimal solution to the problem. 





Apart from the introduction, this paper contains three sections. In Section <ref>, we introduce our approximation algorithm in detail. Section <ref> shows the theoretical analysis and performance evaluation of this algorithm. Section <ref> summarizes all the work of this paper and discusses future work.




§ APPROXIMATION ALGORITHM OF MIN GENERALIZED ALL-ONES PROBLEM



 §.§ Linear algebraic formulation of min generalized all-ones problem


It is not hard to see that the min generalized all-ones problem can be described as the following linear integer program over  𝔽_2. 
For an arbitrary graph G=(V,E) with V={v_1,… ,v_n} we can get its modified adjacency matrix A = (a_ij)_n× n such that for all i j, a_ij=1 if v_iv_j∈ E and a_ij=0 otherwise, 
and for all i∈{1,2,… ,n}, a_ii=1 (a_ii=0, respectively) if  the switch on v_i is of σ^+-type (of σ-type, respectively).
Combined with the initial state B = (b_1,b_2,⋯,b_n), where b_i=0 if the lamp on vertex v_i is initially on and b_i=1 if the lamp is initially off, we can construct a system of linear equations AU=B over 𝔽_2. The solution to this problem is the minimum of ∑ U = ∑_i=1^nu_i. 

Suppose the rank of A is r and the corank is m so that m+r=n. If a_ii = 1 for all i ∈{1,2,⋯,n}, the system of equations AU=B must have a solution, but if a_ii = 0, the system may not necessarily have a solution. However, as long as the system has at least one solution = (γ_1,γ_2,⋯,γ_n)^T, we can find all solutions of the system using the following system combining  with 
the fundamental solution set = (η_1,η_2,⋯,η_m) within time O(n^3). Here x_i is the coefficient of the column vector η_i=(η_1i,… , η_ni)^T.

    X +     =
    	η_11   η_12   ⋯   η_1m
    η_21   η_22   ⋯   η_2m
    η_31   η_32   ⋯   η_3m
    ⋮   ⋮   ⋱   ⋮
    η_n1   η_n2   ⋯   η_nm
    
    		x_1
     x_2
    ⋮
    x_m
    	+
    	γ_1
    γ_2
    γ_3
    ⋮
    γ_n


The problem is how to find the appropriate column vector X to minimize ∑ U, under the condition that X has a total of 2 ^ m values. This problem was proven to be an NP-complete <cit.>. 
Therefore, the next subsection provides an approximation algorithm running in polynomial time.




 §.§ Approximation algorithm

Firstly, it can be observed that the polynomial time complexity (not exceeding O(n^3))  of finding the matrix (η_1,η_2,⋯,η_m) and the special solution  makes this process cost-effective in solving NP-complete problems. Secondly, it is challenging to identify alternative methods capable of directly computing the optimal solution without obtaining all the solutions. Even if such a solution is obtained, verification is often infeasible. 

When  and  are known, we need to find the X that minimizes ∑ U.

    X +     =
    	η_11   η_12   ⋯   η_1m
    η_21   η_22   ⋯   η_2m
    η_31   η_32   ⋯   η_3m
    ⋮   ⋮   ⋱   ⋮
    η_n1   η_n2   ⋯   η_nm
    
    		x_1
     x_2
    ⋮
    x_m
    	+
    	γ_1
    γ_2
    γ_3
    ⋮
    γ_n
        =
    	δ_1
    δ_2
    δ_3
    ⋮
    δ_n
    	+
    	γ_1
    γ_2
    γ_3
    ⋮
    γ_n = 
    	
    		u_1
     u_2
     u_3
    ⋮
     u_n



Row exchanges of matrix  do not change ∑ U.


Multiply both sides of Equation <ref> by matrix P as shown in Equation <ref>. Matrix P is a product of elementary matrices that perform row exchanges. This operation essentially reorders the elements of vector U, but does not change the ∑ U.

    P ( X + ) = P ( + ) = P U





Column transformation of matrix  does not change ∑ U.



Let Q_m*m be a full rank matrix, and QZ=X, with the following equation. 

    X +     =
    		 QZ + 
        =
    		( Q)Z + 
        =
    		 Z + 
        =
    		 + 
        = U

Q is the transition matrix between X and Z, and Q is full rank. When we find that X makes ∑ U the smallest, we can definitely find the corresponding Z, so that the obtained U is the same.


We can transform the  column into an echelon form using row exchanges and column transformations, as shown in the following equation, with a complexity of O (m^2n). The question mark indicates that the value of the number is uncertain, which may be 0 or 1. We can divide the matrix into m+1 parts based on the echelon and assume the last line of the i-th part is line k_i (i = 0,1,⋯,m) for the rank of matrix  is always m. Part 0 is the most special, with all elements in each row being 0. To ensure that Equation <ref> holds, there should be (u1,u2,⋯,u_k_0)=(γ_1,γ_2,⋯,γ_k_0).

    Q =  = 
    
    	0     0     0     0    ⋯    0
    ⋮   ⋮   ⋮   ⋮   ⋱   ⋮
    
    	1     0     0     0    ⋯    0
    
    	1     0     0     0    ⋯    0
    ⋮   ⋮   ⋮   ⋮   ⋱   ⋮
    ϵ_(k_1+1)1    1     0     0    ⋯    0
    ϵ_(k_1+2))1    1     0     0    ⋯    0
    ⋮   ⋮   ⋮   ⋮   ⋱   ⋮
    ϵ_(k_2+1)1   ϵ_(k_2+1)2    1     0    ⋯    0
    ϵ_(k_2+2)1   ϵ_(k_2+2)2    1     0    ⋯    0
    ⋮   ⋮   ⋮   ⋮   ⋱   ⋮
    ϵ_k_m1   ϵ_k_m2   ϵ_k_m3   ϵ_k_m4   ⋯    1

In the following m parts, we will use greedy algorithms to solve for the Z value on the Echelon of each part. Part 1 of the linear Equation <ref> is shown in Equation <ref>. (γ_k_0+1,γ_k_0+2,⋯,γ_k_1) is known and (δ_k_0+1,δ_k_0+2,⋯,δ_k_1) is unknown. It is important to ensure that δ_i is as similar to γ_i as possible. At this moment z_1 only has two possible values: 0 and 1. Therefore, the idea of a greedy algorithm is adopted here. If there are more 0's than 1's in the range from γ_k_0+1 to γ_k_1, then z_1 is set to 0. If there are more 1's than 0's, then z_1 is set to 1. Therefore, we can directly obtain the value of x_1 by solving it here, while ensuring that ∑_i=k_0+1^k_1u_i  ≤ (k_1 - k_0) / 2.

    z_1= δ_k_0+1
         z_1= δ_k_0+2
         z_1= δ_k_0+3
             ⋮
         z_1= δ_k_1     Compare to    γ_k_0+1
    γ_k_0+2
    γ_k_0+3
    ⋮
    γ_k_1






The value of z_2 can be calculated through z_1. Part 2 of Equation <ref> can be written as shown in Equation <ref>. (γ_k_1+1,γ_k_1+2,⋯,γ_k_2) is known, and (δ_k_1+1,δ_k_1+2,⋯,δ_k_2) needs to satisfy the Equation <ref> and be as similar to (γ_k_1+1,γ_k_1+2,⋯,γ_k_2) as possible. The variables in Equation <ref> are z_1 and z_2, and z_1 has been solved before through a greedy algorithm, so the unknown variable is only z_2. Since ϵ_i1z_1 are constants, we can move them from the left side of the equation to the right side, and these two equation systems are obviously equivalent. Then, we need to ensure that ϵ_(k_1+i)1z_1+δ_k_1+i is as similar to γ_k_1+i as possible. It can be seen that another transformation can be carried out, which is equivalent to making δ_k_1+i as similar to ϵ_(k_1+i)1z_1+γ_k_1+i as possible. In this way, we have separated the variables: the left side of the equation is the variable z_2, the right side of the equation is the variable δ_k_1+i (δ_k_1+i = z_2), and the column of ϵ_(k_1+i)1z_1+γ_k_1+i are constants. At this point, we find that part 2 of Equation <ref> has been transformed to be very similar to part 1. Therefore, if there are more 0's than 1's in the range from ϵ_(k_1+i)1z_1+γ_k_1+1 to ϵ_(k_2)1z_1+γ_k_2, then z_2 is set to 0. If there are more 1's than 0's, then z_2 is set to 1. Therefore, the value of z_2 can be solved here and ∑_i=k_1+1^k_2u_i  ≤ (k_2 - k_1) / 2 is ensured.

After obtaining the value of z_2, the value of ϵ_i1z_1 + ϵ_i2z_2 can be calculated, and the value of z_3 can be calculated again. Following this pattern, the values of Z = (z_1, z_2, ⋯, z_m) can be obtained. Then Z +  = U, we obtain U. The complete algorithm is shown in Algorithm [a1]1.



    ϵ_(k_1+1)1z_1+z_2= δ_k_1+1
       ϵ_(k_1+2)1z_1+z_2= δ_k_1+2
       ϵ_(k_1+3)1z_1+z_2= δ_k_1+3
             ⋮
       ϵ_(k_2)1z_1+z_2= δ_k_2             Compare to    γ_k_1+1
    γ_k_1+1
    γ_k_1+1
    ⋮
    γ_k_2
    
    ⇓
    
         z_2= δ_k_1+1+ϵ_(k_1+1)1z_1
         z_2= δ_k_1+2+ϵ_(k_1+2)1z_1
         z_2= δ_k_1+3+ϵ_(k_1+3)1z_1
             ⋮
         z_2= δ_k_2+ ϵ_(k_2)1z_1
    	             Compare to    γ_k_1+1
    γ_k_1+1
    γ_k_1+1
    ⋮
    γ_k_2
    
    ⇓
    
         z_2= δ_k_1+1
         z_2= δ_k_1+2
         z_2= δ_k_1+3
             ⋮
         z_2= δ_k_2         Compare to       γ_k_1+1+ ϵ_(k_1+1)1z_1 
    γ_k_1+2+ ϵ_(k_1+2)1z_1 
    γ_k_1+3+ ϵ_(k_1+3)1z_1 
    ⋮
    γ_k_2+ ϵ_(k_2)1z_1







§ ALGORITHM PERFORMANCE EVALUATION
	
In this section, we present the complexity of Algorithm [a1]1 and analyze its approximation guarantees.


Algorithm [a1]1 has a complexity of O(n^3), and if the fundamental solution set  for the equation AU=B has been obtained and is in column echelon form, then the complexity will reduce to O(mn).



In Algorithm [a1]1, step 1 involves solving a system of linear equations, which has a complexity of O(n^3). Step 8 involves transforming the matrix etaup into column echelon form, which has a complexity of O(m^2n) where m ≤ n. Step 2 to 7 is O(1). Step 9 involves calculating the location of pivots in the column echelon matrix , which has a complexity of O(mn). Steps 10 to 24 consist of a nested loop with three layers. However, each element in the matrix  is only accessed once, resulting in a complexity of O(mn).


 If a given instance I of the min generalized all-ones problem has a solution, 
the value sol of the solution  obtained by Algorithm [a1]1 satisfies sol≤ r, where r is the rank of the matrix A.



In Equation <ref> and <ref>, if δ_i=γ_i, then the resulting u_i will be 0. In each part, we always make more u_i equal to 0, so each part has at least one u_i  that takes on the value of 0. Furthermore, the rank of  is m=n-r because  is the fundamental solution set of the system AU=B. Therefore, at least m values of u_i are 0, so ∑ U ≤ n-m=r.



If a given instance I of the min generalized all-ones problem has a solution, the value sol of the solution obtained by Algorithm [a1]1 satisfies sol ≤ (n+ opt)/2, where opt is the value of an optimal solution of I.



In the Subsection <ref>, we partitioned the matrix  into m+1 parts and proved that for the 1 to m parts, ∑_k_i+1^k_i+1u ≤ (k_i+1 - k_i) / 2. Only the 0th part remains to be discussed. The 0th part is quite special in that it contains no variables, only differing in the value of γ. Let the number of 0's in γ in the 0th part be g_0 and the number of 1's be g_1. g_0 indicates that the switch at that point must not be pressed; otherwise, the conditions for the all-ones problem cannot be satisfied. Similarly, g_1 indicates that the switch must be pressed. Now we have: 

    sol ≤ g_1 + (n-g_1-g_0)/2 = (n + g_1-g_0)/2

Then add the parameter opt. We can easily prove that sol≥ opt≥ g_1, because the switches for these points must be pressed in any case. So we have

    g_1 ≤ opt≤ sol ≤ (n + g_1-g_0)/2

Next, we will bound sol by replacing g_1 with opt and g_0 with 0, resulting in the following expression:

    sol≤ (n+ opt)/2









§ CONCLUSION AND FUTURE WORK

This article presents an approximation algorithm for the min generalized all-ones problem on arbitrary graphs, making it possible to process the problem in batches. The algorithm has a complexity of O(n^3). If the equation system AU=B has been solved and the solution is in column echelon form, the complexity will be reduced to O(n(n-r)), which is the lowest complexity for general graphs. The upper bound of the solution value sol obtained by this algorithm satisfies the inequality sol≤ (n+ opt)/2 and sol≤ r. This ensures that the obtained solution, as shown in Figure 1, is always the optimal half.

In future work, there still remain two questions to be solved. One of them is whether there is a polynomial-time algorithm for the min generalized all-ones problem which always finds a solution of size at most cȯṗṫ for some constant c?
The other one is whether we can get such an algorithm for the minimum all-colors problem?



























elsarticle-harv

















