the prevail condition of which does not involve w**. This operator is extended to a pair of**
operators:

$$\begin{array}{r l}{A^{\prime}}&{{}=}\\ {A^{\prime\prime}}&{{}=}\end{array}$$
$\{\text{pre}:\{b_{u}\},\text{post}:\{\text{w}_{u}\},\text{prv}:\{\text{b}_{u},\text{b}_{w}\}\}$  $\{\text{pre}:\{\text{b}_{u}\},\text{post}:\{\text{w}_{u}\},\text{prv}:\{\text{b}_{u},\text{w}_{w}\}\}$
corresponding to the possible values of w**. In what follows, we refer to the operator set**
resulting from such a compilation of Λ as Λ⊲⊳**. Note that, under the assumption of constantly**
bounded maximal indegree κ of the causal graph, compiling Λ into Λ⊲⊳ **takes only polynomial**
time, since, for every variable v, |Λ
⊲⊳
v| ≤ 2 κ+1**, and thus** |Λ
⊲⊳| = O(n2 κ+1).

Given the maximal sequences σ(w1), . . . , σ(wk**) and the operator set Λ**⊲⊳
v **we construct**
a directed graph (denoted as G′e
(v)) that captures all (and only) feasible **sequences of, up**
to n, value changes of v**, where each value change is annotated with the corresponding**
assignment on pred(v**). Although the number of the captured sequences can be exponential**
in n**, the size of** G′e
(v) is polynomial in n**. With respect to this graph, the problem of finding**
the maximal sequence σ(v**) is reduced to the problem of finding a longest path from a given**
node to an arbitrary other node in a directed acyclic graph.

The graph G′e(v**) is created in three incremental steps. At the first step, given the**
maximal sequences σ(w1), . . . , σ(wk**) and the operator set Λ**⊲⊳
v **we construct a directed labeled**
graph G(v**) capturing information about all sequences of assignments** on pred(v**) that can**
enable n or less value flips of v. The graph G(v**) is defined as follows:**
1. G(v) consist of η **nodes, where**

$$\eta=\left\{\begin{array}{l l}{{n,}}&{{((n=2j)\mathrm{~and~}(v^{0}=v^{*}))\mathrm{~or~}}}\\ {{}}&{{((n=2j+1)\mathrm{~and~}(v^{0}\neq v^{*})),\ j\in\mathbb{N}}}\\ {{n-1,}}&{{\mathrm{otherwise~}}}\end{array}\right.$$

2. G(v) forms a 2-colored multichain**, i.e., (i) the nodes of the graph are colored by black**
and white, starting by black; (ii) there are no two subsequent nodes with the same color; (iii) for 1 ≤ i ≤ η − 1, edges from the node i are only to the node i **+ 1.**
Observe that such a construction of G(v**) promises that the color of the last node will** be consistent with v
∗.

3. The nodes of G(v**) are denoted precisely by the elements of the maximal sequence**
σ(v**), i.e.,** b ivstands for the i**th black node in** G(v).

4. Suppose that there are m **operators in Λ**⊲⊳
v that change the value of v from bv to wv**. In**
this case, for each i, there are m **edges from** b iv to w iv
, and |Λ
⊲⊳ v | − m **edges from** w iv to b i+1 v**. All edges are labeled by the prevail conditions of the corresponding operators,**
i.e., a k-tuple of the values of w1, . . . , wk. This tuple is denoted by l(e**) (label of the**
edge e) and its component, corresponding to a predecessor wi**, is denoted by** l(e)wi
.
This formal definition of G(v**) is relatively complicated, thus we provide a demonstrating**
example: Suppose that we are given a problem instance over 5 variables, and we consider