A Variation on Flipping Lightbulb Switches, pt. 1


Problem. Suppose you are in a room with $n$ lightbulbs and $k$ switches, where $1 \leq n$ and $1 \leq k$. Suppose that any particular switch turns a subset of light bulbs on. Find the minimum number of switches such that flipping them on turns on all of the lights.

If you are familiar with algorithms, you'll recognize this problem as a form of set-cover. Clearly, the search problem stated above is NP-hard! Typically, introductory algorithm courses present the greedy approach, which admits a $O(\log n)$ approximation to set cover. However, for this post, I'll present the linear program (LP) approach.

(Integer) Linear Program for Lightbulb Problem.

Let the set $L = \{1, 2, \dots, n\}$ enumerate the lightbulbs from the problem. Additionally, let $S_i \subseteq L$ indicate the subset of lights that are turned on by the switch $s_i$. We now define the indicator random variable $Z_i$ such that $Z_i = 1$ if the set $S_i$ is selected. Then, the optimization problem is given by:

$$ \begin{align*} \min \sum_{i=1}^k Z_i &&\text{ subject to } \forall j \in L, \sum_{i \in I_j} Z_i \geq 1\\ &&\forall i \in [1, \dots, k], Z_i \in \{0,1\}\\ &&\text{where } I_j = \{i\; |\; j \in S_i\} \end{align*} $$

Then, the set $I_j$ is the set of of all switch set labels $i$ such that the light $j$ is switched on by $s_i$.

This is not a true LP, as the values of $Z_i$ are restricted to the integral values $0$ or $1$. Solving the above problem is NP-hard!

The LP-relaxation of the above problem, such that the constraints for $Z_i$ become $0 \leq Z_i \leq 1$, can be solved in polynomial time using some canonical, black-box LP-solver. The interpretation here is that we allow certain sets to be fractionally included, which intuitively allows for a more easily found solution.

Of course, the tricky part is obtaining an approximately optimal solution to the original problem from the fractional solution, using a rounding scheme.

A canonical rounding scheme for set cover can be shown to give a $2 \ln n$ approximation to the optimal solution of the LP optimum!


I now pose an even harder variation of the light bulb problem:

Variation. (Toggling Light Bulbs Problem) Suppose you are in a room with $n$ lightbulbs and $k$ switches, where $1 \leq n$ and $1 \leq k$. Suppose that any particular switch toggles the state of a subset of light bulbs. That is, suppose switch $s_j$ toggles the switches ${1, 3, 4}$, such that if switch $1$ was on, it is now off - and if $3$ and $4$ were off, they are now on. Find the minimal number of switches such that flipping them on turns on all of the lights.

The ILP formulation for this problem is not too different from above. The key recognition is that for any light bulb that is on, the number of sets that include this light bulb must be odd. For example, if exactly two sets are used in the solution that contain some light bulb $i$, $i$ would be off. We then have,

$$ \begin{align*} \min \sum_{i=1}^k Z_i &&\text{ subject to } \forall j \in L, \bigg(\sum_{i \in I_j} Z_i \bigg) - y_j = 1 \\ &&\forall j \in L, y_j \in \mathbb{N^{+}}\\ &&\forall i \in [1, \dots, k], Z_i \in \{0,1\}\\ &&\text{where } I_j = \{i\; |\; j \in S_i\} \end{align*} $$

The key to this problem is devising a neat rounding scheme that gives a reasonable approximation to the optimal LP solution. I've posed and formulated the problem in this post, and plan to give it some more thought.

Edit, with some more thought:

After sending this problem to my algorithms professor, he directed me to the following paper on a closely related problem: Combination Can Be Hard: Approximability of the Unique Coverage Problem

The crux of the Unique Coverage Problem is to find a collection of subsets that maximizes the number of covered elements with the constraint that each element appears exactly once across all subsets.

Clearly, given a solution to Unique Coverage, we can find a solution to the Toggling Light Bulbs problem by greedily trying to cover the remaining uncovered elements (while still satisfying the odd # constraints). Of course, since the constraints in the Unique Coverage problem are tighter (only allowing one of each element as opposed to an odd number), I am optimistic that it is possible to achieve better than $\Omega(1/\log^c n)$ inapproximability.

I'll be thinking some more about this problem, but it is definitely an interesting thought experiment!