$$ \leq \max_{\substack{i \in [1:p] \\ q \leq i}} (\text{bg}(T^{\diamond q}) - (q-1)) \text{ by assumption} $$

$$ \leq \max_{q \in [1:p]} (\text{bg}(T^{\diamond q}) - (q-1)) \text{ putting more terms in the max is allowed} $$

$$ = \text{bg}(T^{\diamond p}) \text{ with Corollary 3} $$

□

With the following Lemma, we show that one can commit to any prefix of a canonical solution, then any canonical solution for the remaining subgraph yields a global canonical solution.

**Lemma 5** Given $T$ a canonical schedule, we write $P$ such that $T = P$ if $T$ canonical one-sided and $T = P\bar{Q}$ if $T$ canonical two-sided. Let $H \subseteq P$. Let $S'$ be a canonical solution of $G \setminus H$ then $S = H \cdot S'$ is a canonical solution of $G$.

*Proof* Suppose first that $G \setminus H$ is a one-sided graph and $S'$ a canonical schedule (i.e. $S'$ is a canonical one-sided schedule). Write $S$ for the canonical schedule starting with $H$ and $S' = S \setminus H$, i.e. $S = H \cdot S'$; and $d = \delta(H)$.

Let $p \in [1 : k_L] \cup \{\infty\}$. We distinguish two cases:

* Case A: $H$ has a prefix that is a $p$-sequence, then $S^{\diamond p} = H^{\diamond p} = P^{\diamond p} = T^{\diamond p}$

* Case B: no prefix of $H$ is a $p$-sequence, then $H \subseteq S^{\diamond p}$ and $H \supseteq P^{\diamond p} = T^{\diamond p}$. In particular, $S^{\diamond p} = H \cdot S'^{\diamond p+d}$ and $T^{\diamond p} = H \cdot T'^{\diamond p+d}$ with $T' = T \setminus H$. We can then rewrite:

$$ \begin{aligned} \text{bg}(S^{\diamond p}) &= \max(\text{bg}(H), \text{bg}(S^{\diamond p} \setminus H) + d) \text{ with Prop 10} \\ &= \max(\text{bg}(H), \text{bg}(S'^{\diamond p+d}) + d) \\ &\leq \max(\text{bg}(H), \text{bg}(T'^{\diamond p-d}) + d) \text{ since } S' \text{ is canonical one-sided} \\ &= \max(\text{bg}(H), \text{bg}(T^{\diamond p} \setminus H) + d) \\ &= \text{bg}(T^{\diamond p}) \text{ with Prop 10} \end{aligned} $$

We have shown that $\forall p \in [1 : k_L] \cup \{\infty\}$, $\text{bg}(T^{\diamond p}) \geq \text{bg}(S^{\diamond p})$ and since $T$ is canonical, by definition, $\forall U$-sequence of $G$, $\text{bg}(U) \geq \text{bg}(T^{\diamond p}) \geq \text{bg}(S^{\diamond p})$ and $S$ is canonical which concludes the proof for the one-sided case.

We now suppose that $G \setminus H$ is a two-sided graph and $S'$ is canonical (i.e. $S'$ is a canonical two-sided schedule). We denote $S' = P'\bar{Q}'$. (with $P'$ and $Q'$ both one-sided, with Proposition 3).

We put $S = HS' = HP'\bar{Q}'$. We will show that $Y = HP'$ is a divider.

First, note that $V(Y) = V(H \cup P')$ is a licit subset thanks to lemma 2. Note that $V(P')$ is a divider of the graph $G \setminus H$. Now, suppose by contradiction that $Y$ is not a divider of $G$, which implies by definition of the balance that $\delta(Y) = \delta(HP') > \delta(P) \leftrightarrow \delta(P') > \delta(P \setminus H)$. It contradicts the fact that $P'$ is a divider of $G \setminus H$. Thus, $V(Y) = V(H \cup P')$ is divider of $G$.

One can apply current lemma in the one-sided case on prefix $H$ prefix of schedule $P$ canonical over the one-sided graph $G[P]$ and $P'$ canonical over the one-sided graph $G[P'] = G[Y] \setminus H$. Thus, $Y$ is canonical one-sided and $V(Y)$ is a divider. Additionally,
## B.2 Proof of Proposition 2:

# Appendix C Re-derivation of Tamaki's algorithm for directed pathwidth

For completeness, we include here a re-derivation of the results of [1], with the slight modification mentioned in the main text related to *pruning*. It results in an algorithm with a $O(n^{\rho+2})$ complexity, slightly different from the $O(n^{\rho+1})$ announced in [1]. The re-derivation follows the same strategy as in the original article, and re-uses most of the notations.

## C.1 Commitment lemma - shortest non-expanding extensions (SNEKFEs)

**Notations and definitions.** In a directed graph, $d^-(u)$ denotes the in-degree of a node $u$. We work with layouts of vertices, i.e. ordered sequences of vertices, not necessarily containing all vertices. A partial layout $\sigma$ is called feasible valid if $\forall$ prefix $p$ of $\sigma$ we have $d^-(p) = |N^-(p)| \le k$. A partial layout which is completable into a valid full layout (for the entire digraph $G$) is called strongly feasible or just completable into a full solution. An extension $\tau$ of $\sigma$ is a valid partial layout with $\sigma$ as one of its prefixes. A shortest non-expanding extension of $\sigma$ is an extension $\tau$ such that $d^-(\tau) \le d^-(\sigma)$ and $\forall \rho \text{ s.t. } V(\sigma) \subseteq V(\rho) \subseteq V(\tau)$, $d^-(\rho) > d^-(\sigma)$. In the rest of this note, we will write SNEKFE for shortest non-expanding extension.

**Lemma 1 - Commitment Lemma - shortest non-expanding extensions.** If $\sigma$ is completable into a full solution, and $\tau$ is a SNEKFE of $\sigma$, then $\tau$ is also completable into a full solution.

In fact, a more general version is true: $\rho$ could be allowed to be equal in $d^-$ to $\tau$ before rising again. The proof relies on the fact that, for any two subsets $X, Y$ of vertices of $G$:

$$d^-(X \cup Y) + d^-(X \cap Y) \le d^-(X) + d^-(Y)$$

*Proof* If $\sigma$ is completable into a full solution, then $\exists F$ such that $\sigma \cdot F$ is a valid layout for $G$. Let us reshuffle $F$ into $(\tau \setminus \sigma) \cdot F'$. Within both parts, the ordering of elements is the same as in $F$. $\tau \cdot F'$ is now a complete layout for $G$. Is it valid?

Consider a prefix $P$ of $\tau \cdot F'$. If $P$ is contained within $\tau$, $d^-(P) \le k$ by the validity of $\tau$.

Else, if $P$ contains some of $F'$, then $P = P' \cup \tau$ for $P'$ a certain prefix of $\sigma \cdot F$. As for $P' \cap \tau$, which we call $\rho$ it verifies $V(\sigma) \subset V(\rho) \subset V(\tau)$ and therefore $d^-(\rho) \ge d^-(\sigma) \ge d^-(\tau)$ by definition of a SNEKFE, with the equality only potentially happening if $\rho = \sigma$ or $\rho = \tau$.

We therefore have:

$$ \begin{aligned} d^-(P) &= d^-(P' \cup \tau) \\ &\le d^-(P') + d^-(\tau) - d^-(\rho) \end{aligned} $$
$Q'$ remains canonical one-sided, and by definition, $Y \overleftarrow{Q'} = HP' \overleftarrow{Q'}$ is canonical two-sided which concludes the proof. □

## 5.4 Existence of canonical schedules

We show an existential proof of canonical schedules for any graph $G$ (Lemma 8), thus making sure our algorithm 4 always finds a solution. The proof relies on specific motifs, called starters, that can always be found in the graph and safely used as prefixes for canonical solutions.

**Definition 6** A starter is a sequence $X$ such that

* $X$ is licit with $\delta(X) = -1$

* (budget minimality) for any licit set $X'$ with $\delta(X') \le -1$, $\text{bg}(X') \ge \text{bg}(X)$

* (inclusion minimality) for any licit set $X' \subseteq V(X)$, $\delta(X') \ge 0$.

**Lemma 6** Any graph with $|L| < \alpha(G)$ contains a starter.

*Proof* Since $|L| < \alpha(G)$, there exist licit sequences $S_X$ with $\delta(S_X) = -1$ (e.g., pick any licit schedule $S$ of a Maximal Independent Set of $G$, and let $S_X = S^{\triangle 1}$). Among such sequences, pick one that minimizes the pair $(\text{bg}(V(S_X)), |V(S_X)|)$ in lexicographical order.

Aiming at a contradiction, assume that $X = V(S_X)$ is not a starter. Then, since $X$ satisfies the first two conditions (by the choice of $S_X$), there must exist a licit set $X'$ with $X' \subseteq X$ and $\delta(X') = -1$.

By minimality of $(\text{bg}(X), |X|)$, since $|X'| < |X|$, for any schedule $S_{X'}$ of $X'$, we have $\text{bg}(S_{X'}) \ge \text{bg}(X) + 1$. In particular, $S_X \cap X'$ (that is licit by Lemma 2) reaches budget at least $\text{bg}(X) + 1$. Thus there exists a prefix $P$ of $S_X$ such that $\delta(P \cap X') = \text{bg}(X) + 1$ (pick the shortest possible such prefix). Consider now the set $Y' = V(P) \setminus X'$. We have

$$ \delta(P) = \delta(Y') + \delta(P \cap X') = \delta(Y') + \text{bg}(X) + 1 $$

and $\delta(P) \le \text{bg}(X)$

so $\delta(Y') \le -1$

Overall, $Y' \cup X' = P \cup X'$ is a licit set (with Lemma 2) and $\delta(Y' \cup X') = \delta(X') + \delta(Y') \le \delta(X') - 1 \le -2$. Note also that $Y' \cup X' \subseteq X$ (it is a subset by construction, and it is strict since it $\delta(X) = -1 \ge -2 \ge \delta(Y' \cup X')$). In addition, $\text{bg}(Y' \cup X') \le \text{bg}(X)$ (by construction of $X$) which contradicts $X$ having minimum size. □

**Lemma 7** For any licit sequence $S$ (not necessarily a full schedule) with $\delta(S) \le -1$, and any optimal schedule $S_X$ of a starter $X$, $\text{bg}(S_X \cdot S \setminus X) \le \text{bg}(S)$.
$$ \leq d^{-}(P') \leq k $$

$\tau \cdot F'$ is therefore a valid complete layout for $G$, and $\tau$ is completable into a full solution. □

Let us now describe more precisely what SNEKFEs might look like. We show that they can only be of three types, and formalize it into the next lemma. Its proof relies on the fact that, by adding a single vertex $u$ to a partial layout $\sigma$, we may only decrease $d^{-}(\sigma)$ by at most 1, since $d^{-}(\sigma) = |N^{-}(\sigma)|$. We obtain this decrement of 1 if $u$ is a predecessor to a vertex of $\sigma$, and does not introduce any new predecessor itself when added.

**Lemma 2 - SNEKFE types.** *a SNEKFE $\tau$ of a partial layout $\sigma$ may only be of three types:*

* type-(i): single-vertex "decreasing" extension: $\tau = \sigma \cdot u$ for some vertex $u$ and $d^{-}(\sigma \cdot u) = d^{-}(\sigma) - 1$

* type-(ii): single-vertex "non-decreasing" extension: $\tau = \sigma \cdot u$ for some vertex $u$ and $d^{-}(\sigma \cdot u) = d^{-}(\sigma)$

* type-(iii): several vertices "shortcut" extension: $\tau$ adds strictly more than one vertex to $\sigma$ and $d^{-}(\tau) = d^{-}(\sigma)$.

*Proof* For single vertex extensions, the two possible types follow from the observation above that the addition of one vertex to a layout can only decrease $d^{-}$ by at most 1.

For SNEKFEs composed of more than one vertex, observe that if $d^{-}(\tau) < d^{-}(\sigma)$, then by considering the prefix $\rho$ of $\tau$ obtained by removing just 1 vertex to $\tau$, we would have $d^{-}(\rho) \leq d^{-}(\tau) + 1 \leq d^{-}(\sigma)$. This stems from the observation above that $d^{-}$ may only decrease by at most 1 when adding a vertex. $\rho$ would be a non-expanding extension of $\sigma$ shorter than $\tau$, yielding a contradiction. □

## C.2 Algorithm

In this section, we restrict ourselves to a pure description of the algorithm, delaying the justification of its correctness and complexity to the “Analysis” section below.

**Tree of prefixes (trie).** We will build a tree of prefixes of all possible layouts. We prune the tree during its construction thanks to the commitment lemma, as justified in the next section. We call $S_i$ the $i^{th}$ level of the tree of prefixes. I.e. the elements of the tree of length $i$. $S_0 = \{\emptyset\}$.

**Algorithm.** $S_{i+1}$ is generated in the following way given $S_i$:

For each $\sigma \in S_i$:

1. We generate all feasible immediate extensions to $\sigma$ and add them to the tree. I.e the node $\sigma$ now has the following children set: $\{\sigma \cdot u \text{ s.t. } d^{-}(\sigma \cdot u) \leq k\}$

2. If some of these immediate extensions verify $d^{-}(\sigma \cdot u) \leq d^{-}(\sigma)$, then they are SNEKFEs of $\sigma$. In that case, we do the following:

a. We choose 1 arbitrarily and prune the others.
**Proof** Let $S' = S_X \cdot S \setminus X$ and, based on the definition of budget, we need to show that $\forall P' \subseteq S'$, $\delta(P') \le \text{bg}(S)$. We take $P'$ prefix of $S'$. If $P' \subseteq S_X$ then, by definition of starter (budget minimality condition) with $\delta(S^{\text{cl}}) \le -1$, we have $\text{bg}(S_X) \le \text{bg}(S^{\text{cl}}) \le \text{bg}(S)$, thus by budget definition $\delta(P') \le \text{bg}(S_X) \le \text{bg}(S)$. Otherwise, $P' = S_X \cdot P \setminus X$ for some prefix $P$ of $S$ and $V(P') = V(P) \cup X$. By Lemma 2, $\delta(P') = \delta(P) + \delta(X) - \delta(P \cap X)$ (*). By inclusion minimality of $X$, since $V(P \cap X) \subseteq X$ we have, by inclusion minimality, $\delta(P \cap X) \ge -1 = \delta(X)$. By rewriting that in (*), we have $\delta(P') \le \delta(P) \le \text{bg}(S)$ which concludes the proof. □

**Lemma 8** Any graph admits a canonical schedule.

**Proof** We show the property by induction on one-sided graphs $G$. In the special case $|L| = \alpha(G)$ (i.e. $k_L = 0$), any optimal schedule is canonical (Proposition 12), so at least one exists.

Assume now that $G$ is one-sided with $|L| < \alpha(G) = |R|$, let $k = k_L(G) > 0$. By Lemma 6, $G$ contains a starter $X$ with optimal schedule $S_X$, and by induction $G \setminus X$ contains a canonical schedule $C$. Let $S = S_X \cdot C$, we show that $S$ is canonical.

Consider any $p \in [1 : k] \cup \{\infty\}$ and let $T$ be any $p$-sequence of $G$. Note that $T \setminus X$ is licit in $G \setminus X$. Additionally, $\delta(T \cap X) \ge -1$ as $\delta(T \cap X) = -1$ if $T \cap X = X$ or $\delta(T \cap X) \ge 0$ by inclusion minimality otherwise. For $p \in [1 : k]$, $\delta(T \setminus X) = \delta(T) - \delta(T \cap X) = -p - \delta(T \cap X) \le -p+1$. Thus, $T \setminus X$ contains a $(p-1)$-sequence as a prefix, so $\text{bg}(T \setminus X) \ge \text{bg}(C^{\text{cl}})$ since $C$ is canonical. For $p = \infty$, $T \setminus X$ is an $\infty$-sequence of $G \setminus X$, so $\text{bg}(T \setminus X) \ge \text{bg}(C)$, and $\text{bg}(C) \ge \text{bg}(C^{\text{cl}})$ as $C^{\text{cl}}$ is a prefix of $C$ using the budget definition. Overall,

$$ 
\begin{aligned}
\text{bg}(S^{\text{cl}}) &= \max(\text{bg}(S_X), \text{bg}(C^{\text{cl}})) - 1) \quad (\text{Corollary 4}) \\
&\le \max(\text{bg}(S_X), \text{bg}(T \setminus X)) - 1) \\
&= \text{bg}(S_X \cdot T \setminus X) \quad (\text{Proposition 10}) \\
&\le \text{bg}(T) \quad (\text{Lemma 7})
\end{aligned}
$$

So $S$ is indeed canonical for $G$.

Assume finally that $G$ is two-sided. Then $G$ contains a divider $Z$. Pick $P, Q$ canonical schedules of $G[Z]$ and $\overleftarrow{G} \setminus \overleftarrow{Z}$ respectively (both of them are canonical one-sided). Then $S = P \cdot \overleftarrow{Q}$ is canonical for $G$. □

## 5.5 Merging canonical schedules through slice-based shuffle

We now want to show that reordering some “blocks” of canonical schedules $C_1$ and $C_2$ for disjoint graphs $G_1$ and $G_2$ is sufficient to obtain a canonical schedule $S$ on the graph $G_1 + G_2$. This reordering is called a “shuffle”, and is the main operation justifying Algorithm Canonical Merge (Algorithm 3). The following formally defines the shuffle operation, we then show in Section 5.5.1 that a minimal shuffle of canonical solutions in one-sided graphs is also canonical, and we then extend this result to two-sided graphs in Section 5.5.2.
40

Parameterized Independent Set Reconfiguration for RNA kinetics

b. If the chosen element verifies $d^-(\sigma \cdot u) = d^-(\sigma) - 1$ (the only possibility if $d^-(\sigma \cdot u) < d^-(\sigma)$), then we in addition look for a prefix $\eta$ of $\sigma$ verifying $d^-(\eta) = d^-(\sigma \cdot u)$ and $d^-(\rho) > d^-(\eta) \quad \forall \rho \text{ s.t. } \eta \subseteq \rho \subseteq \sigma \cdot u, \rho \neq \eta, \rho \neq \sigma \cdot u$. If such an $\eta$ is found, then any part of tree branching off the path from $\eta$ to $\sigma \cdot u$ is removed. Note that this might shorten the overall loop over $\sigma \in S_i$.

End Algorithm

C.3 Analysis

This section will be composed of three parts. In the first one, we define an invariant property ("internally pruned") for trees of prefixes of layouts of vertices. In the second one, we show that, in the algorithm presented in the previous section, the tree of prefixes verifies the invariant at all times, and prove the correctness of the algorithm. Finally, in the third part, we analyze the size of trees of prefixes verifying the invariant, proving that each level $S_i$ of such a tree has a size $\le n^k$, yielding a complexity analysis of the algorithm.

C.3.1 Internally pruned trees of prefixes

**Definition - Internally pruned.** A tree $\mathcal{T}$ of prefixes of layouts of vertices (such as the one used in the algorithm in the previous section) is said to be internally pruned if for all pairs $(\sigma, \tau)$ of nodes of $\mathcal{T}$ such that $\tau$ is a shortest non-expanding extension of $\sigma$, all nodes on the path from $\tau$ (included) to $\sigma$ (excluded) in $\mathcal{T}$ have degree exactly 2. I.e. there are no sub-parts of the tree rooted on the path from $\tau$ (included) to $\sigma$ (excluded)

We use the term “internally” to emphasize the fact that, in a context where we apply the definition of “internally pruned” to a partially constructed $\mathcal{T}$ within the algorithm of the previous section, More (“external”) pruning of the tree might be achieved further in the construction of the tree, as new SNEKFEs are discovered (see below for the justification of why new SNEKFEs are indeed discovered at step 2.b of the algorithm).

C.3.2 Invariant and correctness

**Lemma 3 - Invariant.** Throughout the execution of the algorithm presented in the previous section, the tree $\mathcal{T}$ of prefixes of layouts of vertices remains “internally pruned” at all times

*Proof* The tree $\mathcal{T}$ starts off with one node for the empty sequence. It is therefore internally pruned.

Suppose now that the tree of prefixes $\mathcal{T}$ is internally pruned at an intermediate step in the algorithm, then the next building step always consists in considering a leaf $\sigma$ and executing step 1. and 2. of the algorithm. Several cases may arise:
40

**Definition 7** Let $G = G_1+G_2$ and $C_1, C_2$ be schedules over $G_1$ and $G_2$ respectively. If $C_1$ and $C_2$ are both canonical one-sided, a schedule $S$ is a *shuffle* of $C_1, C_2$ if any of the following applies:

* $k_L(G) = 0$ (so $k_L(G_1) = k_L(G_2) = 0$)

* $k_L(G_1) > 0$, $S^{\triangle 1} = C_1^{\triangle 1}$ and $S \setminus S^{\triangle 1}$ is a shuffle of $C_1 \setminus C_1^{\triangle 1}$ and $C_2$

* $k_L(G_2) > 0$, $S^{\triangle 1} = C_2^{\triangle 1}$ and $S \setminus S^{\triangle 1}$ is a shuffle of $C_1$ and $C_2 \setminus C_2^{\triangle 1}$

Otherwise, if $C_1$ or $C_2$ is canonical two-sided, we write $C_1 = P_1 \overleftarrow{T_1}$ and $C_2 = P_2 \overleftarrow{T_2}$ with one of $T_1$ or $T_2$ possibly empty and a schedule $S$ is a *shuffle* if $S = P_1 \overleftarrow{T_1}$ and $P$ shuffle of $P_1, P_2$ (canonical one-sided) and $T$ shuffle of $T_1, T_2$ (Note that $T = T_i, i = 1, 2$ is a shuffle if $T_{(i+1) \mod 2} = \emptyset$). Furthermore, if $C_1$ and $C_2$ are both canonical one-sided, a shuffle $S$ is *minimal* if $k_L(G) = 0$ and $S$ is optimal for $G$, or if $k_L(G) > 0$ and the following holds:

* $bg(S^{\triangle 1})$ is minimal among all shuffles (i.e. $= \min(bg(C_1^{\triangle 1}), bg(C_2^{\triangle 1}))$ whenever both prefixes are defined)

* $S \setminus S^{\triangle 1}$ is a minimal shuffle

Otherwise, if $C_1$ or $C_2$ is canonical two-sided, a shuffle $S = P_1 \overleftarrow{T_1}$ of $C_1, C_2$ is *minimal* if $P$ and $T$ are minimal.

### 5.5.1 Slice-based shuffle in one-sided graphs

In this section, we assume that $G = (V = L \cup R, E)$ is the disjoint union of two subgraphs $G_1 = (V_1, E_1)$ and $G_2 = (V_2, E_2)$. We further assume that $G$ is one-sided. We aim at proving Lemma 15: a canonical solution for $G$ can be obtained by some form of interleaving of canonical solutions from $G_1$ and $G_2$. The overall strategy is to start with any canonical solution for $G$ (that exists by Lemma 8), and show that it can be rearranged first to be *simple* (each slice $S^{\diamond i}$ is included either in $V_1$ or $V_2$) and then rearranged again to follow any two prescribed solutions for $G_1$ and $G_2$.

**Definition 8** Let $S$ be a schedule over a one-sided graph $G$. We say that $S$ is *simple* if for each $i \in [1 : k_L(G)]$, $V(S^{\diamond i}) \subseteq V_1$ or $V(S^{\diamond i}) \subseteq V_2$.

In particular for graphs with $k_L(G) = 0$, all schedules are simple.

**Lemma 9** Let $T$ be a simple schedule. We write $T_i = T \cap V_i, \forall i = 1, 2$. Then $\forall i = 1, 2$ there exists a strictly increasing integer sequence $\Theta_i = [p_1, \dots, p_{k_L(G_i)}]$ such that $\forall i = 1, 2, \forall q \in [1, k_L(G_i)], T_i^{\diamond q} = T^{\diamond p_q}$.

*Proof* One can rewrite $T$ by slices:

$$T = T^{\diamond 1} T^{\diamond 2} \dots T^{\diamond k}$$

We annotate every $T^{\diamond i}$: we add $i$ to the initially empty list $\Theta_1$ (resp. $\Theta_2$) when $V(T^{\diamond i}) \subseteq V_1$ (resp. $V_2$) which is always the case with $T$ simple.
* If all of the immediate extensions are such that {$d^-(\sigma) < d^-(\sigma \cdot u) \le k$}, then no new SNEKFEs are generated when adding them to the tree. (if $\sigma \cdot u$ is a SNEKFE of some $\eta$ up the tree, then $\sigma$ is shorter and also non-expanding). After the addition of the immediate extension, the tree is therefore still internally pruned.

* If one of these immediate extensions verifies $d^-(\sigma \cdot u) = d^-(\sigma)$ but none of them verify $d^-(\sigma \cdot u) < d^-(\sigma)$, then one of these extensions is a SNEKFE of $\sigma$, and is kept while the others are pruned. However, this is the only SNEKFE introduced by the extension. Therefore, the pruning of immediate extensions other than the selected one is enough to keep the tree internally pruned.

* If one of the immediate extensions verifies $d^-(\sigma \cdot u) = d^-(\sigma) - 1$, then one of the immediate extensions is selected and the others are pruned, as in the previous case. However, in addition, $\sigma \cdot u$ might be a new shortest non-expanding extension of a node $\eta$ up the tree.

If this is the case, then there is only one such $\eta$, per the definition of shortest non-expanding extensions.

We argue that the conditions used in the algorithm indeed detect such an $\eta$. If $\sigma \cdot u$ is a SNEKFE of $\eta$, then the conditions described in the algorithm (that $d^-(\sigma \cdot u) = d^-(\eta)$, and $d^-(\rho) > d^-(\eta)$ for any $\rho$ on the path from $\eta$ to $\sigma \cdot u$) are verified.

Conversely, if the conditions are verified, then suppose $\eta$ has a shorter non-expanding extensions $\tau$. $\tau$ cannot be on the path from $\eta$ to $\sigma \cdot u$ as that would imply $d^-(\tau) > d^-(\eta)$. Since $\tau$ is shorter than $\sigma \cdot u$, $\tau$ has been generated in a previous step of the algorithm. At this point, step 2.b of the algorithm would have pruned the path to $\sigma$, which cannot be visited, leading to a contradiction.

Therefore, the potentially newly introduced SNEKFE is detected, and the corresponding pruning is carried out, leaving the tree internally pruned

Therefore, after each extension of the tree throughout the algorithm, the tree remains internally pruned. □

We quickly finish this sub-section with a proof of correctness of the algorithm.

**Lemma 4 - correctness.** If the graph $G$ allows for a full $k$-feasible solution, then there is such a solution among the leaves of the tree of prefixes $T$ generated by the algorithm.

*Proof* Denote the set of full solutions $S$, and suppose all solutions are absent from $T$. $\forall \sigma \in S$, there is some (possibly empty) prefix of $\sigma$ in $T$. We pick $\sigma \in S$ allowing for the largest prefix $\eta \in T$, i.e:

$$ \sigma = \underset{\sigma' \in S}{\operatorname{argmax}} \left[ \max_{\eta \subseteq \sigma', \eta \in T} |\eta| \right] $$

Take $\eta$ the largest prefix of $\sigma$ belonging to $T$. If the path from $\eta$ to $\sigma$ has been pruned, it is because $\eta$ is on the path from $\eta'$ to $\tau$, with $\tau$ shortest non expanding extension of $\eta'$, and $\tau$ is not a prefix of $\sigma$.
<figure><img src="image_13.png" /></figure>

<figure><img src="image_14.png" /></figure>

<figure><img src="image_15.png" /><figcaption>**Fig. 11** Illustrations for the object in the proof of Lemma 10. (A) is the *T* schedule, (B) the constructed *S* schedule and (C) the *Z* schedule.</figcaption></figure>

Each $\Theta_i$ is indeed an increasing sequence and one can check by induction on $p$ that $T_i^{\diamond q} = T^{\diamond p_q}$ and. $\square$

**Lemma 10** Let $G = G_1 + G_2$ one-sided with $|L| < \alpha(G)$. There exists $S$ canonical one-sided schedule of $G$ with $V(S^{\diamond 1}) \subseteq V_i$ for some $i \in \{1, 2\}$.

*Proof* Let $T$ be a canonical schedule of $G$ (one exists by Lemma 8). Let $P$ be the shortest prefix of $T$ such that $\delta(P \cap V_i) = -1$ for some $i$ (assume wlog. that $i=1$): at least one exists (and is a prefix of $T^{\diamond 1}$), since $\delta(T^{\diamond 1} \cap V_1) + \delta(T^{\diamond 1} \cap V_2) = \delta(T^{\diamond 1}) = -1$. Note that by definition, for any strict prefix $Z$ of $P$, $\delta(Z \cap V_1) \ge 0$, and $\delta(Z \cap V_2) \ge 0$.

Let $Q = (P \cap V_1) \cdot (P \cap V_2)$, and $S = Q \cdot (T \setminus P)$. Let $p \in [1 : k_L(G)] \cup \{\infty\}$ and $D$ be a prefix of $S^{\diamond p}$ such that $\delta(D) = \text{bg}(S^{\diamond p})$ that always exist by definition of the budget. We show that $\delta(D) \le \text{bg}(T^{\diamond p})$, which is enough to show that $S$ is canonical with $T$ canonical.
The path from $\eta$ to $\sigma$ is pruned only when $\tau$ is visited. Hence $\tau \in \mathcal{T}$, otherwise, the path from

Per the commitment lemma, $\tau$ is the prefix of a full solution $\sigma''$. But $|\tau| > |\eta|$, contradicting the choice of $\sigma$. $\square$

### C.3.3 Signature analysis

We show here that, at any point in the algorithm, thanks to the pruning, $\forall i, \quad |S_i| = O(n^k)$.

**Definition - signature.** Consider $\sigma \in S_i$ for some $i$, within the internally pruned tree generated by the algorithm, valid partial layout. We call signature of $\sigma$ the set of vertices obtained from $V(\sigma)$ by removing, given any pair $(\eta, \rho)$ of prefixes of $\sigma$ such that $\rho$ is a SNEKFE of $\eta$, all vertices in $\rho \setminus \eta$.

Given $\sigma \in S_i$, its signature can be easily computed by looking at the path from the root to $\sigma$: any vertex chosen out of several available possibilities is part of the signature, while any vertex that was the only possibility at the point of its choosing isn't.

**Lemma 5 - Same signature same sequence.** If $sgn(\sigma) = sgn(\tau)$ within the pruned tree of layouts and $|\tau| = |\sigma|$ then $\sigma = \tau$

*Proof* When starting at the root and building $\tau$ and $\sigma$ by going down the tree, at every node, there are two cases:

* Either the next move is part of a SNEKFE. In this case there are no choices to be made, the added vertex is not part of the signature, and is the same for $\sigma$ and $\tau$.

* Or the next move is not part of a SNEKFE. In this case, several choices are possible, and the next added vertex will be part of the signature. Since the signatures of $\sigma$ and $\tau$ are the same, the same vertex is added to $\sigma$ and $\tau$.

At the end of this process, $\sigma$ and $\tau$ are therefore identical. $\square$

<figure><img src="image_14.png" /></figure>

**Lemma 6 - overall strictly decreasing = SNEKFE only.** Consider $\tau \in S_i$ for some $i$ partial valid layout, and $\sigma$ a prefix of $\tau$ such that:

* $d^{-}(\sigma) > d^{-}(\tau)$

* For any $\rho$ such that $\sigma \sqsubseteq \rho \sqsubseteq \tau$, $\rho \neq \tau$, we also have $d^{-}(\rho) > d^{-}(\tau)$.

Then, the suffix $\tau \setminus \sigma$ of $\tau$ corresponding to $\sigma$ can be entirely partitioned into SNEKFEs. In particular, none of its elements are part of the signature of $\tau$.

*Proof* We prove the lemma by induction on the length of the suffix $\tau \setminus \sigma$. If $|\tau \setminus \sigma| = 1$, then $\tau = \sigma \cdot u$ and $d^{-}(\tau) = d^{-}(\sigma) - 1$. $\tau$ is a type-(i) SNEKFE of $\sigma$ and the lemma is true.

If $|\tau \setminus \sigma| > 1$ and we assume the lemma true $\forall l < |\tau \setminus \sigma|$, then let us distinguish two cases related to the first element $v$ of $\tau \setminus \sigma$:

* if $\sigma \cdot v$ is a type-(i) or type-(ii) SNEKFE of $\sigma$, then we apply the induction hypothesis to the suffix $\tau \setminus (\sigma \cdot v)$ of $\tau$ and we have the result.
42 Bipartite IS Reconfiguration: General and RNA-inspired Algorithms

**Case 1:** $D \sqsubseteq P \cap V_1$. We denote $D'$ the (strict) prefix of $P$ such as $D \cap V_1 = D' \cap V_1$.
$$
\begin{align*}
\delta(D) &= \delta(D' \cap V_1) \\
&= \delta(D') - \delta(D' \cap V_2) \text{ with } \delta(D' \cap V_2) \ge 0 \text{ (otherwise } P \text{ not smallest prefix}) \\
&\le \delta(D') \\
&\le \text{bg}(D') \text{ with the budget definition} \\
&\le \text{bg}(P) \text{ with } D' \sqsubseteq P \\
&\le \text{bg}(T^{\square p}) \text{ with } P \sqsubseteq T^{\square 1}
\end{align*}
$$

**Case 2:** $P \cap V_1 \sqsubseteq D \sqsubseteq Q$. Then $D \cap V_1 = P \cap V_1$, and there exists a strict prefix $D'$ of $P$ such that $D \cap V_2 = D' \cap V_2$. By construction of $P$, $\delta(D' \cap V_1) \ge 0$. So

$$
\begin{align*}
\delta(D) &= \delta(D \cap V_1) + \delta(D \cap V_2) \\
&= \delta(P \cap V_1) + \delta(D' \cap V_2) \\
&= -1 + \delta(D') - \delta(D' \cap V_1) \\
&\le \delta(D') \\
&\le \text{bg}(T^{\square p})
\end{align*}
$$

**Case 3:** $Q \sqsubseteq D$. Let $Z = Q \cdot (T^{\square p} \setminus P)$. Note that $V(Z) = V(T^{\square p})$ as $Z$ is just a rearrangement of $T^{\square p}$. Thus $|Z| = |T^{\square p}|$ and $\delta(Z) = \delta(T^{\square p})$ as they are composed of the same elements. Then $Z$ is a $p$-sequence. By construction $Z \sqsubseteq S$, so either $S^{\square p} \sqsubseteq Z$ or $Z \sqsubseteq S^{\square p}$. As $\delta(Z) = -p$ and by definition $S^{\square p}$ stops at the first point that reaches balance $-p$. Then $S^{\square p} \sqsubseteq Z$. Thus, $|D| \le |S^{\square p}| \le |Z| = |T^{\square p}|$. We can look at the size-$|D|$ prefix of $T^{\square p}$ that we name $D'$. It has the same vertices as $D$ (i.e. $|D| = |D'|$ and $\delta(D) = \delta(D')$). With the definition of the budget, we finally have $\delta(D) = \delta(D') \le \text{bg}(T^{\square p})$.

Thus $\delta(D) \le \text{bg}(T^{\square p})$ for each prefix $D$ of $S^{\square p}$, and $\text{bg}(S^{\square p}) = \delta(D) \le \text{bg}(T^{\square p}) \le \text{bg}(U)$ for any $p$-sequence $U$ since $T$ is canonical. Thus, $S$ is canonical and satisfies $V(S^{\square 1}) \subseteq V_1$ since $S^{\square 1} = P \cap V_1$. $\square$

**Lemma 11** Let $G = G_1+G_2$ one-sided, then here exists a canonical simple schedule for $G$.

*Proof* The proof is by induction on $G$. For $|L| = \alpha(G)$, any canonical schedule is simple (and one exists by Lemma 8). Otherwise, $|L| < \alpha(G)$, by Lemma 10 there exists a canonical schedule $T$ of $G$ with $V(T^{\square 1}) \subseteq V_i$ for some $i \in \{1, 2\}$. By induction there exists $C$ a simple canonical schedule of $G \setminus T^{\square 1}$. Write $S = T^{\square 1} \cdot C$; $S$ is indeed simple, and it is canonical by Lemma 5. $\square$

**Lemma 12** For any canonical schedule $C_1$ of $G_1$ and $C_2$ of $G_2$ with $C_1^{\square k_L(G_1)} = C_1$ and $C_2^{\square k_L(G_2)} = C_2$, there exists a simple canonical schedule $S$ of $G$ (one-sided) such that $S \cap V_1 = C_1$.
* else, if $d^-(\sigma \cdot v) > d^-(\sigma)$, we know, since $d^-(\tau) < d^-(\sigma)$ and the $d^-$-curve only decreases by steps of $-1$, that there must exist $\rho$ such that $d^-(\rho) = d^-(\sigma)$, $\sigma \sqsubseteq \rho \sqsubseteq \tau$, and $d^-(\rho') > d^-(\sigma)$ for any $\rho'$ such that $\sigma \sqsubseteq \rho' \sqsubseteq \rho$ ($\rho$ is the shortest prefix of $\tau$ which contains $\sigma$ and has the same $d^-$ value). $\rho$ is then a type-(iii) SNEKFE of $\sigma$ by Lemma 4, and we may apply the induction hypothesis to $\tau \setminus \sigma$ □

**Lemma 7 - Signature size.** $\forall \sigma \in S_i$ for some $i$ partial layout of vertices, $|sgn(\sigma)| \le d^-(\sigma)$

*Proof* The proof is by induction on $|\sigma|$. Suppose $|sgn(\sigma)| \le d^-(\sigma)$, and consider the extension $\sigma \cdot u$, where $u$ is a vertex.

* If $\sigma \cdot u$ is not a SNEKFE of $\sigma$, then $|sgn(\sigma \cdot u)| = |sgn(\sigma) \cup \{u\}| = \mathbf{sgn}(u) + 1 \le d^-(\sigma) + 1 \le d^-(\sigma \cdot u)$

* If $\sigma$ is a type-(ii) SNEKFE of $\sigma$, then $sgn(\sigma) = sgn(\sigma \cdot u)$ and $d^-(\sigma \cdot u) = d^-(\sigma)$.

* If $\sigma \cdot u$ is a type-(i) SNEKFE of $\sigma$, then consider $\eta$, the closest node (up the tree) such that $d^-(\eta) < d^-(\sigma \cdot u)$, and $\eta \cdot v$ its successor on the path to $\sigma \cdot u$. We have $d^-(\eta) < d^-(\sigma \cdot u) \le d^-(\eta \cdot v)$, by definition of $\eta$. The path from $\eta \cdot v$ to $u$ is either a type-(iii) SNEKFE or overall-decreasing. Therefore $sgn(\sigma \cdot u) = sgn(\eta \cdot v)$. and $|sgn(\sigma \cdot u)| = |sgn(\eta)| + 1 \le d^-(\eta) + 1$ by induction hypothesis, and $|sgn(\sigma \cdot u)| \le d^-(\sigma \cdot u)$. □

In particular, $\forall \sigma$ partial layout, $d^-(\sigma) \le k$. Since two different elements of $S_i$ need different signatures, we get the following corollary:

**Corollary.** $\forall i$, at any point in the algorithm, $|S_i| = O(n^k)$

The overall complexity of the algorithm is therefore $O(n^{k+O(1)})$. More precisely, it is $O(n^{k+2})$. (there are $n$ levels of the tree to fill, $\le n^k$ nodes per level and $O(n)$ work per node to generate the next level).

# Appendix D Detailed RNA reconfiguration example

We provide in Figure D1 the intermediate sets of base pairs, and associated RNA secondary structures, for our running example, described in Figures 1 and ??.

## References

[1] Tamaki, H.: A polynomial time algorithm for bounded directed path-width. In: Kolman, P., Kratochvíl, J. (eds.) Graph-Theoretic Concepts in Computer Science, pp. 331–342. Springer, Berlin, Heidelberg (2011)
Proof Let $T$ be any simple canonical one-sided schedule of $G$ (one exists by Lemma 11), and let $T_i = T \cap V_i$.

Let $S$ be the sequence obtained by replacing each $T_1^{\diamond p}$ by $C_1^{\diamond p}$ in $T$ for each $p \in [1: k_1] \cup \{\infty\}$ and $T_2^{\diamond p}$ by $C_2^{\diamond p}$ in $T$ for each $p \in [1: k_2] \cup \{\infty\}$ (note that $C_i^{\diamond \infty}$ is empty otherwise $C_1^{\diamond k_L(G_1)} \neq C_1$, in contradiction with the hypothesis). thus $T^{\diamond \infty}$ is replaced by an empty sequence).

We show that $bg(S^{\diamond p}) \le bg(T^{\diamond p})$ for each $q \in [1: k] \cup \{\infty\}$ which is enough to say that $S$ is canonical with $T$ canonical.

By Corollary 3, it suffices to show that $bg(S^{\diamond p}) - (p-1) \le bg(T^{\diamond p})$ for each $p \in [1: k] \cup \infty$. With $0 = bg(S^{\diamond \infty}) \le bg(T^{\diamond \infty})$ with $S^{\diamond \infty}$, we just have to show the property for $p \in [1: k]$.

Assume now that $p \in [1: k]$ and w.l.o.g. $V(S^{\diamond p}) \subseteq V_1$, with Lemma 9, there exists a strictly increasing integer sequence $\Theta_1 = [p_1, \dots, p_{k_1}]$ such that $\forall q' \in [1, k_1], T_i^{\diamond q'} = T^{\diamond p_{q'}}$. (1) Additionaly, there exists $q \in [1, k_1]$ such as $p = p_q$. (2) We can then rewrite:

$$ 
\begin{aligned}
bg(S^{\diamond p}) - (p-1) &= bg(S^{\diamond p_q}) - (p_q - 1) \text{ with (2)} \\
&\le bg(C^{\diamond q}) + (q-1) - (p_q - 1) \text{ by Corollary 3} \\
&\le bg(T_1^{\diamond q}) + (q-1) - (p_q - 1) \text{ since } C \text{ is canonical and } T_1^{\diamond q} \text{ is a } q\text{-sequence} \\
&= bg(T_1^{\diamond r}) - (r-1) + (q-1) - (p_q - 1) \text{ for some } r \in [1:q] \text{ by Corollary 3} \\
&= bg(T^{\diamond p_r}) - (p_r - 1) + (p_r - r) - (p_q - q) \text{ with (1)} \\
&\le bg(T^{\diamond p_r}) - (p_r - 1) \text{ since } p_r - r \le p_q - q \text{ (r \le q, } \Theta_1 \text{ strictly increasing)} \\
&\le bg(T^{\diamond p_q}) \text{ by Corollary 3, since } p_r \le p_q
\end{aligned}
$$

which concludes the proof. $\square$

**Lemma 13** For any canonical schedule $C_1$ of $G_1$ and $C_2$ of $G_2$ there exists a simple canonical schedule $S$ of $G$ (one-sided) such that $S \cap V_1 = C_1$ and $S \cap V_2 = C_2$.

Proof Let $k_i = k_L(G_i)$. Let $C_i' = C_i^{\diamond k_i}$, $Z = V(C_1') \cup V(C_2')$ and $G' = G[Z]$. Note that $\delta(Z) = -k_1 - k_2 = -k_L(G)$ so $Z$ is a divider. By Lemma 12, there exists a simple canonical solution $T$ of $G[Z]$. Let $Q$ be any optimal schedule of $Z$. Clearly $S = T \cdot Q$ is a simple schedule of $G$, we show that it is canonical. Indeed, let $p \in [1: k_L(G)]$ and $U$ be any $p$-sequence of $G$. Then by Lemma 3, $\delta(U \cap Z) \le \delta(U) \le -p$ and $bg(U \cap Z) \le bg(U)$, thus $U' = (U \cap Z)^{\diamond p}$ is a $p$-sequence of $G[Z]$ with $bg(U') \le bg(U)$. Overall,

$$ 
\begin{aligned}
bg(S^{\diamond p}) &= bg(T^{\diamond p}) \text{ since } \delta(T) = -k_L(G) \le -p \\
&\le bg(U') \text{ since } T \text{ canonical in } G[Z] \\
&\le bg(U)
\end{aligned}
$$

$\square$

**Lemma 14** For $C_1$ and $C_2$ canonical and $S$ be a minimal shuffle of $C_1, C_2$, for any $p \in [1: k_L(G)]$ there exists a canonical shuffle $T$ such that $S^{\diamond p} = T^{\diamond p}$.
<figure><img src="image_15.png" /><figcaption>**Fig. D1** Optimal (min barrier) refolding scenario between two RNA secondary structures. In each intermediate state, the conflict graph is given, featuring the selected independent set of base pairs (filled nodes), and the corresponding secondary structure.</figcaption></figure>

[2] van den Heuvel, J.: The complexity of change. Surveys in combinatorics 409 (2013), 127–160 (2013)

[3] Lokshtanov, D., Mouawad, A.E.: The complexity of independent set reconfiguration on bipartite graphs. ACM Transactions on Algorithms (TALG) 15(1), 1–19 (2018)

[4] Ito, T., Kamiński, M., Ono, H., Suzuki, A., Uehara, R., Yamanaka, K.: Parameterized complexity of independent set reconfiguration problems. Discrete Applied Mathematics 283, 336–345 (2020)

[5] Mouawad, A.E., Nishimura, N., Raman, V., Simjour, N., Suzuki, A.: On the parameterized complexity of reconfiguration problems. Algorithmica 78(1), 274–297 (2017)
44 Bipartite IS Reconfiguration: General and RNA-inspired Algorithms

*Proof* By recurrence on *p*. For *p* = 1 the property is exactly Lemma 13. Consider any other *p* > 1, and assume the property is true for *p* − 1, i.e. there exists *T* such that *T*<sup>*qp*−1</sup> = *S*<sup>*qp*−1</sup>. Write *P* = *S*<sup>*qp*−1</sup> (*P* is possibly empty), and let *S'* = *S* \ *P*, *T'* = *T* \ *P*, *C*'<sub>1</sub> = *C*<sub>1</sub> \ *P*, *C*'<sub>2</sub> = *C*<sub>2</sub> \ *P*<sup>1</sup>. Note that *S'*<sup>*q*1</sup> = *S*<sup>*q*P</sup> and *T'*<sup>*q*1</sup> = *T*<sup>*q*P</sup>. By definition, *S'* and *T'* are both shuffles of *C*'<sub>1</sub> and *C*'<sub>2</sub> (with *S'* minimal), so bg(*S'*<sup>*q*1</sup>) ≤ bg(*T'*<sup>*q*1</sup>) and {*S'*<sup>*q*1</sup>, *T'*<sup>*q*1</sup>} = {*C*'<sub>1</sub><sup>*q*1</sup>, *C*'<sub>2</sub><sup>*q*1</sup>} (since these are the only two possible values for shuffles and both prefixes are distinct). Without loss of generality, assume that *S'*<sup>*q*1</sup> = *C*'<sub>1</sub><sup>*q*1</sup> and *T'*<sup>*q*1</sup> = *C*'<sub>2</sub><sup>*q*1</sup>.

Since *T* is a shuffle of *C*₁, *C*₂, there exists *q* (necessarily *q* > *p*) such that *T*<sup>*q*</sup> = *C*'<sub>1</sub><sup>*q*1</sup>. We build *U* as:

$$
U = T^{<p-1} \cdot C'_1^{<1} \cdot T^{<q-1} \cdot (T \setminus T^<q).
$$

Note that *U* is a shuffle of *C*₁, *C*₂ as we only swapped slices of *C*₁ with slices of *C*₂,
keeping each as a subsequence. We show that *U* is canonical using Proposition 13.

For $r < p$ or $r > q$, we have $U^{\diamond r} = T^{\diamond r}$, therefore

$$
\text{so } \operatorname{bg}(U^{\diamond r}) = \operatorname{bg}(T^{\diamond r}).
$$

For $r = p$, we have $U^{\diamond p} = C_1^{\diamond 1}$, so

$$
\begin{align*}
\operatorname{bg}(U^{\diamond r}) &= \operatorname{bg}(S'^{\diamond 1}) \\
&\le \operatorname{bg}(T'^{\diamond 1}) \\
&= \operatorname{bg}(T^{\diamond p}).
\end{align*}
$$

Finally for $p < r \le q$, we have $U^{\diamond r} = T^{\diamond r-1}$, thus

$$
\text{so } \operatorname{bg}(U^{\diamond r}) = \operatorname{bg}(T^{\diamond r-1}).
$$

We conclude that *U* is a canonical shuffle of *C*₁, *C*₂ with *U*<sup>*qp*</sup> = *S*<sup>*qp*</sup>. □

**Lemma 15** For $C_1$ and $C_2$ canonical, all minimal shuffles $S$ of $C_1$ and $C_2$ are canonical. (G one-sided)

*Proof* By Lemma 14, there exists *T* a canonical shuffle of *C*₁ and *C*₂. Since *S* is a minimal shuffle, *S* \ *S*<sup>*dkL*</sup> is optimal, so canonical for *G* \ *S*<sup>*dkL*</sup> with Prop. 12. Thus *S* is the concatenation of a canonical prefix and of a canonical solution, it is canonical by Lemma 5. □

5.5.2 Shuffle in two-sided graphs

**Lemma 16** Let $S$ be a canonical solution of $G$, then $\overleftarrow{S}$ is a canonical solution of $\overleftarrow{G}$.

*Proof* W.l.o.g. we consider *G* with associated schedule *S* and we write *S* = *P*<sub>*G*</sub>*Q* with *P* and *Q* canonical and *Q* possibly empty. Thus, <sub>*S*</sub> = <sub>*Q*</sub><sub><u>*G*</u></sub><sub><u>*P*</u></sub> = *Q*<sub><u>*P*</u></sub> and with *P* and *Q* canonical, <sub>*S*</sub> is also canonical. □

<footnote n="1">¹Here, we slightly abuse notations in the latter two cases, since *P* is not necessarily a prefix of *C*₁ and/or *C*₂, but *P* ∩ *V*₁ is a prefix *C*₁ since *S* and *T* are shuffles of *C*₁, *C*₂, so more formally *C*ᵢ' = *C*ᵢ \ (*P* ∩ *V*ᵢ)</footnote>
[6] Lokshtanov, D., Mouawad, A.E., Panolan, F., Ramanujan, M., Saurabh, S.: Reconfiguration on sparse graphs. Journal of Computer and System Sciences 95, 122–131 (2018)

[7] Lokshtanov, D., Mouawad, A.E., Panolan, F., Siebertz, S.: On the param- eterized complexity of reconfiguration of connected dominating sets. arXiv preprint arXiv:1910.00581 (2019)

[8] Barát, J.: Directed path-width and monotonicity in digraph searching. Graphs and Combinatorics 22(2), 161–172 (2006)

[9] Yang, B., Cao, Y.: Digraph searching, directed vertex separation and directed pathwidth. Discrete Applied Mathematics 156(10), 1822–1837 (2008)

[10] Coudert, D., Mazauric, D., Nisse, N.: Experimental evaluation of a branch-and-bound algorithm for computing pathwidth and directed path- width. Journal of Experimental Algorithmics (JEA) 21, 1–23 (2016)

[11] Erde, J.: Directed path-decompositions. SIAM Journal on Discrete Math- ematics 34(1), 415–430 (2020)

[12] Kitsunai, K., Kobayashi, Y., Komuro, K., Tamaki, H., Tano, T.: Com- puting directed pathwidth in $o(1.89^n)$ time. Algorithmica 75(1), 138–157 (2016)

[13] Bodlaender, H.L.: Fixed-parameter tractability of treewidth and path- width. In: The Multivariate Algorithmic Revolution and Beyond, pp. 196–227. Springer, ??? (2012)

[14] Tamaki, H.: A directed path-decomposition approach to exactly identi- fying attractors of boolean networks. In: 2010 10th International Sym- posium on Communications and Information Technologies, pp. 844–849 (2010). IEEE

[15] Kobayashi, Y., Komuro, K., Tamaki, H.: Search space reduction through commitments in pathwidth computation: An experimental study. In: International Symposium on Experimental Algorithms, pp. 388–399 (2014). Springer

[16] Tinoco Jr, I., Bustamante, C.: How rna folds. Journal of molecular biology 293(2), 271–281 (1999)

[17] Mañuch, J., Thachuk, C., Stacho, L., Condon, A.: Np-completeness of the energy barrier problem without pseudoknots and temporary arcs. Natural Computing 10(1), 391–405 (2011)
**Lemma 17** For any $G = (L \cup R, E)$ with $L \neq \emptyset$, there exist $\ell \in L$ such that for any canonical sequence $S'$ of $G \setminus (\{\ell\} \cup N(l))$ such as $S = S'.l.N(l)$ is a canonical schedule of $G$.

*Proof* We write the canonical schedule $T = H\overleftarrow{D}$ of $G$ (that always exists with Lemma 8) with $D$ possibly empty. If $D = \emptyset$, we consider the smallest suffix of $T = H$ that contains an element in $L$ that always exists with $L \neq \emptyset$ and that we can write $l.N(l)$ and we write $T = T'.l.N(l)$. Given $S'$ of $G \setminus (\{\ell\} \cup N(l))$ canonical, we now show that $S = S'.l.N(l)$ is canonical. We note $S' = H'\overleftarrow{D}$. We denote $p_{lim} \in [1, k_L(G)] \cup \infty$ the first value such as $T'_{lim} \neq T^{\leftarrow}_{lim}$. $\forall p < p_{lim}$, given a p- sequence $F$, $\text{bg}(S^{\leftarrow}_{\leftarrow p}) = \text{bg}(S'^{\leftarrow}_{\leftarrow p}) = \text{bg}(S''^{\leftarrow}_{\leftarrow p}) \leq \text{bg}(F)$ with $S''$ canonical one-sided. $\forall p \geq p_{lim}$, given a p- sequence $F$, we use Proposition 10, $\text{bg}(S^{\leftarrow}_{\leftarrow p}) = \max(\text{bg}(S'^{\leftarrow}_{\leftarrow p}), \delta(S') + \text{bg}(l.N(l)))$. With $\text{bg}(S'^{\leftarrow}_{\leftarrow p}) = \text{bg}(S''^{\leftarrow}_{\leftarrow p}) \leq \text{bg}(F)$ and $\delta(S') = \delta(T')$ as they contain same elements. We have $\text{bg}(S'^{\leftarrow}_{\leftarrow p}) \leq$ Thus $\text{bg}(S^{\leftarrow}_{\leftarrow p}) \leq \max(\text{bg}(F), \text{bg}(T^{\leftarrow}_{\leftarrow p})) \leq \text{bg}(F)$ with $T$ canonical one-sided and we have shown that when $D = \emptyset$, we have $S$ canonical.

If $D \neq \emptyset$, we consider the smallest suffix of $T$ that contain an element in $L$ that always exists with $L \neq \emptyset$ and that we can write $N(l).l$ with $N(l) \subset R$ possibly empty and $l \in L$. Given $S'$ of $G \setminus (\{\ell\} \cup N(l))$ canonical, we can now apply Lemma 5 with prefix $N(l).l$ of $D \subseteq \overleftarrow{T}$ and $\overleftarrow{T}$ canonical thanks to lemma 16) It yields that $N(l).lS'$ is a canonical schedule for $\overleftarrow{G}$. Using lemma 16 again, we have $S = S'.l.N(l)$ is a canonical schedule of $G$. $\square$

**Lemma 18** For $C_1$ and $C_2$ canonical two- or one-sided, all minimal shuffles $S$ of $C_1$ and $C_2$ are canonical.

*Proof* We write $C_1 = P_1\overleftarrow{T_1}$ and $C_2 = P_2\overleftarrow{T_2}$. We denote $P$ and $T$ respectively minimal shuffles of $P_1$ and $P_2$ and of $T_1$ and $T_2$. Thanks to Lemma 15 applied two times, $P$ and $T$ are canonical.

Note that the union of two dividers $P_1$ and $P_2$ on distinct graphs $G_1$ and $G_2$ is a divider on the union graph. Indeed, suppose it is not the case, it means that there exists $P'$ divider on $G$ such that $I(P')$ is an independent set with $|I(P')| > |I(P_1 \cup P_2)|$. Set $I(P')$ necessarily intersects $G_1$ or $G_2$ and at least in one of them contains more element than $P'$ thus w.l.o.g we have $|I(P') \cap V(G_1)| > |I(P) \cap V(G_1)| = |I(P_1)|$ thus $P_1$ is not a divider of $G_1$ which is a contradiction.

Using that, we have $P$ divider of $G = G_1 + G_2$. We have shown that $S = P\overleftarrow{Q}$ is a canonical two-sided schedule which concludes the proof. $\square$

## 5.6 Correctness of Canonical Merge and Subtree-Schedule

**Theorem 7** (Canonical Merge Correctness) If $G_1$ and $G_2$ are two disjoint bipartite graphs and $C_1$ and $C_2$ two canonical solutions for $G_1$ and $G_2$ respectively, then Canonical Merge (Algorithm 3) yields a canonical solution for $G$.
46

[18] Thachuk, C., Manuch, J., Rafiey, A., Mathieson, L.-A., Stacho, L., Condon, A.: An Algorithm for the Energy Barrier Problem Without Pseudoknots and Temporary Arcs. In: Biocomputing 2010, pp. 108–119. World Scientific, ??? (2009). https://doi.org/10.1142/9789814295291_0013

[19] Gottschau, M., Happach, F., Kaiser, M., Waldmann, C.: Budget minimization with precedence constraints. CoRR abs/1905.13740 (2019) arXiv:1905.13740

[20] Kinne, J., Manuch, J., Rafiey, A., Rafiey, A.: Ordering with precedence constraints and budget minimization. CoRR abs/1507.04885 (2015) arXiv:1507.04885

[21] Cygan, M., Fomin, F.V., Kowalik, Ł., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms vol. 5. Springer, ??? (2015)

[22] Abdel-Wahab, H.: On strictly optimal schedules for the cumulative cost-optimal scheduling problem. Computing **24**, 61–86 (1980)

[23] Wolfinger, M.T., Svrcek-Seiler, W.A., Flamm, C., Hofacker, I.L., Stadler, P.F.: Efficient computation of rna folding dynamics. Journal of Physics A: Mathematical and General **37**(17), 4731–4731 (2004)

[24] Senter, E., Clote, P.: Fast, approximate kinetics of rna folding. Journal of Computational Biology **22**(2), 124–144 (2015)

[25] Fukuda, K., Matsui, T.: Finding all the perfect matchings in bipartite graphs. Applied Mathematics Letters **7**(1), 15–18 (1994)

[26] Zhang, Z., Zhang, X., Wen, X.: Directed hamilton cycles in digraphs and matching alternating hamilton cycles in bipartite graphs. SIAM J. Discret. Math. **27**(1), 274–289 (2013). https://doi.org/10.1137/110837188

[27] Tamaki, H.: A polynomial time algorithm for bounded directed path-width. In: International Workshop on Graph-Theoretic Concepts in Computer Science, pp. 331–342 (2011). Springer

[28] Rafiey, A., Kinne, J., Manuch, J., Rafiey, A.: Ordering with precedence constraints and budget minimization. arXiv preprint arXiv:1507.04885 (2015)

[29] Lovász, L., Plummer, M.D.: Matching Theory vol. 367. American Mathematical Soc., ??? (2009)

[30] Chen, J., Kanj, I.A.: Constrained minimum vertex cover in bipartite graphs: complexity and parameterized algorithms. Journal of Computer
*Proof* We prove by induction that Canonical Merge (Algorithm 3) yields a minimal shuffle, as with Lemma 18, it would show that S, the resulting schedule is canonical.

Our base case of induction is when $C_1 = \emptyset$ or $C_2 = \emptyset$. Note that the other schedule is canonical by hypothesis and that a canonical schedule is indeed a minimal shuffle by definition.

In the general case, we suppose first that $C_1^{<1} = \emptyset$ or $C_2^{<1} = \emptyset$. W.l.o.g we suppose (*): $C_2^{<1} = \bot$ or $\text{bg}(C_1^{<1}) \le \text{bg}(C_2^{<1})$

By induction, CMERGE($C_1 \setminus C_1^{<1}$, $C_2$) is a minimal shuffle. We suppose it of the form $P \leftarrow Q$ with $Q$ possibly empty. We have to show that $C_1^{<1} \cdot P$ is a minimal shuffle. It is a shuffle through case 2 of the one-sided case definition 7 and it is minimal by definition 7 in the two-sided case thanks to (*). $\square$

**Theorem 8** *Subtree-Schedule (Algorithm 4) outputs a canonical (and therefore optimal) schedule.*

*Proof* By Lemma 8, a canonical schedule S for G exists.

We now show by induction that the output of the Subtree-Schedule (Algorithm 4) is a canonical schedule. If L is empty, the elements of R can be proceeded in any order as it is done in line 5-6 and any schedule is canonical one-sided by definition.

We can now suppose $L \ne \emptyset$. We want to show that after loop of line 8, $M[(L, R)]$ contains a canonical schedule. First, by induction $S_{IN}$ and $S_{OUT}$ are canonical. Thus with the correctness of CMERGE (Theorem 7), we have $S'' = CMERGE(S_{IN}, S_{OUT})$ canonical. Thanks to Lemma 17 with $S''$ canonical, there exist $l_{canon} \in L$ such that $S'_{canon} = S''_{canon} \cdot l_{canon} \cdot N(l_{canon})$ is canonical. The correct choice of $l$ is done at some point as we exhaustively enumerate all possible $l$. (line 8) We now show that $M[(L, R)] = S'_{canon}$ at the end of the loop. We also denote $S_{base} = L \cdot R$. First, thanks to the definition of canonical applied multiple time, we have $\forall S', \forall p$ in $[1, \delta_{min}(S_{canon})]$, $\text{bg}(S_{canon}^{<p}) \le \text{bg}(S'^{<p})$ and $\text{bg}(\overleftarrow{S}_{canon}^{<p}) \le \text{bg}(\overleftarrow{S}_{base}^{<p})$. It means that when $S_{canon}$ is put in $M[(L, R)]$ it has no way to be removed by condition of line 12-13. It concludes the induction and we have shown that the algorithm returns a canonical, thus optimal, schedule (with Property 11). $\square$

# 6 Implementation and empirical evaluation

In this section, we study and report the empirical behavior of our algorithms using random instances. Specifically, we first present a general benchmark of Divider-Schedule (Algorithm 2) on random Erdös-Rényi bipartite graphs, focusing on the runtime, distribution of $\rho$ for increasing values of $n$, and the impact of $\rho$ on the runtime. Then, we compare our implementations of Divider-Schedule (Algorithm 2) and Subtree-Schedule (Algorithm 4) on the conflict graphs of randomly-generated pairs of RNA structures (i.e. random bipartite circle graphs), as such instances enable us to use an optimized routine for finding Strict Dividers in bipartite circle graphs (cf Lemma 1), leading to a sizeable speedup.
[31] de Berg, M., Jansen, B.M., Mukherjee, D.: Independent-set reconfiguration thresholds of hereditary graph classes. Discrete Applied Mathematics **250**, 165–182 (2018)

[32] Zhang, Z.-B., Lou, D.: Bipartite graphs with a perfect matching and digraphs. arXiv preprint arXiv:1011.4359 (2010)
## Divider-Schedule implementation

Compared to the description of the Divider-Schedule algorithm (Algorithm 2), our implementation uses a slightly more efficient rule in the absence of a Strict Divider: it loops over all possible $r \in R$, and adds $N(r) \cdot r$ to the schedule. It also only explicitly handles cases such that $|L| \ge |R|$. For cases such that $|L| < |R|$, $L$ and $R$ are swapped prior to the recursive call(s), and the resulting schedule is reversed, so that the assumption does not break the generality of our implementation.

## Code availability

The implementation used for our benchmarks uses a combination of Python and C++, and is available at https://github.com/bmarchand/rnabarrier_bisr.

# 6.1 Random Erdös-Rényi bipartite graphs

Our first benchmark considers the value of $\rho$ and empirical complexity induced by random Erdös-Rényi bipartite graphs.

## Methodology

We generate bipartite graphs of size $n$ (# nodes) ranging from 10 to 40 nodes, with probability of connecting any two nodes of $p = 2 \cdot 5/n$. More precisely, given an (even) integer $n$, two sets of nodes $A$ and $B$ are created, each of size $n/2$. Any two vertices $u \in A$ and $v \in B$ are then connected with probability $p$, resulting in an average degree of 5.

## Results and interpretation

The results and runtime of the Divider-Schedule algorithm (Algorithm 2) on such instances are summarized in Figure 12.

All instances could be solved in time ranging from 10 milliseconds to 10 seconds, an altogether modest computational requirement. However, the execution time seems to grow exponentially with the number $n$ of vertices, as suggested the linear growth of the runtime for increasing instance size (top left panel; logarithmic scale for y-axis). This behavior is probably explained by the linear growth of the average value of $\rho$ as a function of $n$ (lower left panel).

Finally, we reason that the worst-case complexity in $O(n^{2\rho+2.5})$ may only be witnessed in very specific circumstances. In particular, the $2\rho+2.5$ growth of the degree may only hold in highly constrained families of instances. To obtain a loose estimate for the practical degree of the polynomial complexity, we report the value $\log_n(T)$, for each instance of length $n = 40$ with range $\rho$, computed in time $T$ on a reference architecture. As can be seen in the right panel of Figure 12, the $\log_n(T)$ values observed in our experiments fall in the $[-1, 0.8]$ range, far from the $[2.5, 18.5]$ range expected from our worst-case analysis for values of $\rho$ in $[2, 8]$. This observation suggests that the slope (i.e. coefficient of $\rho$ in the degree of the complexity) may typically be substantially smaller than 2.
<figure><img src="image_16.png" /><figcaption>**Fig. 12** (Top left) Average run-time (seconds, log-scale) of Algorithm 2 (Divider-Schedule) on random Erdös-Rényi bipartite graphs with average degree 5 (i.e. probability of connection $p = 2 \cdot (5/n)$). (Bottom left) Distribution of parameter $\rho$ for generated instances, as a function of input size. (Right) Evolution of $\log_n$ (Runtime) with increasing values of $\rho$ within instances of size $n = 40$.</figcaption></figure>

However, such an interpretation needs to be moderated as: i) the hypothesized behavior may only hold for specific families of instances; and ii) our instances are relatively small, and may be poorly representative of the true asymptotic behavior. This is seemingly supported by the apparent sublinear growth of the degree as a function of $\rho$.

## 6.2 Random RNA barrier instances (bipartite circle graphs)

Next, we investigate the practical speedup induced by Subtree-Schedule (Algorithm 4) in the context of a special class of bipartite circle graphs, designed to reflect natural constraints arising in the study of RNA kinetics.

### Methodology

Overall, we generate a pair of random realistic RNA structures using statistical sampling in the Boltzmann ensemble, then merge their base pairs as within a (bipartite) graph, two base pairs being connected if their coexistence violates the definition of a secondary structure.

Let us recall that, as introduced above, a secondary structure over an RNA of length $n$ is a set $S$ of base pairs $(i, j) \in [1, n]^2, i < j$, such that:

C1 a position may be involved in at most a single base pair: $\forall (i, j), (k, l) \in S$ such that $i \notin \{k, l\}$ and $j \notin \{k, l\}$;

C2 base pairs do not cross: $\nabla^+(i, j), (k, l) \in S$ such that $i < k < j < l$;

C3 base pairs should span at least $\theta$ positions: $\forall (i, j), j - i - 1 \ge \theta$. We use a default value of $\theta = 1$ in the following.

The Boltzmann probability of any structure $S$ is proportional to $\exp(-\beta E(S))$, where $\beta$ is a parameter akin to a temperature and $E(S) = -|S|$. Note that we can equivalently write $E(S) = \frac{1}{2}(n - |U(S)|)$, with $|U(S)|$ the number of unpaired positions in $S$. The probability of a structure (for a fixed length $n$) is then proportional to $\exp(\beta|U|/2)$. We then use standard techniques [41, 42]
<figure><img src="image_17.png" /><figcaption>**Fig. 13** (Top left) Execution times of Divider-Schedule (Algorithm 2) and Subtree-Schedule (Algorithm 4) on pairs of random RNA secondary structures, and distributions of arboricity values (bottom left). In agreement with their asymptotic complexities ($O(n^{2\rho+2.5})$ and $O(n^{\Phi+3})$ respectively), Subtree-Schedule scales better than Divider-Schedule. (Right) The evolution of the runtime with $\Phi$ suggests a polynomial degree much smaller than the $\phi+3$ degree occurring in our worst-case complexity analysis.</figcaption></figure>

for sampling RNA structures in the Boltzmann ensemble according to this energy function. We set $\beta$ such that $\exp(\beta/2) = 10^{-1}$, i.e. the probability of a structure with $x$ unpaired position is proportional to $10^{-x}$, to reflect a realistic numbers of unpaired positions.

Finally, we create BISR instances by first generating a pair $(S_L, S_R)$ of random RNA secondary structures of a given length $n$. We then create a graph $G$ whose vertices are $S_L \cup S_R$, having edges $((i, j), (k, l)) \in S_L \times S_R$ whenever the two base pairs cannot coexist in a valid secondary structures (i.e. a structure $\{(i, j), (k, l)\}$ would violate at least one of the C1 or C2 Conditions above).

## Results and interpretation

Figure 13 reports (upper left panel) the average execution times of running Divider-Schedule (Algorithm 2) and Subtree-Schedule (Algorithm 4) on bipartite circle graphs generated as described above. We also report the distribution of the arboricity parameter $\Phi$ (lower left) as a function of the total number $n$ of vertices. Finally, following a similar rationale as for Erdös-Rényi graphs, we report the base-$n$ logarithm of the runtime (right), whose value is asymptotically expected to converge to $\phi + 3$.

We remark that, consistent with their respective worst-case complexities, Subtree-Schedule (Algorithm 4) is more efficient than Divider-Schedule (Algorithm 2) by at least an order of magnitude. Under a time cutoff of 1 second per run, Subtree-Schedule enables solving instances consisting of 55 nodes while Divider-Schedule exceeds the 1 sec cutoff around 40 nodes. The evolution of the runtime as a function of $n$ also appears sublinear in logarithmic scale, despite $\Phi$ seemingly being a linearly increasing function of $n$.

Finally, the evolution of $\log_n(T)$, for $T$ the runtime in sec., seemingly confirms a complexity in $n^{O(\phi)}$, but also suggests an average case behavior in
$o(n^{2+\phi})$ for these instances. Again, this interpretation is only tentative, and possibly induced by the limited value of $n$, motivating further formal studies.

# 7 Conclusion

Motivated by the development of exact parameterized algorithms for the RNA ENERGY BARRIER problem, we studied several parameterizations for BIPARTITE INDEPENDENT SET RECONFIGURATION. For the range $\rho$ of possible cardinalities for the independent sets along the reconfiguration as a parameter, we give a direct $O(n^2)$-space, $O(n^{2\rho+2.5})$-time algorithm (Algorithm 2), and an indirect $O(n^2)$-space, $O(\rho n^{2\rho})$-time algorithm [37] through an equivalence with directed pathwidth.

In the case of RNA instances, i.e. BISR on bipartite circle graphs, we additionally study an *arboricity* parameter denoted $\Phi$, that should intuitively be much smaller than the size of instances on natural RNA structures. For this parameter, we also provide an XP algorithm, with complexity $O(n^{\Phi+2})$ in space and $O(n^{\Phi+3})$ in time. This algorithm involves a novel *merge* procedure for optimal solutions of disjoint instances of *mimimum cumulative-cost* scheduling, which may be of independent interest.

The fixed-parameter tractability of BIPARTITE INDEPENDENT SET RECONFIGURATION restricted to bipartite circle graphs, with respect to $\rho$, $\Phi$ and $\rho + \Phi$ remains open. It implies that the fixed-parameter tractability of directed pathwidth (i.e. $\rho$ for BISR on general instances) also remains open. We nevertheless hope that this newly-drawn connection between a width parameter (directed pathwidth) and a reconfiguration problem (BISR), may help shed new light onto this problem. In that respect, combining [43] and [29] to try to formulate an “obstacle theory” for directed pathwidth might be an interesting avenue for future research.

# References

[1] van den Heuvel, J.: The complexity of change. Surveys in combinatorics 409 (2013), 127–160 (2013)

[2] Lokshtanov, D., Mouawad, A.E.: The complexity of independent set reconfiguration on bipartite graphs. ACM Transactions on Algorithms (TALG) 15(1), 1–19 (2018)

[3] Ito, T., Kamiński, M., Ono, H., Suzuki, A., Uehara, R., Yamanaka, K.: Parameterized complexity of independent set reconfiguration problems. Discrete Applied Mathematics 283, 336–345 (2020)

[4] Mouawad, A.E., Nishimura, N., Raman, V., Simjour, N., Suzuki, A.: On the parameterized complexity of reconfiguration problems. Algorithmica 78(1), 274–297 (2017)
[5] Lokshtanov, D., Mouawad, A.E., Panolan, F., Ramanujan, M., Saurabh, S.: Reconfiguration on sparse graphs. Journal of Computer and System Sciences 95, 122–131 (2018)

[6] Lokshtanov, D., Mouawad, A.E., Panolan, F., Siebertz, S.: On the param- eterized complexity of reconfiguration of connected dominating sets. arXiv preprint arXiv:1910.00581 (2019)

[7] Bousquet, N., Mouawad, A.E., Nishimura, N., Siebertz, S.: A survey on the parameterized complexity of reconfiguration problems. Computer Science Review 53, 100663 (2024)

[8] Maňuch, J., Thachuk, C., Stacho, L., Condon, A.: Np-completeness of the energy barrier problem without pseudoknots and temporary arcs. Natural Computing 10(1), 391–405 (2011)

[9] Tinoco Jr, I., Bustamante, C.: How rna folds. Journal of molecular biology 293(2), 271–281 (1999)

[10] Thachuk, C., Manuch, J., Rafiey, A., Mathieson, L.-A., Stacho, L., Condon, A.: An Algorithm for the Energy Barrier Problem Without Pseu-doknots and Temporary Arcs. In: Biocomputing 2010, pp. 108–119. World Scientific, ??? (2009). https://doi.org/10.1142/9789814295291.0013

[11] Gottschau, M., Happach, F., Kaiser, M., Waldmann, C.: Budget min- imization with precedence constraints. CoRR abs/1905.13740 (2019) arXiv:1905.13740

[12] Kinne, J., Manuch, J., Rafiey, A., Rafiey, A.: Ordering with precedence constraints and budget minimization. CoRR abs/1507.04885 (2015) arXiv:1507.04885

[13] Danaee, P., Rouches, M., Wiley, M., Deng, D., Huang, L., Hendrix, D.: bpRNA: large-scale automated annotation and analysis of RNA secondary structure. Nucleic Acids Research 46(11), 5381–5394 (2018)

[14] Belmonte, R., Hanaka, T., Lampis, M., Ono, H., Otachi, Y.: Independent set reconfiguration parameterized by modular-width. Algorithmica 82(9), 2586–2605 (2020)

[15] Mouawad, A.E., Nishimura, N., Raman, V., Wrochna, M.: Recon- figuration over tree decompositions. In: International Symposium on Parameterized and Exact Computation, pp. 246–257 (2014). Springer

[16] Bodlaender, H.L., Groenland, C., Swennenhuis, C.M.: Parameterized complexities of dominating and independent set reconfiguration. arXiv preprint arXiv:2106.15907 (2021)
[17] Nagamochi, H.: Linear layouts in submodular systems. In: Algorithms and Computation: 23rd International Symposium, ISAAC 2012, Taipei, Taiwan, December 19-21, 2012. Proceedings 23, pp. 475-484 (2012). Springer

[18] Abdel-Wahab, H.: On strictly optimal schedules for the cumulative cost-optimal scheduling problem. Computing **24**, 61–86 (1980)

[19] Rafiey, A., Kinne, J., Manuch, J., Rafiey, A.: Ordering with precedence constraints and budget minimization. arXiv preprint arXiv:1507.04885 (2015)

[20] Cygan, M., Fomin, F.V., Kowalik, Ł., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms vol. 5. Springer, ??? (2015)

[21] Morgan, S.R., Higgs, P.G.: Barrier heights between ground states in a model of rna secondary structure. Journal of Physics A: Mathematical and General **31**(14), 3153 (1998). https://doi.org/10.1088/0305-4470/31/14/005

[22] Wolfinger, M.T., Svrcek-Seiler, W.A., Flamm, C., Hofacker, I.L., Stadler, P.F.: Efficient computation of rna folding dynamics. Journal of Physics A: Mathematical and General **37**(17), 4731 (2004)

[23] Senter, E., Clote, P.: Fast, approximate kinetics of rna folding. Journal of Computational Biology **22**(2), 124-144 (2015)

[24] Michálik, J., Touzet, H., Ponty, Y.: Efficient approximations of rna kinetics landscape using non-redundant sampling. Bioinformatics **33**(14), 283-292 (2017) https://academic.oup.com/bioinformatics/article-pdf/33/14/i283/50314613/bioinformatics-33-14-i283.pdf. https://doi.org/10.1093/bioinformatics/btx269

[25] Entzian, G., Hofacker, I.L., Ponty, Y., Lorenz, R., Tanzer, A.: Rmaxplorer: harnessing the power of guiding potentials to sample rna landscapes. Bioinformatics **37**(15), 2126-2133 (2021) https://academic.oup.com/bioinformatics/article-pdf/37/15/2126/50578834/btab066.pdf. https://doi.org/10.1093/bioinformatics/btab066

[26] Barát, J.: Directed path-width and monotonicity in digraph searching. Graphs and Combinatorics **22**(2), 161–172 (2006)

[27] Yang, B., Cao, Y.: Digraph searching, directed vertex separation and directed pathwidth. Discrete Applied Mathematics **156**(10), 1822–1837 (2008)
[28] Coudert, D., Mazauric, D., Nisse, N.: Experimental evaluation of a branch-and-bound algorithm for computing pathwidth and directed path-width. Journal of Experimental Algorithmics (JEA) **21**, 1–23 (2016)

[29] Erde, J.: Directed path-decompositions. SIAM Journal on Discrete Mathematics **34**(1), 415–430 (2020)

[30] Kitsunai, K., Kobayashi, Y., Komuro, K., Tamaki, H., Tano, T.: Computing directed pathwidth in $o(1.89^n)$ time. Algorithmica **75**(1), 138–157 (2016)

[31] Tamaki, H.: A polynomial time algorithm for bounded directed path-width. In: Kolman, P., Kratochvíl, J. (eds.) Graph-Theoretic Concepts in Computer Science, pp. 331–342. Springer, Berlin, Heidelberg (2011)

[32] Bodlaender, H.L.: Fixed-parameter tractability of treewidth and path-width. In: The Multivariate Algorithmic Revolution and Beyond, pp. 196–227. Springer, ??? (2012)

[33] Kobayashi, Y., Komuro, K., Tamaki, H.: Search space reduction through commitments in pathwidth computation: An experimental study. In: International Symposium on Experimental Algorithms, pp. 388–399 (2014). Springer

[34] Fukuda, K., Matsui, T.: Finding all the perfect matchings in bipartite graphs. Applied Mathematics Letters **7**(1), 15–18 (1994)

[35] Zhang, Z., Zhang, X., Wen, X.: Directed hamilton cycles in digraphs and matching alternating hamilton cycles in bipartite graphs. SIAM J. Discret. Math. **27**(1), 274–289 (2013). https://doi.org/10.1137/110837188

[36] Bulteau, L., Marchand, B., Ponty, Y.: A New Parametrization for Independent Set Reconfiguration and Applications to RNA Kinetics. In: Golovach, P.A., Zehavi, M. (eds.) 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), vol. 214, pp. 11–1115. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany (2021). https://doi.org/10.4230/LIPIcs.IPEC.2021.11. https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2021.11

[37] Tamaki, H.: A polynomial time algorithm for bounded directed path-width. In: International Workshop on Graph-Theoretic Concepts in Computer Science, pp. 331–342 (2011). Springer

[38] Chen, J., Kanj, I.A.: Constrained minimum vertex cover in bipartite graphs: complexity and parameterized algorithms. Journal of Computer
54 *Bipartite IS Reconfiguration: General and RNA-inspired Algorithms* and System Sciences **67**(4), 833–847 (2003)

[39] Lovász, L., Plummer, M.D.: Matching Theory vol. 367. American Mathematical Soc., ??? (2009)

[40] Zhang, Z.-B., Lou, D.: Bipartite graphs with a perfect matching and digraphs. arXiv preprint arXiv:1011.4359 (2010)

[41] McCaskill, J.S.: The equilibrium partition function and base pair binding probabilities for rna secondary structure. Biopolymers: original research on biomolecules **29**(6-7), 1105–1119 (1990)

[42] Ponty, Y.: Efficient sampling of rna secondary structures from the boltzmann ensemble of low-energy: the boustrophedon method. Journal of mathematical biology **56**(1), 107–127 (2008)

[43] de Berg, M., Jansen, B.M., Mukherjee, D.: Independent-set reconfiguration thresholds of hereditary graph classes. Discrete Applied Mathematics **250**, 165–182 (2018)