Let us denote the state of the ~i^\text{th}~ switch by ~a_i~. We can think about ~a_i~ as a Boolean variable, which is true when the switch is turned on. Using this approach, all we have to do is to find a valuation of these variables fulfilling task conditions. Moreover, we can easily transform the problem into the language of logic. We show it using the example from the task statement:

3 2
1 0 2 1
1 0 2 0
1 1 2 1

In this example, we have two switches. As a result, we will have two variables ~a_1~ and ~a_2~. If we look at channel number one, we will see that switch number one has to be off or switch number two has to be on in order for this channel to be closed. For each channel, we can create a logical formula:

• channel 1: ~\lnot a_1 \lor a_2~
• channel 2: ~\lnot a_1 \lor \lnot a_2~
• channel 3: ~a_1 \lor a_2~

Since we are looking for a configuration that closes all the channels, we have to make a conjunction of the constructed logical formulas:

$$\displaystyle (\lnot a_1 \lor a_2) \land (\lnot a_1 \lor \lnot a_2) \land (a_1 \lor a_2)$$

Our task is to find a valuation of variables ~a_1~ and ~a_2~ that satisfies the above formula. In general, the problem of satisfying a given logical formula is known to be NP-complete. Fortunately, the formula obtained in this task is of a very special form:

$$\displaystyle (x_1^1 \lor x_1^2) \land (x_2^1 \lor x_2^2) \land \dots \land (x_n^1 \lor x_n^2)$$

where ~x_i^1~ and ~x_i^2~ are literals and each of them stands for some variable ~a_j~ or negated variable ~\lnot a_j~. The literals ~x_i^1~ and ~x_i^2~ correspond to the gates on the ~i^\text{th}~ channel. The formula is a conjunction of alternatives of exactly two literals. This form is called the second conjunctive normal form (2-CNF). We show that this problem can be solved in linear time.

For the remaining part of the analysis, we assume that our goal is to find such a valuation of variables ~a_1, a_2, \dots, a_m~, that the following formula is satisfied:

$$\displaystyle (x_1^1 \lor x_1^2) \land (x_2^1 \lor x_2^2) \land \dots \land (x_n^1 \lor x_n^2)$$

2-CNF Formulas and Graphs

Let us consider an undirected graph ~G = (V, E)~ with vertices corresponding to all possible literals:

$$\displaystyle V = \{a_1, \lnot a_1, a_2, \lnot a_2, \dots, a_m, \lnot a_m\}$$

and edges connecting pairs of literals which appear in alternatives of the formula:

$$\displaystyle E = \{(l_i^1, l_i^2) : i = 1, 2, \dots, n\}$$

Graph ~G~ is shown on the following figure.

Our goal is to select a subset ~W \subseteq V~ containing vertices corresponding to literals which have to be true in order for the formula to be true. For that, the following conditions have to be satisfied:

1. either ~a_i \in W~ or ~\lnot a_i \in W~, for ~i = 1, 2, \dots, m~
2. for every edge ~(u,v) \in E~, ~u \in W~ or ~v \in W~

Let us construct a directed graph ~G_1 = (V, E_1)~ using the definition of graph ~G~:

$$\displaystyle E_1 = \{(\lnot u, v) : (u, v) \in E\}$$

We will call it the inference graph because it can be used to find which vertices have to belong to ~W~, provided that some given vertex has already been included in it. The inference graph has ~2m~ vertices and at most ~2n~ edges. The inference for graph ~G~ is shown below.

Looking at this graph, it is easy to notice that every ~W \subseteq V~, which is a correct solution to our problem, must satisfy the condition:

$$\displaystyle (w \in W \land (w, v) \in E_1) \implies v \in W \quad (1)$$

This logical formula is equivalent to condition 2. As a result, we can search for ~W \subseteq V~ using the inference graph.

Let us denote

$$\displaystyle \operatorname{Induced}(u) = \{v : u \mapsto v\}$$

where ~u \mapsto v~ means that there exists a path from vertex ~u~ to vertex ~v~ in graph ~G_1~. Using this definition, we can easily rewrite (1) as:

$$\displaystyle w \in W \implies \operatorname{Induced}(w) \subseteq W$$

If a set ~\operatorname{Induced}(v)~ contains two opposite vertices (~w \in \operatorname{Induced}(v)~ and ~\lnot w \in \operatorname{Induced}(v)~) we will call the vertex ~v~ problematic.

Let us introduce another kind of undirected graph: a conflict graph. Using condition 2, we can say that for every edge ~(u, v) \in E~ of graph ~G~, it is not possible for ~\lnot u~ and ~\lnot v~ to be both in ~W~. We can say that these vertices are in conflict. Therefore, we can build a conflict graph ~G_2 = (V, E_2)~ where:

$$\displaystyle E_2 = \{(\lnot u, \lnot v) : ((u, v) \in E) \lor ((v, u) \in E)\}$$

Conflict graph for our example is shown below.

Using these definitions and facts, we can show a solution to the problem.

Polynomial Solution

Using previously introduced definitions, we can solve this problem with the following method:

1. ~W = \emptyset~
2. while ~|W| < m~ repeat
   • let ~x~ be a vertex such that ~x \notin W~ and ~\lnot x \notin W~
   • if both ~x~ and ~\lnot x~ are problematic then solution does not exist (stop the algorithm)
   • let ~v~ be a non-problematic vertex among ~x~ and ~\lnot x~
   • ~W := W \cup \operatorname{Induced}(v)~
3. ~W~ is a correct solution for our problem

It is not obvious that this algorithm always returns a correct answer. To see that, let us show the following lemma.

Lemma 1. Let ~A~ be a set of vertices ~a~, such that ~a \notin \operatorname{Induced}(v)~ and ~\lnot a \notin \operatorname{Induced}(v)~. If vertex ~v~ is non-problematic then there is not an edge in the conflict graph between any pair of vertices from ~A~ and ~\operatorname{Induced}(v)~.

Proof: Let ~a~ be a vertex from ~A~ and ~u~ be a vertex from ~\operatorname{Induced}(v)~. If there was a conflict between ~a~ and ~u~, there would have to be an edge ~(u, \lnot a)~ in the inference graph ~G_2~. As a result, there would have to be: ~\lnot a \in \operatorname{Induced}(u) \subseteq \operatorname{Induced}(v)~. But ~\lnot a \notin \operatorname{Induced}(v)~ by the definition of ~A~. ■

This Lemma shows the correctness of the presented algorithm — setting the value of a certain variable in a way not leading to a contradiction does not affect the vertices not belonging to ~\operatorname{Induced}(v)~ and thus leads to a proper solution, if one exists. This solution has the overall time complexity ~\mathcal O(m(n+m))~, as checking if a vertex is problematic may take time proportional to the size of the graph.

Model Solution

Let us think about strongly connected components of the inference graph. (Two vertices ~u~ and ~v~ belong to the same strongly connected component if and only if there is a path from ~u~ to ~v~ as well as from ~v~ to ~u~). Strongly connected components of an inference graph have a very useful property for us: for any component ~C \subseteq V~, either ~C \subseteq W~, or ~C \cap W = \emptyset~, as every vertex induces its whole component. As a result, we can consider the graph of components ~G_c = (V_c, E_c)~, whose vertices are strongly connected components of graph ~G_1~ and edges are inherited from that graph in a natural way. There is a simple algorithm computing strongly connected components of a graph in ~\mathcal O(n+m)~ time.

Obviously, the graph of components is a directed acyclic graph. We sort it topologically and consider its vertices in non-ascending order. This can be done in linear time as well.

We say that we accept a component when that component is chosen and included in ~W~ while performing the algorithm. Similarly, we say that we reject a component if we decide not to choose the component. Note that if we reject a component, we have to reject all its predecessors as well. Similarly, if we accept a component, we have to accept all the components induced by it.

These observations lead to a more efficient version of the previous algorithm:

1. Generate the inference graph ~G_1~.
2. Find strongly connected components of ~G_1~ and build a graph of components ~G_c~.
3. If there are two opposite vertices in a component, reject this component (and all its predecessors).
4. Sort the components topologically, and process them in non-ascending order:
   • If the current component has not been rejected yet, accept it.
   • For each vertex in the accepted component, reject the component containing the opposite vertex (and consequently all its predecessors).
5. If exactly ~m~ vertices have been accepted, they form a correct solution. Otherwise, a solution does not exist.

Because of the topological ordering of components, each time we accept a component ~C~, all components induced by ~C~ have already been accepted. Indeed, if one of those components had been rejected before, then ~C~ would also have been rejected as its predecessor. It is also clear that set ~W~ does not contain any conflicts. As a result, if the algorithm finds a solution, it is correct. All we have to do is to show that if a solution exists, this algorithm will find it. It is a consequence of the previous algorithm and Lemma 1, as we reject all problematic vertices in the third step of our algorithm.

As we mentioned before, steps 1–3 can be done in linear time. Moreover, we accept or reject each component exactly once. Therefore, the fourth step also runs in linear time. Hence, the running time of the presented algorithm is ~\mathcal O(n+m)~.