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

HAL
open science

# Independent set reconfiguration: general and RNA-focused parameterized algorithms

Théo Boury, Laurent Bulteau, Bertrand Marchand, Yann Ponty

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

## To cite this version:

Théo Boury, Laurent Bulteau, Bertrand Marchand, Yann Ponty. Independent set reconfiguration: general and RNA-focused parameterized algorithms. 2023. hal-04094405

HAL Id: hal-04094405

https://hal.science/hal-04094405

Preprint submitted on 11 May 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.
<figure><img src="image_1.png" /></figure>

**HAL**
open science

# Independent set reconfiguration: general and RNA-focused parameterized algorithms

Théo Boury, Laurent Bulteau, Bertrand Marchand, Yann Ponty

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

## To cite this version:

Théo Boury, Laurent Bulteau, Bertrand Marchand, Yann Ponty. Independent set reconfiguration: general and RNA-focused parameterized algorithms. 2025. hal-04094405v2

HAL Id: hal-04094405

https://hal.science/hal-04094405v2

Preprint submitted on 11 Jun 2025 (v2), last revised 9 Dec 2025 (v3)

**HAL** is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est destinée au dépôt et à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.
# Independent set reconfiguration: general and RNA-focused parameterized algorithms

Théo Boury¹,³, Laurent Bulteau², Bertrand Marchand¹,²
and Yann Ponty¹

¹LIX, Ecole Polytechnique, Palaiseau, France.

²LIGM, Université Gustave Eiffel, Marne-la-Vallée, France.

³ENS Lyon, Lyon, France.

Contributing authors: theo.boury@ens-lyon.fr; laurent.bulteau@upem.fr; bertrand.marchand@lix.polytechnique.fr; yann.ponty@lix.polytechnique.fr;

## Abstract

In this paper, we study the Independent Set (IS) reconfiguration problem in graphs, and its applications to RNA kinetics. An IS reconfiguration is a scenario transforming an IS $L$ into another IS $R$, inserting/removing one vertex at a time while keeping the cardinalities of intermediate sets as large as possible. We focus on the bipartite variant where only start and end vertices are allowed in intermediate ISs. Our motivation is an application to the RNA energy barrier, a classic hard problem from bioinformatics, which asks, given two RNA structures given as input, whether there exists a reconfiguration pathway connecting them and staying below an energy threshold. A natural parameter for this problem would be the difference between the initial IS size and the threshold (barrier). We first show the para-NP hardness of the problem with respect to this parameter. We then investigate two new parameters, the cardinality range $\rho$ and a measure of arboricity $\Phi$. $\rho$ denotes the maximum allowed size difference between an IS along the reconfiguration and a maximum IS, while $\Phi$ is a measure of the amount of “branching” in the two input RNA structures. We show that bipartite IS reconfiguration is XP for $\rho$ in the general case, and XP for $\Phi$ in the sub-case of bipartite graphs stemming from RNA instances. We give two different routes yielding XP algorithms for $\rho$: The first is a direct $O(n^2)$-space, $O(n^{2\rho+2.5})$-time algorithm based on a separation lemma; The second builds on a parameterized equivalence
# Bipartite Independent Set Reconfiguration: General and RNA-inspired Parameterized Algorithms

Théo Boury¹,³, Laurent Bulteau², Bertrand Marchand¹,² and Yann Ponty¹

¹LIX, Ecole Polytechnique, Palaiseau, France.

²LIGM, Université Gustave Eiffel, Marne-la-Vallée, France.

³ENS Lyon, Lyon, France.

Contributing authors: theo.boury@ens-lyon.org;
laurent.bulteau@u-pem.fr;
bertrand.marchand@lix.polytechnique.fr;
yann.ponty@lix.polytechnique.fr;

## Abstract

The computation of energy barriers between RNA structures is a classic NP-hard problem in bioinformatics, of which the Independent Set (IS) reconfiguration in bipartite graphs represents a natural generalization. Parameterized algorithms, based on parameters taking limited or bounded values on biological instances, are thus crucial towards practical solutions. In this work, we show that bipartite IS reconfiguration is slice-wise Polynomial (XP) solvable for both the range $ρ$ of IS sizes allowed along the reconfiguration, and the arboricity $Φ$ when the input is restricted to a circle graph. Such a setting is relevant to Bioinformatics as it provides a solution to the RNA energy barrier problem. We propose algorithms based on a divide-and-conquer approach, yielding a $O(n^2)$-space, $O(n^{2ρ+2.5})$-time algorithm for the range $ρ$, and a $O(n^{Φ+2})$-space, $O(n^{Φ+3})$-time algorithm for the arboricity $Φ$. Then, we demonstrate the practicality of these algorithms on a benchmark consisting of random RNA instances.
## 2 Parameterized Independent Set Reconfiguration for RNA kinetics

with the directed pathwidth problem, leading to a $O(n^{\rho+1})$-space, $O(n^{\rho+2})$-time algorithm for the reconfiguration problem through an adaptation of a prior result by Tamaki [1]. This equivalence is an interesting result in its own right, connecting a reconfiguration problem (which is essentially a connectivity problem within a reconfiguration network) with a structural parameter for an auxiliary graph. For $\Phi$, our $O(n^{\Phi+1})$-algorithm stems from seeing the problem as an instance of minimum cumulative-cost scheduling, and relies on a merging procedure that might be of independent interest. These results improve upon a partial $O(n^{2\rho+2.5})$-algorithm that only applied to the RNA case. We also demonstrate their practicality of these algorithms through a benchmark on small random RNA instances.

**Keywords:** reconfiguration problems - parameterized algorithms - RNA bioinformatics - directed pathwidth - minimal cumulative cost scheduling

# 1 Introduction

**Reconfiguration problems.** Reconfiguration problems informally ask whether there exists, between two configurations of a system, a reconfiguration pathway entirely composed of legal intermediate configurations, connected by legal moves. In a thoroughly studied sub-category of these problems, configurations correspond to feasible solutions of some optimization problem, and a feasible solution is legal when its quality is higher than a specified threshold.

Examples of optimization problems for which reconfiguration versions have been studied include DOMINATING SET, VERTEX COVER, SHORTEST PATH or INDEPENDENT SET, which is our focus in this article. Associated complexities range from polynomial (see [2] for examples) to NP-complete (for bipartite independent set reconfiguration [3]), and even PSPACE-complete for many of them [3, 4]. Such computational hardness motivates the study of these problems under the lens of parametrized complexity [4–7], in the hope of identifying tractable sub-regimes. Typical parameters considered by these studies focus on the value of the quality threshold (typically a solution size bound) defining legal configurations and the length of the reconfiguration sequences.

**Directed pathwidth.** Directed pathwidth, originally defined in [8] and attributed to Robertson, Seymour and Thomas, represents a natural extension of the notions of pathwidth and path decompositions to directed graphs. Like its undirected restriction, it may alternatively be defined in terms of graph searching [9], path decompositions [10, 11] or vertex separation number [1, 12]. An intuitive formulation can be stated as the search for a visit order of the directed graph, using as few active vertices as possible at each step, and such that no vertex may be deactivated until all its in-neighbors have been activated. Although an FPT algorithm is known for the undirected pathwidth [13], it remains open whether computing the directed pathwidth admits a FPT
# 1 Introduction

Reconfiguration problems informally ask whether there exists a valid reconfiguration sequence between two given configurations of a system. In a thoroughly studied sub-category of these problems, configurations correspond to feasible solutions of some optimization problem, and a feasible solution is legal when its quality is higher than a specified threshold. Examples of optimization problems for which reconfiguration versions have been studied include DOMINATING SET, VERTEX COVER, SHORTEST PATH or INDEPENDENT SET. Associated complexities range from polynomial (see [1] for examples) to NP-complete (for bipartite independent set reconfiguration [2]), and even PSPACE-complete for many of them [2, 3]. Such computational hardness motivates the study of these problems under the lens of parametrized complexity [3–7], in the hope of identifying tractable sub-regimes. For instance, the general version of the Independent set reconfiguration problem was proven W[1]-hard [3, 4] parameterized by the minimum allowed size of intermediate sets, and fixed-parameter tractable for planar graphs or graphs of bounded degree [5]. Typical parameters considered in these studies focus on the value of the quality threshold (typically a solution size bound) defining legal configurations and the length of the reconfiguration sequences.

## Problem statement

In this work, we focus on the independent sets reconfigurations in bipartite graphs. Specifically, we consider BIPARTITE INDEPENDENT SET RECONFIGURATION in the Token Addition Removal (TAR) model following the terminology of Lokshtanov and Mouawad [2], which establish the NP-completeness of the problem through the equivalent k- VERTEX COVER RECONFIGURATION.

Without loss of generality, we restrict ourselves to the case where the start and end configurations are the two sides of the bipartite graph, and part of the input, typically denoted as $L$ ("start" vertices) and $R$ ("end" vertices). We use $\alpha(G)$ to denote the size of a maximum independent set of $G$, noting that $\alpha(G)$ can be computed in polynomial time on bipartite graphs.

## BIPARTITE INDEPENDENT SET RECONFIGURATION (BISR)

**Input:** Bipartite graph $G = (V, E)$ with partition $V = L \cup R$; integer $\rho$

**Output:** True if there exists a sequence $I_0 \cdots I_\ell$ of independent sets of $G$ such that

* $I_0 = L$ and $I_\ell = R$;

* $|I_i| \ge \alpha(G) - \rho, \forall i \in [0, \ell]$;

* $|I_i \triangle I_{i+1}| = 1, \forall i \in [0, \ell-1]$.

False otherwise.

Figure 1 shows an example of an instance of BISR, along with a possible reconfiguration pathway.
algorithm. XP algorithms [1, 12] are known, and have been implemented in practice [14, 15].

**RNA energy barrier.** RNAs are single-stranded biomolecules, which fold onto themselves into 2D and 3D structures through the pairing of nucleotides along their sequence [16]. Thermodynamics then favors low-energy structures, and the RNA energy barrier problem asks, given two structures, whether there exists a re-folding pathway connecting them that does not go through unlikely high-energy intermediate states [17, 18]. Interestingly, the problem falls under the wide umbrella of reconfiguration problems described above, namely the reconfiguration of solutions of optimization problems (here, energy minimization). An important specificity of the problem is that the probability of a refolding pathway depends on the energy difference between intermediate states and the *starting point* rather than the absolute energy value. Another aspect is that since some pairings of the initial structure may impede the formation of new pairings for the target structure, it induces a notion of *precedence constraints*, and may therefore also be treated as a *scheduling* problem, as carried out in [19, 20].

**Problem statement.** In our work, we focus on independent set reconfigurations where only vertices from the start or end ISs ($L$ and $R$) are allowed within intermediate ISs. This amounts to considering the induced subgraph $G[L \cup R]$, bipartite by construction. We write $\alpha(G)$ for the size of a maximum independent set of $G$ (recall that $\alpha(G)$ can be computed in polynomial time on bipartite graphs).

BIPARTITE INDEPENDENT SET RECONFIGURATION (BISR)

**Input:** Bipartite graph $G = (V, E)$ with partition $V = L \cup R$; integer $\rho$

**Parameter:** $\rho$

**Output:** True if there exists a sequence $I_0 \cdots I_\ell$ of independent sets of $G$ such that

* $I_0 = L$ and $I_\ell = R$;

* $|I_i| \ge \alpha(G) - \rho, \forall i \in [0, \ell]$;

* $|I_i \triangle I_{i+1}| = 1, \forall i \in [0, \ell - 1]$.

False otherwise.

The vertices of $L$ and $R$ will typically respectively be called “start” and “end” vertices. We further assume that when a bipartite graph $G$ is given, a specification of which side is $L$ (the “start” set) and which is $R$ (the “end” set) is given. When we explicitly need to state which sets are the “start” and “end” sets, we will write $G_{L \to R}$.

Figure 1 shows an example of an instance of BISR and a possible reconfiguration pathway. We introduce the *cardinality range* (or simply *range*) $\rho = \max_{1 \le i \le \ell} \alpha(G) - |I_i|$ as a natural parameter for this problem, since it measures
<figure><img src="image_3.png" /><figcaption>**Fig. 1** Bipartite independent set (IS) reconfiguration sequence from an IS $L$ (blue) to an IS $R$ (red). Vertices included in the current IS $I$ are indicated by a filled background and white font, and we have $I_0 \equiv L$ and $I_{|L|+|R|} \equiv R$. Here the smallest intermediate IS has cardinality 3 and the largest IS has cardinality 5 so this scenario has range $\rho = 2$.</figcaption></figure>

In the following we restrict our attention to *monotonous* sequences, i.e. any vertex of $R$ (resp. $L$) is inserted (resp. removed) exactly once from the independent set along the reconfiguration sequence. This monotonicity assumption does not impact the existence of a solution, as shown by Lokshtanov and Mouawad [2, Theorem 2], and notably implies that the configuration sequence length is $\ell = |L| + |R|$.

## RNA energy barrier

Our main motivation for revisiting this reconfiguration problem, and exploring new parameters, stems from its strong connection with the RNA ENERGY-BARRIER problem, a classic problem in RNA Bioinformatics whose NP-hardness was established by Manuch *et al* [8].

RNAs are single-stranded biomolecules, which fold onto themselves into 2D and 3D structures through the pairing of nucleotides along their sequence [9]. Thermodynamics then favors low-energy structures (i.e. with a high number of base-pairs as a first approximation), and the RNA energy barrier problem asks, given two structures, whether there exists a re-folding pathway connecting them that does not go through unlikely high-energy intermediate states [8, 10].

Interestingly, the problem falls under the wide umbrella of reconfiguration problems, namely the reconfiguration of solutions of optimization problems (here, energy minimization). An important specificity of the problem is that the probability of a refolding pathway depends on the energy difference between *intermediate* states and the starting point rather than the final energy value. Moreover, the incompatibility of certain pairings of the initial and target structures induces *precedence constraints*, leading the barrier to be computed as the solution of a *scheduling* problem [11, 12].

## Parameters

Motivated by applications to the RNA energy barrier problem, we study three parameters for BISR:

* A natural parameter in the context of RNA is the (energy) *barrier k*. Given a solution $I_0, \dots, I_\ell$ to BISR, it is defined as $k = \max_{1 \le i \le \ell} |L_i|$ –
4 Parameterized Independent Set Reconfiguration for RNA kinetics

<figure><img src="image_3.png" /><figcaption>**Fig. 1** Example of a bipartite independent set reconfiguration from $L$ (blue) to $R$ (red). Selected vertices at each step have a filled background. All intermediate ISs have size at least 3, and the optimal IS has size 5, so this scenario has a range of 2; it can easily be verified that it is optimal.</figcaption></figure>

a distance to optimality. As mentioned above, another natural parameter for RNA kinetics is the *barrier*, denoted $k$, and defined as $k = \max_{1 \le i \le l} |L_i - I_i|$. Intuitively, $k$ measures the size difference from the starting point rather than from an “absolute” optimum. Note that $k = \rho - (\alpha(G) - |L|)$, so one has $0 \le k \le \rho$. Both parameters are obviously similar for instances where $L$ is close to being a maximum independent set, which is generally the case in RNA applications, but in theory the range $\rho$ can be arbitrarily larger than the barrier $k$.

**Our results.** We first prove that in general, the barrier $k$ may not yield any interesting parameterized algorithm, since BISR is Para-NP-hard for this parameter.

We thus focus on two other parameterizations, the *range* $\rho$, as defined above and illustrated in Figure 1, and the *arboricity* $\Phi$ in the case of RNA instances, as illustrated on Figure 7.

For the range $\rho$, we prove that BISR is in $\mathbf{XP}$ by providing two distinct algorithmic strategies to tackle it. Our first algorithmic strategy stems from a parameterized equivalence we draw between BISR parameterized by $\rho$ and the problem of computing the directed pathwidth of directed graphs. Within this equivalence, $\rho$ maps exactly to the directed pathwidth. This allows to apply $\mathbf{XP}$ algorithms for *DIRECTED PATHWIDTH* to BISR while retaining their complexity, such as the $O(n^{\rho+2})$-time, $O(n^{\rho+1})$-space algorithm from Tamaki [1] (with $n = |V|$). This equivalence between directed pathwidth and bipartite independent set reconfiguration is itself an interesting result, as it connects a *structural* problem, whose parameterized complexity is open, with a reconfiguration problem of the kind that is routinely studied in parameterized complexity [4–7].

The other algorithmic strategy for BISR parameterized by $\rho$ is more direct, and runs with a time complexity of $O(n^{2\rho}\sqrt{nm})$ ($m = |E|$) but using only $O(n^2)$ space. It relies on a separation lemma involving, if it exists, a *mixed*
<figure><img src="image_4.png" /><figcaption>**Fig. 2** Connection between BISR and the RNA (direct) energy barrier problem in a simple energy model where valid base pairs homogeneously contribute $-1\text{kcal.mol}^{-1}$. (A & C) Two exemplary RNA source/destination structures, having respective arboricities $\Phi_L$ and $\Phi_R$ (see highlighted leaves). The arboricity parameter of the instance is defined as $\Phi = \min(\Phi_L, \Phi_R) = 1$; (B) Optimal sequence of compatible base pairs removal/addition (i.e reconfiguration sequence) with energy barrier $k = 3$ (kcal.mol$^{-1}$) and range $\rho = 4$; Representations of the instance as a bipartite circle graph (D) and associated conflict graph (E), of which any independent set can be interpreted as a (pseudoknot-free) secondary structure $S$, consisting of $|S|$ base pairs and having energy $-|S|$ kcal.mol$^{-1}$.</figcaption></figure>

$|I_i|$ and represents the maximum allowed deviation from the *starting* cardinality;

* We introduce the *cardinality range* $\rho$, abbreviated as *range* in the following, defined as $\rho = \max_{1 \le i \le \ell} \alpha(G) - |I_i|$. The range $\rho$ is always greater than the barrier $k$, and their values coincide whenever $|L| = \alpha(G)$;

* Finally, to exploit specific features of RNA instances, we define the *arboricity* $\Phi$. Consider a bipartite circle graph $G = (L \cup R, E)$, with $R$ and $L$ both represented as non-intersecting chords on a circle. Choosing an arbitrary first position in the circle enables to define the number $\Phi_L$ (resp. $\Phi_R$) of chords that are minimal by inclusion in $L$ (resp. $R$). The arboricity of an instance is then defined as $\Phi = \min(\Phi_R, \Phi_L)$.

The arboricity parameter is particularly relevant to RNA bioinformatics, where it coincides with the number of occurrences of a structural motif named *hairpin or terminal loops*. Its value remains fairly modest in comparison to the length of RNA (#nucleotides). For instance, over the 28,370 structures found in the non-redundant version of the BPRNA dataset [13], more than half feature less that 2 hairpins, 10% have more than 5 hairpins, and we observe an overall average value of 4.2 hairpins.

To the best of our knowledge, prior to our work, these parameters had not been considered for reconfiguration problems. In the case of INDEPENDENT SET RECONFIGURATION under the TAR model, only the overall lower bound
<figure><img src="image_4.png" /><figcaption>**Fig. 2** (A) Example of two RNA structures, and the corresponding value for the arboricity Φ. Within this work, we consider only “conflict-free” secondary structures that can be seen as well-parenthesized strings. Φ is then the number of “terminal” pairs of matching parentheses, highlighted by gray shading. (B) Example of a conflict bipartite graph associated to two input secondary structures. The arcs (base-pairs) of both structures are the vertices of the graph, and two vertices are in conflict if the corresponding arcs are not nested in one another. By “RNA instances of BISR”, we mean instances of BISR in which the bipartite graph is such a conflict graph of two RNA structures.</figcaption></figure>

maximum independent set of $G$ containing at least one vertex from both parts of the graph. In the specific case of bipartite graphs arising from RNA reconfiguration, we improve the run-time of the subroutine computing a mixed MIS to $O(n^2)$ (rather than $O(\sqrt{nm})$), with a dynamic programming approach.

As for the arboricity $\Phi$, we also show membership in XP of BISR restricted to RNA instances, through dynamic programming over the sub-trees of $T(S)$ for one of the input structures $S$ (see Figure 7).

We present benchmark results for all algorithms, on random instances of general bipartite graphs as well as instances of the RNA ENERGY BARRIER problem. The approach based on directed pathwidth yields reasonable solving times for RNA strings of length up to ~150 nucleotides.

**Techniques.** The equivalence between BISR parameterized by $\rho$ and directed pathwidth is obtained by defining a directed graph from a *maximum matching* of the input bipartite graph. Our more “direct” algorithm for the $\rho$ parameterization is an example of the “bounded search-tree” technique [21], enabled by a *separation lemma*.

As for the arboricity parameterization, the XP algorithm we present involves seeing the problem in terms of *cumulative cost-optimal scheduling* [22]. In particular, we develop a *merge* procedure for combining optimal solutions on disjoint graphs into an optimal solution for the union of the graphs. We believe this merge procedure and its associated concepts (canonical solutions, preferability criteria) can be of independent interest.
on the size of the independent set ($α(G) - ρ$) had been studied in a parame-
terized setting [3, 4]. The length of the reconfiguration sequence has also been
considered [4], but this parameter is fixed in our case (as remarked above). The
two previous parameters have also been combined with structural parameters,
such as modular-width [14] or tree-width [15]. To finish, other parameterized
results involve reconfiguration under more constrained models, such as token
sliding and token jumping [7, 16], and do not apply to our problem.

Our results

We first prove that BISR is Para-NP-hard for the barrier *k*, ruling out any
parameterized tractability for *k*. We thus shift our attention to the range
parameter *ρ*, leading to more appealing outcomes. Our first result is a direct
XP algorithm for this parameter, denoted * Divider-Schedule*, using a divide-
and-conquer approach:

**Theorem 1** There exists a $O(n^2)$-space, $O(n^{2\rho+2.5})$-time XP algorithm for BISR parameterized by the range $\rho$.

Considering an alternative approach, we also establish a parameterized
equivalence between BISR with parameter $\rho$ and the DIRECTED PATHWIDTH
problem. Literature XP algorithms for DIRECTED PATHWIDTH thus yield XP
algorithms for BISR, e.g. the algorithm presented by Nagamochi [17] yields a
$O(n^2)$-space and $O(\rho n^{2\rho})$-time algorithm for BISR.

Finally we focus on bipartite circle graphs, thus returning to our origi-
nal motivation in computing the RNA ENERGY-BARRIER. We consider the
arboricity parameter $\Phi$ which, for RNA instances, coincides with the number of
terminal loops, thus taking very modest values within typical inputs. Our main
result for this parameter is the following XP algorithm, called *Subtree-Schedule*:

**Theorem 2** There exists a $O(n^{\Phi+2})$-space, $O(n^{\Phi+3})$-time XP algorithm for BISR restricted to "RNA instances" (i.e. bipartite circle graph as defined later) parameterized by the arboricity $\Phi$.

Subtree-Schedule also uses a divide-and-conquer technique, with the divi-
sion step begin facilitated by the specific structure of independent sets in circle
graphs. However, joining solutions for two subproblems into a larger one turned
out to be a non-trivial task. In fact, we show that a direct formalization of
this problem, that we call MERGE, is NP-hard. Our XP algorithm thus relies
on a careful analysis of the solutions produced for subproblems, based on a
novel notion of canonicity. At the core of this result lies an involved proof that
canonical solutions for subproblems can always be found, and merged in linear
time.

Beyond its use in Subtree-Schedule, the linear-time merge algorithm is
interesting in its own right, since it is not specific to circle graphs. In particular,
**Outline.** To start with, Section 2 presents some previously known results related to BISR, and some notations and definitions we will use throughout the article. Then, Section 3 shows that BISR is equivalent to the computation of *directed pathwidth* in directed graphs. Section 4 presents the separation lemma and merge procedure on which our direct XP algorithm in $\rho$ and our XP algorithm in $\Phi$ are based. The related concepts of canonical schedule and preferability between schedules are also introduced in this section. Section 5 and Section 6 build on the technical results of Section 4 to present our direct XP algorithm parameterized by $\rho$ and our algorithm XP in $\Phi$ in the RNA case. To finish, Section 7 explains some optimizations specific to RNA reconfiguration instances, and presents our numerical results.

# 2 Preliminaries

## 2.1 State of the art

**Computational hardness.** BIPARTITE INDEPENDENT SET RECONFIGURATION was proven NP-complete in [3], through the equivalent $k$- VERTEX COVER RECONFIGURATION problem. Formulated in terms of RNAs, and restricted to secondary structures (i.e. the subset of bipartite graphs that can be obtained in RNA reconfiguration instances), it was independently proven NP-hard in [17]. To the authors' knowledge, its parameterized complexity remains open.

Independent set reconfiguration in an unrestricted setting (allowing vertices which are outside from the start or end independent sets, i.e. in possibly non-bipartite graphs) when parameterized by the minimum allowed size of intermediate sets has been proven W[1]-hard [4, 5], and fixed-parameter tractable for planar graphs or graphs of bounded degree [6]. Whether this more general problem is in XP for this parameter remains open. We note that in this setting, parameter $\rho$ seems slightly less relevant since it involves computing a maximal independent set in a general graph (i.e. testing if there exists a reconfiguration from $\emptyset$ to $\emptyset$ with range $\rho$ is equivalent to deciding if $\alpha(G) \ge \rho$).

**Heuristics.** Given the great practical importance of the RNA Energy barrier problem in Bioinformatics (BISR in the RNA case), several heuristics [23, 24] have been developed for it. In this paper, we assess the potential of parameterized algorithmics for the development of efficient *exact* algorithms for the problem, starting with a simple energy model (corresponding to BIPARTITE INDEPENDENT SET RECONFIGURATION).

**Exact algorithms.** As for algorithms for BISR, the closest precedent is an algorithm by Thachuk et al. [18]. It is restricted to RNA secondary structure conflict graphs, and additionally to conflict graphs for which both parts *L* and *R* are *maximum independent sets* of *G*. In this restricted setting, although it is not stated as such, [18] provides an XP algorithm with respect to the barrier parameter *k* which then coincides with the range parameter $\rho$ that we introduce. In this paper, we extend this line of study by showing the
it augments the set of tools that can be used in a search towards an FPT algorithm for BISR and for DIRECTED PATHWIDTH.

Both Divider-Schedule and Subtree-Schedule have been implemented, and tested on both random bipartite circle graphs (for Divider-Schedule) and random RNA instances (for Divider-Schedule and Subtree-Schedule). We demonstrate the possibility of (exactly) computing energy barriers between structured RNAs of length $\lesssim 40$.

## Outline

Following this introduction, we give in Section 2 a formal presentation of BISR in terms of schedules (Section 2.1), its parameters (Section 2.2), and the MERGE subproblem along with its NP-hardness proof (Section 2.3). Section 3 states three connections between BISR and other problems from the literature: first with the RNA ENERGY-BARRIER in bioinformatics, and second with the MINIMAL CUMULATIVE COST SCHEDULING problem. The third connection, elaborated in Section 3.3, describes the equivalence between BISR and DIRECTED PATHWIDTH, giving in particular an indirect XP algorithm for BISR with parameter $\rho$.

We then present our algorithms in Section 4: first the Strict Divider algorithm (Section 4.2), used as a subroutine in Divider-Schedule (Section 4.3). Section 4.4 details our linear Canonical Merge algorithm used in Subtree-Schedule (Section 4.5). Each algorithm is presented with its complexity analysis, and advanced correctness proofs are deferred to Section 5. To finish, Section 6 presents our empirical results on random bipartite graphs and random RNA instances, confirming the relative efficiency of our algorithms, while suggesting much more favorable typical behaviors than expected from the worst-case complexities.

## 2 Preliminaries

After general notations below, we define a schedule formalism for BISR (see Example 1), then graph parameters and finally the MERGE subproblem. We refer the reader to Section 4.1 for further algorithm-specific definitions (e.g. *divider* and *canonical*), and to Section 5 for advanced definitions relating to correctness proofs.

For a graph $G = (V, E)$, we write $V(G)$ for the set of vertices of $G$, and $G[X]$ (resp. $G \setminus X$) with $X \subseteq V(G)$ for the subgraph of $G$ induced by $X$ (resp. $V(G) \setminus X$). The *reverse* of a bipartite directed graph $G = (L \cup R, E)$ is $\overleftarrow{G} = (L' \cup R', E)$ such that $L' = R, R' = L$. Lists are written using square brackets, with indices starting at 1, $||$ for the length and the dot $\cdot$ for concatenation. For instance, $S = [S[1], \dots, S[|S|]]$ for any list $S$. We write $[i : j]$ for intervals of integers.
Para-NP-hardness of BISR for *k* in the general setting. We further show that generalizing *k* into *ρ* allows to retain membership in XP.

Recent unpublished work [19, 20] describe polynomial-time algorithm for restricted input versions of BISR. More precisely, within RNA instances of BISR, they tackle the Φ = 1 case, called “bipartite permutation graphs” in [20] and “convex bipartite partial orders” in [19]. The specialization of XP algorithm we describe for Φ yields a O(n³) algorithm in that case, improving over the O(n⁶ log n) of [20].

## 2.2 Preliminary results

**Restriction to the monotonous case.** A reconfiguration pathway for BIPARTITE INDEPENDENT SET RECONFIGURATION is called *monotonous* or *direct* if every vertex is added or removed exactly once in the entire sequence. The length of a monotonous sequence is therefore necessarily: $ℓ = |L \cup R| = |L| + |R|$. Theorem 2 from [3] tells us that if *G*, *ρ* is a yes-instance of bipartite independent set reconfiguration, then there exists a *monotonous* reconfiguration between *L* and *R* respecting the constraints. We will therefore restrict without loss of generality our study to this simpler case. In the more restricted set studied in [18], this was also independently shown.

**Hardness for the barrier parameter.** In the general case where *L* is not necessarily a maximal independent set, the range and barrier parameters (respectively *ρ* and *k* = *ρ* − (α(*G*) − |*L*|)) may be arbitrarily different. The following result motivates our use of parameter *ρ* for the parameterized analysis of BISR.

**Proposition 1** BISR is Para-NP-hard for the energy barrier parameter *k* (i.e. NP-hard even for a constant value of *k*, here with *k* = 0).

*Proof* We use additional vertices in *R* to prove this result. Informally, such a vertex may always be inserted first in a realization: it improves the starting IS from $|L|$ to $|L| + 1$, so the lower bound on the rest of the sequence is shifted from $|L| - k$ to $|L| - (k - 1)$, effectively reducing the barrier without simplifying the instance. Thus, we build a reduction from the general version of BISR: given a bipartite graph *G* with parts *L* and *R* and an integer *ρ*, we construct a new instance $G' = (L' \cup R, \rho)$ with parts $L' = L$ and $R'$ equal to $R \cup N_R$ and $\rho' = \rho$. $N_R$ is composed of $|L| - (\alpha(G) - \rho)$ isolated vertices (we can assume without loss of generality that this quantity is non-negative, otherwise ($G, \rho$) is a trivial no-instance), completely disconnected from the rest of the graph.

Note that $\alpha(G') = \alpha(G) + |N_R| = |L| + \rho$, so the barrier in $(G', \rho')$ is $k = \rho - (\alpha(G') - |L|) = 0$. A realization for $(G, \rho)$ can be transformed into a realization for $(G', \rho)$ by inserting vertices from $N_R$ first, and conversely, vertices from $N_R$ can be ignored in a realization for $(G', \rho)$ to obtain a realization for $(G, \rho)$. Therefore, since BISR is NP-Complete, it is also Para-NP-hard w.r.t the barrier $k$. $\square$
## 2.1 Reconfiguration as an edge-scheduling problem

A schedule for a graph $G$ or a subset $X$ of $V(G)$ is an (ordered) list of vertices such that each vertex of $V(G)$ (resp. of $X$) appears exactly once. We denote by $\tilde{S}$ the reverse of a schedule $S$, i.e. the list of elements of $S$ in reverse order. We write $V(S)$ for the set of vertices appearing in $S$. When the context is clear, we use $S$ instead of $V(S)$, e.g. in $G[S]$ for the subgraph induced by vertices of $S$, $S \subseteq T$ if the vertices of $S$ are a subset of the vertices of $T$, etc.

We write $S \sqsubseteq S'$ (resp. $S \sqsubseteq S'$) if schedule $S$ is a prefix (resp. strict prefix) of a schedule $S'$. Given a set $X$ of vertices, we write $S \setminus X$ (resp. $S \cap X$) for the schedule of $V(S) \setminus X$ (resp. $V(S) \cap X$) using the same relative order as $S$. These notations are extended to pairs $(S, S')$ of schedules, with $S \setminus S' = S \setminus V(S')$ and $S \cap S' = S \cap V(S')$.

Given a subset $X$ of vertices, we define $I(X) = (L \setminus X) \cup (R \cap X) = L\Delta X$. We say that $X$ is licit if $I(X)$ is an independent set. We write $\delta(X)$ for the balance of $X$ defined as

$$ \delta(X) = |L \cap X| - |R \cap X| = |L| - |I(X)|. $$

A schedule $S$ is licit if $V(P)$ is licit for each prefix $P$ of $S$; note that $S$ is licit if and only if $\forall r \in R$, the neighborhood $N(r)$ of $r$ in $G$ appears before $r$ in $S$. For a licit schedule $S$ of $G$, the barrier of $S$, denoted $bg(S)$ is its highest balance among its prefixes:

$$ bg(S) := \max_{P \subseteq S} \delta(P) \quad \text{and} \quad bg(\emptyset) = 0. $$

The budget of a graph $G$ is then the smallest budget over licit schedules:

$$ bg(G) := \min_{S} \{bg(S) | S \text{ licit schedule of } G\}. $$

A schedule $S$ is optimal if it is licit and $bg(S) = bg(G)$. Given these definitions, we propose an alternative formulation of BISR, proven to be equivalent in Section 3.2.

### BIPARTITE INDEPENDENT SET RECONFIGURATION (BISR)

**Input:** Bipartite constraint graph $G = (V = L \cup R, E)$, barrier $k \in \mathbb{N}^+$.

**Output:** True if $bg(G) \le k$, False otherwise.

**Example 1** Consider the instance $G = (L \cup R, E)$, $k = 2$ of BISR presented in Figure 1, and the depicted solution. The schedule associated to the solution is the list of added/removed vertices at successive steps, i.e. $S = [c, b, i, g, e, d, h, a, f]$. This formalism gives a more succinct representation of the solution, focusing on local steps. Independent sets can be retrieved by taking the symmetric difference between $L$ and the corresponding prefixes, e.g. $I_3 = I(S[1:3]) = L\Delta\{c, b, i\} = \{a, d, e, i\}$. The schedule is licit since any vertex in $R$ (say, $h$) is scheduled after its neighbors (b, c and d).
## 2.3 Definitions

The following definitions and notations will be used throughout the paper. They allow to link, at an intermediary step along a reconfiguration, the set of processed vertices to the current independent set and its size.

**Licit subsets.** Given a subset $X$ of vertices, we define $I(X) = (L \setminus X) \cup (R \cap X) = L\Delta X$. We say that $X$ is licit if $I(X)$ is an independent set. Intuitively, in a bipartite graph $G$ with sides $L$ and $R$, $I(X)$ is the independent set obtained after processing the vertices of $X$, starting from $L$ ($L \cap X$ removed, $R \cap X$ added).

**Permutation formulation.** An equivalent representation of a monotonous reconfiguration pathway $I_0...I_\ell$ from $L$ to $R$ for a graph $G$ is a *permutation* $S$ of $L \cup R$. We will also use the term of *schedule*. The $i$-th vertex of the permutation is the vertex that is *processed* (i.e. added or removed) between $I_{i-1}$ and $I_i$ (this formulation lightens the representation of a solution, from a list of vertex sets to a list of vertices). We write $P \sqsubseteq S$ if $P$ is a prefix of $S$, and $V(P)$ (or simply $P$ if the context is clear) for the set of vertices appearing in $P$. A permutation $S$ is licit if $V(P)$ is licit for each prefix $P$ of $S$; note that $S$ is licit if and only if $\forall r \in R$, the neighborhood $N(r)$ of $r$ in $G$ appears before $r$ in $S$.

**Balance $\delta$ and $\rho$-realizations.** Given a subset $X$ of vertices, we write $\delta(X) = |L \cap X| - |R \cap X|$. With this quantity, $|I(X)| = |L| - \delta(X)$. $\delta(X)$ is called the *balance* of $X$, as it corresponds to the size difference between the initial IS $L$ and the current IS $I(X)$. Then, $S$ is a permutation (or *schedule*) of barrier $k$ if $S$ is licit and for each prefix $P \sqsubseteq S$, $\delta(V(S)) \le k$. Equivalently, $S$ is a $\rho$-realization if $S$ is licit and such that for each prefix $P \subseteq S$, $|I(P)| \ge \alpha(G) - \rho$ (i.e. $\delta(V(P)) \le \rho + |L| - \alpha(G)$). This is consistent with the fact that $\rho = k + \alpha(G) - |L|$.

**Budget.** Finally, given a bipartite graph $G$ and a licit permutation $S$ for $G$, we write $bg(S)$ for the barrier of $S$, i.e.

$$bg(S) = \max_{P \sqsubseteq S} |I(P)| - |L| = \max_{P \sqsubseteq S} \delta(P)$$

The *budget* of a graph $G$ is the best possible budget of a licit permutation of $G$. Denoting by $\mathcal{L}(G)$ the set of licit permutations of $G$:

$$bg(G) = \min_{S \in \mathcal{L}(G)} bg(S)$$

A related quantity is the best possible *range* of a graph $G$, which we write $\rho(G)$. It verifies $\rho(G) = bg(G) + \alpha(G) - |L|$. Note that with these definitions, the BISR problem can be equivalently defined as deciding, given a graph $G$ and an upper-bound $\rho$, whether $\rho(G) \le \rho$.
The budget of S is attained e.g. with its length-6 prefix: bg(S) = δ([c, b, i, g, e, d]) = 2 (= 4 vertices in L − 2 vertices in R).

2.2 Graphs and relevant parameters

Although BISR is relevant to general bipartite graphs, we also aim at design-
ing optimized algorithms for instances stemming from the RNA ENERGY-
BARRIER problem. In this context, instances can be restricted to *bipartite circle
graphs*, as described below. The main intuition is that RNA base-pairs in a sec-
ondary structure can be drawn as non-intersecting chords on a circle. Taking
both *L* and *R* chords together yields a bipartite conflict graph with intersec-
tions only between chords of different sides, as illustrated in Figure 2. Before
introducing further graph parameters, we introduce necessary formalism to
describe bipartite circle graphs.

Circle graphs are defined using the notion of *chords* over a circle. Electing
an arbitrary linear ordering of the circle nodes, each chord can be encoded
as pairs of integers (*i*, *j*) with *i* < *j*. The chord (*i*₁, *j*₁) is *nested* in (*i*₂, *j*₂) if
*i*₂ < *i*₁ < *j*₁ < *j*₂, in which case we write (*i*₁, *j*₁) ⊂ (*i*₂, *j*₂). The chords (*i*₁, *j*₁)
and (*i*₂, *j*₂) are *parallel* and we write (*i*₁, *j*₁) || (*i*₂, *j*₂) if *i*₁ < *j*₁ < *i*₂ < *j*₂ or
*i*₂ < *j*₂ < *i*₁ < *j*₁. If two chords are neither nested nor parallel, we say they are
*crossing* (then *i*₁ < *i*₂ < *j*₁ < *j*₂, *i*₂ < *i*₁ < *j*₂ < *j*₁, or they share a position:
{*i*₁, *j*₁} ∩ {*i*₂, *j*₂} ≠ ∅). A graph *G* = (*V*, *E*) is a *circle graph* if *V* is a set of
chords, and *E* contains an edge {*u*, *v*} if and only if *u* and *v* are crossing.

An independent set *I* of a circle graph *G* is thus a set of pairwise non
crossing chords. A vertex *u* in *I* is a *leaf* of *I* if there is no *v* ∈ *I* nested in
*u*. For the rest of the manuscript, the restriction of BISR to bipartite circle
graphs will be denoted CG-BISR.

Parameters

We remind the three parameters investigated within this manuscript:

* The *barrier* is the integer *k* used in the definition of BISR: it is a natural parameter which has direct interpretation and implications in RNA bioinformatics. However, from an algorithmic point of view, its promises are limited since BISR remains NP-hard even when *k* = 0, as shown in Section 3.1;

* The *range* of *S* is defined as $\rho(S) = bg(S) + \alpha(G) - |L|$, and $\rho(G) = bg(G) + \alpha(G) - |L|$ (we use the phrase *range-ρ schedule* to designate schedules with range at most $\rho$). In terms of independent sets, it corresponds to the size difference between the largest possible independent set and the smallest allowed one;

* The *arboricity* $\Phi$ is only defined for bipartite circle graphs. Given a conflict-free set of chords *C*, $\Phi_C$ is defined as the cardinality of the subset of chords, also called *leaves of* *C*, which are minimal with respect to the nested relationship $\subset$. We write $\Phi_L$ and $\Phi_R$ for the number of leaves
# 3 Connection with Directed Pathwidth

We first present a parameterized reduction from bipartite independent set reconfiguration to an input-restricted version, on graphs allowing for a perfect matching. Then, this version of the problem is shown to be simply equivalent to the computation of directed pathwidth on general directed graphs.

## 3.1 Definitions

**Parameterized reduction.** In this section, we provide a definition of directed pathwidth, and then prove its parameterized equivalence to the bipartite independent set reconfiguration problem. We say two problems $\mathcal{P}_1$ and $\mathcal{P}_2$ are parametrically equivalent when there exists both a *parameterized reduction* from $\mathcal{P}_1$ to $\mathcal{P}_2$ and another from $\mathcal{P}_2$ to $\mathcal{P}_1$. A sufficient condition to obtain a parameterized reduction [21] from problem $\mathcal{P}$ to problem $\mathcal{Q}$ is to have a function $\varphi$ from instances of $\mathcal{P}$ to instances of $\mathcal{Q}$ such that (i) $\varphi(x)$ is a yes-instance of $\mathcal{Q} \Leftrightarrow x$ is a yes-instance of $\mathcal{P}$, (ii) $\varphi$ can be computed in polynomial time (iii) the parameter of $x$ and the parameter of $\varphi(x)$ are equal.

**Interval representation.** Our definition of directed pathwidth relies on interval embeddings. Alternative definitions can be found, for instance in terms of directed path decomposition or directed vertex separation number [1, 9, 12].

**Definition 1 (Interval representation)** An *interval representation* of a directed graph $H$ associates each vertex $u \in H$ with an interval $I_u = [a_u, b_u]$, with $a_u, b_u$ integers. An interval representation is *valid* when $(u, v) \in E \Rightarrow a_u \le b_v$. I.e., the interval of $u$ must start before the interval of $v$ ends. If $m, M$ are such that $\forall u, m \le a_u, b_u \le M$, we define the *width* of an interval representation as $\max_{m \le i \le M} |\{u| i \in I_u\}| - 1$

**Definition 2 (directed pathwidth)** The *directed pathwidth* of a directed graph $H$ is the minimum possible width of a valid interval representation of $H$. We note this number $dpw(H)$.

**Nice interval representation.** An interval representation is said to be *nice* when no more than one interval bound is associated to any given integer, and the integers associated to interval bounds are exactly $[1...2 \cdot |V(H)|]$. Any interval representation may be turned into a nice one without changing the width by introducing new positions and “spreading events”. See Appendix B.1 for more details.

**Directed graph from perfect matching.** Given a bipartite graph $G$ allowing for a perfect matching $M$, we construct an associated directed graph $H$ in the following way: the vertices of $H$ are the edges of the matching, and $(l, r) \to (l', r')$ is an arc of $H$ iff $(l, r') \in G$. Alternatively, $H$ is obtained from $G, M$ by orienting the edges of $G$ from $L$ to $R$, and then contracting the edges of $M$. We will denote this graph $H(G, M)$, and simply call it the *directed*
in $L$ and $R$ respectively. Finally, as shown in Figure 2, the arboricity of a
CG-BISR instance $(L, R)$ is defined as $\Phi := \min(\Phi_L, \Phi_R)$.

## 2.3 Merging schedules

In order to use divide-and-conquer strategies (as we will use in Section 4.5), we should be able to aggregate sub-solutions for sub-parts of an input into global solutions. A natural problem is thus to merge two optimal schedules for distinct subgraphs. Surprisingly, this turns out to be a challenging question, even when the two distinct graphs are disconnected. Indeed, we show that the MERGE problem (stated below) is NP-hard as, in general, merging may imply reshuffling entirely the input schedules (see below Theorem 3). We use the following formalism for the general MERGE problem:

**MERGE**

**Input:** A bipartite graph $G = (V = L \cup R, E)$, partitions $L = L_1 \cup L_2$, $R = R_1 \cup R_2$ of either side, and optimal schedules $S_1$ and $S_2$ respectively for $G_1 = G[L_1 \cup R_1]$ and $G_2 = G[L_2 \cup R_2]$. An integer $k$.

**Output:** Does there exist a budget-$k$ schedule for the union graph $G'$?

Both our algorithms make use of Merge subroutines, which are performed in polynomial time (Lemma 3 and Theorem 7) but only for restricted settings (in Lemma 3 the partition corresponds to a *divider* of the graph, in Theorem 7 sequences $S_1$ and $S_2$ are *canonical*, see Section 4.1 for more details). Similarly in the literature, a merge procedure had already been designed in [18] for the minimal cumulative cost scheduling problem, of which BIPARTITE INDEPENDENT SET RECONFIGURATION is an instance. However the notion of *strictly-optimal schedules*, sharing similarities with our canonical schedules, was not adaptable to algorithmic application, see Section 4.5. The unpublished pre-prints [11, 19] also claimed to derive a merge procedure for the same problem. However, the merge (*combine*) procedure of [19] relies on an unproven observation (Observation 5.5 in [19]). Even if this observation was correct, the merge procedures we design achieve a better (linear) complexity. As for [11], it is unclear (in a similar fashion as [18]) how it could adapt to our algorithmic application.

The key observation justifying the use of restricted instances is that, in full generality, MERGE is NP-hard, using a reduction from BISR as proven below.

**Theorem 3** MERGE is NP-hard, even when restricted to instances where subgraphs $G_1$ and $G_2$ are disconnected.

*Proof* The reduction is illustrated in Figure 3. Consider an instance of BISR consisting of a bipartite graph $G' = (L \cup R, E)$ with $2n$ vertices and an integer $k'$. We assume without loss of generality that $|L| = |R| = \alpha(G') = n$: indeed, such a setting can be obtained by inserting $\alpha(G') - |L|$ vertices in $L$ and $\alpha(G') - |R|$ vertices in $R$. We build an instance of MERGE consisting of $G, G_1, G_2, S_1, S_2$ and $k$ as follows.
10

graph associated to G, M. Such a construction is relatively standard and can
be found in [25, 26], for instance.

## 3.2 Directed pathwidth $\Leftrightarrow$ Bipartite independent set reconfiguration

**Perfect matching case.** Our main structural result regarding directed path-
width is the following. Its proof relies on interval representations, with the
intuition that the number of open intervals at a given position is the number
of dependencies that have been lifted, but not compensated for yet.

**Proposition 2** Let $G$ be a bipartite graph allowing for a perfect matching $M$. Then $G$ allows for a $\rho$-realization iff $dpw(H(G, M)) \le \rho$. Conversely, given any directed graph $H$, there exists a bipartite graph $G$ allowing for a perfect matching $M$ such that $H = H(G, M)$ and $G$ allows for a $\rho$-realization iff $dpw(H) \le \rho$.

*Proof* We start with the first statement, the equivalence between $dpw(H(G, M)) \le \rho$ and the existence of a $\rho$-realization for $G$. First note that, since $G$ allows for a perfect matching, we have $|L| = |R|$, and by König's theorem, if $K$ is a minimum vertex cover of $G$, $|K| = |L| = |R|$. Since $\alpha(G) = |L| + |R| - |K|$ we have $\alpha(G) = |L| = |R|$. I.e. $L$ and $R$ are maximum independent sets of $G$.

⇒ If $G$ allows for a $\rho$-realization, then $\exists P$ ordering of the vertices of $G$ such that every prefix $X_i$ of $P$ verifies $|I(X_i)| = |L| - \delta(X_i) = \alpha(G) - \delta(X_i) \ge \alpha(G) - \rho$. Therefore $\delta(X_i) = |X_i \cap L| - |X_i \cap R| \le \rho$.

Consider a vertex $(l, r)$ of $H(G, M)$, with $(l, r)$ an edge of $M$. We associate to $(l, r)$ the interval $[a_{(l,r)}$, $b_{(l,r)}$] where $a_{(l,r)}$ is such that $P[a_{(l,r)}] = l$. i.e, it corresponds to the step in the reconfiguration where $l$ is removed. Likewise, $b_{(l,r)}$ is such that $P[b_{(l,r)}] = r$.

For any edge $(l, r) \to (l', r')$ of $H$, necessarily $(l, r') \in G$, which implies that in the reconfiguration sequence, $l$ has to be removed before $r'$ is added. $l$ appears therefore earlier than $l$ in $P$, and $a_{(l,r)} \le b_{(l',r')}$. The intervals we have defined therefore form a valid interval representation of $H$.

In addition, the intervals intersecting a given position $i$ correspond to pairs $(l, r)$ where, at step $i$, $l$ has already been removed while $r$ is yet to be added. Since the decrease in independent set size incurred by the removal of $l$ is compensated by the addition of its match $r$, the number of intervals intersecting position $i$ is exactly $\delta(X_i)$, the imbalance of the $i$-prefix of $P$, which by hypothesis is $\le \rho$.

⇔ Suppose the directed graph $H(G, M)$ associated to $G, M$ has directed pathwidth $\le \rho$. Consider an optimal nice interval representation for $H$. In this representation, a vertex $(l, r)$ of $H$ is associated to an interval $[a_{(l,r)}, b_{(l,r)}]$. Thanks to the structure of *nice* interval representation, we
10

<figure><img src="image_5.png" /><figcaption>**Fig. 3** Reduction from BISR to MERGE. Top: the input graph $G'$ with $n = 3$, and optimal (unknown) schedule $S'$ with barrier $k' = 2$. Middle: graph $G'$ is extended into $G = G_1 + G_2$, with subgraph solutions $S_1, S_2$, such that an optimal solution $S^*$ (bottom) for $G$ necessarily includes an optimal solution for $G'$.</figcaption></figure>

Graph $G_1$ consists of $G'$ augmented with a $(n+1, n+1)$-biclique $B_1$, such that the $n+1$ left vertices of $B_1$ are dependencies of all the right vertices of $G'$. Additionally, one left vertex denoted $x_1$ is added as a dependency of all the right vertices of $G'$. Graph $G_2$ consists of a single biclique (denoted $B_2$) with $n+1$ left vertices and $k'+1$ right vertices. The full graph $G$ consists of the disjoint union of $G_1$ and $G_2$.

Let $S_1$ start with $B_1$, followed by vertex $x_1$, and a simplistic schedule for $G'$, consisting of all the left vertices of $G'$ followed by all the right vertices of $G'$, i.e. $L \cdot R$. We have $bg(S_1) = n+1$ and all vertices in the right part of $G_1$ have degree at least $n+1$, so $bg(G_1) \ge n+1$ and $S_1$ is optimal. Similarly for $G_2$, all right vertices have degree $n+1$ so $bg(G_2) \ge n+1 = bg(S_2)$ and $S_2$ is optimal.

We will now show that $bg(G) \le n+1$ if and only if $bg(G') \le k'$. In the first direction, if $G'$ admits a schedule $S'$ with $bg(S') \le k'$, then $S = B_1 \cdot B_2 \cdot x_1 \cdot S'$ is a schedule with barrier $n+1$ for $G$ (with $B_1, B_2$ in any order in which all left vertices are before the right vertices) and $bg(G) \le n+1$.

In the other direction, assume there exists a schedule $S$ of $G$ with $bg(S) \le n+1$. Consider the first occurrence of a right vertex of $B_1$ in $S$, and the prefix $P$ before that occurrence. $P$ contains all $n+1$ left vertices of $B_1$, and some set $X$ of vertices in $\{x_1\} \cup L \cup R \cup B_2$. We have $\delta(P) = n+1+\delta(X)$ and $\delta(P) \le bg(S) = n+1$ so $\delta(X) \le 0$. Thus, $X$ is necessarily empty: any non-empty licit subset in $B_2$ has a strictly positive balance, and any non-empty licit subset in $G_1$ also has a positive balance (since $|L| = \alpha(G')$) and further requires $x_1 \in X$ thus yielding a strictly positive balance. Overall, $B_1$ is necessarily scheduled first (once the first right vertex of $B_1$ is scheduled, all remaining vertices of $B_1$ can also be scheduled without increasing the budget). Likewise, the prefix before the first right vertex of $B_2$ may not contain any vertex in $\{x_1\} \cup L \cup R$, so scheduling any part of $\{b_1\} \cup G$ before $B_2$ would yield a barrier $> n+1$. Therefore, $S$ starts with $B_1 \cdot B_2$. Then, $x_1$ is a universal vertex for the remainder of the graph, so $S$ continues with $x_1$ and some schedule $S'$ of $G'$. Since $\delta(B_1 \cdot B_2 \cdot x_1) = n-k'+1$, the remaining barrier for $S'$ is $bg(S') \le n+1-(n-k+1) = k'$, concluding the proof. $\square$
simply define a permutation $P$ of $L \cup R$ with, $\forall (l, r) P[a_{(l,r)}] = l$ and $P[b_{(l,r)}] = r$.

If $(l, r')$ is an edge of $G$, with $r$ the match of $l$ and $l'$ the match of $r'$, then the construction above ensures that $l$ is before $r'$ in $P$. For two matched vertices, this is also immediate. Then, as for two matched vertices $l, r$, the removal of $l$ is compensated by the addition of $r$, for any prefix $X_i$ of $P$, the imbalance $\delta(X_i)$ is exactly the number of intervals intersecting position $i$. By assumption, we therefore have $\delta(X_i) \le \rho$ and $P$ is a $\rho$-realization.

For the second part of the statement, given a directed graph $H$, we construct a bipartite graph $G$ with sides $L, R$ allowing for a perfect matching $M$ in the following way: for each vertex $u \in H$ we introduce two vertices $(l_u, r_u)$ in $G$. We assign $l_u$ to $L$ and $r_u$ to $R$, connect $l_u$ and $r_u$ and add the edge to the matching $M$. We now add an edge from $l_u$ to $r_v$ in $G$ for any $(u, v) \in E(H)$. $G$ now verifies $H = H(G, M)$, and by the result above, $dpw(H) \le \rho$ iff $G$ allows for a $\rho$-realization.

□

The first half of Proposition 2 is a parameterized reduction from an input-restricted version of BIPARTITE INDEPENDENT SET RECONFIGURATION to directed pathwidth. The restriction is on bipartite graphs allowing for a perfect matching. The second half is a parameterized reduction in the other direction. In both cases, the parameter value is directly transferred, which allows to retain the same complexity when transferring an algorithm from one problem to the other.

**Non-perfect-matching case.** In the case where $G$ does not allow for a perfect matching, we construct $G'$ allowing for a perfect matching $M'$, and such that $\rho(G) = \rho(G') = dpw(H(G', M'))$. $G'$ is obtained from $G$ through the addition of new vertices. Specifically, with a bipartite graph $G$ with sides $L, R$, a maximum matching $M$ of $G$, and the set $U$ of unmatched vertices in $G$, we extend $G$ with $|U|$ new vertices in two sets $N_L, N_R$, giving a new graph $G'$, with sides $L' = L \cup N_L, R' = R \cup N_R$, in the following way ($M'$ is initialized to $M$):

* For each $u \in L \cap U$, we introduce a new vertex $r(u) \in N_R$, connect it to all vertices of $L'$, and add the edge $(u, r(u))$ to $M'$.

* Likewise, for each $v \in R \cap U$, we introduce $l(v) \in N_L$, connect it to all vertices of $R'$ and add $(v, l(v))$ to $M'$.

Note that $M'$ is a perfect matching of the extended bipartite graph $G'$.

**Proposition 3** *With $G, G'$ defined as above, we have that $G$ allows for a $\rho$-realization iff $G'$ allows for a $\rho$-realization.*

*Proof* First note that by König's Theorem, $\alpha(G') = |M'| = |M| + |U| = \alpha(G)$, so it suffices to ensure that any realization for $G$ can be transformed into a realization for $G'$ where independent sets are lower-bounded by the same value, and vice versa.
<figure><img src="image_6.png" /><figcaption>**Fig. 4** Connections between parameterized variants of BISR and other algorithmic problems (RNA barrier, Directed pathwidth, Scheduling). The selected parameter is given for each problem (white boxes). Solid (red) arcs denote parameterized reductions between problems, leading to groups of equivalent problems (light gray boxes). The dashed (blue) arcs denote direct reductions that do not preserve the parameter, i.e. all problems are NP-hard.</figcaption></figure>

## 3 Connections to other problems

The BISR problem connects quite straightforwardly with two other known problems with their own states of the art (Sections 3.1 and 3.2). The first is the RNA ENERGY-BARRIER problem that stems from our bioinformatics motivation, which represents the specialization CG-BISR of BISR to circle graphs. The second is MINIMAL CUMULATIVE COST SCHEDULING, which is equivalent and whose formalism is used through our method. Finally, a third problem (Section 3.3), DIRECTED PATHWIDTH, can be proven equivalent to BISR through a more involving reduction proof where the directed pathwidth value corresponds to the range. A summary of all used and drawn connections in this paper is available in Figure 4.

### Parameterized reduction

A parameterized reduction [20] from problem $\mathcal{P}$ to problem $\mathcal{Q}$ consists in a function $\varphi$ from instances of $\mathcal{P}$ to instances of $\mathcal{Q}$ such that the following conditions hold:

1. $\varphi(x)$ is a yes-instance of $\mathcal{Q} \Leftrightarrow x$ is a yes-instance of $\mathcal{P}$;

2. $\varphi$ can be computed in polynomial time;

3. the parameter of $\varphi(x)$ is bounded by a function depending solely on the parameter of $x$.

Thus, any FPT (resp. XP) algorithm for $\mathcal{Q}$ combined with such a reduction from $\mathcal{P}$ to $\mathcal{Q}$ gives an FPT (resp. XP) algorithm for $\mathcal{P}$.
12 *Parameterized Independent Set Reconfiguration for RNA kinetics*

Let $P$ be any $\rho$-realization of $G$, then $P' = N_L \cdot P \cdot N_R$ is a $\rho$-realization for $G'$,
with $N_L$ and $N_R$ laid out in any order. Indeed, $P'$ satisfies the precedence constraint,
and any intermediate set $I$ in $P'$ satisfies one of the following cases: $L \subseteq I$, $R \subseteq I$, or
$I$ is an intermediate set from $P$, so in any case it has size at least $\alpha(G) - \rho = \alpha(G') - \rho$.

Conversely, because of the all-to-all connectivity between $N_L$ and $R$ and between $L$ and $N_R$, a realization for $G'$ needs to have $N_L$ before any vertex from $R$, and have $N_R$ after all vertices from $L$. Without loss of generality, it is therefore of the form $N_L \cdot P \cdot N_R$ with $P$ a realization of $G$, and $G$ allows for a $\rho$-realization. $\square$

The construction above in fact yields a parameterized reduction from BIPARTITE INDEPENDENT SET RECONFIGURATION to its input-restricted version on bipartite graphs allowing for a perfect matching. This input-restricted version is in turn parametrically equivalent to directed pathwidth by Proposition 2. Hence the following corollary:

**Corollary 1** *BIPARTITE INDEPENDENT SET RECONFIGURATION is parametrically equivalent to DIRECTED PATHWIDTH*

It allows to import algorithmic results for DIRECTED PATHWIDTH and
apply them to BIPARTITE INDEPENDENT SET RECONFIGURATION. In partic-
ular:

**Corollary 2** *There exists a $O(n^{\rho+1})$-space, $O(n^{\rho+2})$-time XP algorithm for BIPARTITE INDEPENDENT SET RECONFIGURATION.*

*Proof* Application of the algorithm from [27]. See also Section 7.1 for more details.

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

An implementation and a benchmark of this algorithm in the context of
RNA kinetics is presented in Section 7.

**Limitations.** The high space-complexity of [27] may hinder the practicality of the algorithm, and the $\rho$ parameterization may not necessarily be adapted to the RNA kinetics context. This is why we also explored direct algorithms parameterized by $\rho$ for the problem, presented in Section 5, and another parameterization (arboricity) in Section 6. They rely on the technical elements presented in the following section, regarding the role of *mixed* maximum independent sets (i.e. intersecting both $L$ and $R$) in $G$ as *separators* and the problem of optimally *merging* optimal solutions for disconnected instances.

**4 Lemmata: algorithmic building blocks**

This section introduces our main technical results, which are the build-
ing blocks of the algorithms we propose for BIPARTITE INDEPENDENT SET
RECONFIGURATION. They consist of a *separation lemma* and a *merge* proce-
dure.
We say that two problems $P_1$ and $P_2$ are parametrically equivalent when there exists both a parameterized reduction from $P_1$ to $P_2$ and another from $P_2$ to $P_1$.

## 3.1 Connection with RNA energy barrier

### RNA structures

RiboNucleic Acids (RNAs) are biomolecules of outstanding interest in molecular biology, which can be represented as strings over an alphabet $\Sigma := \{A, C, G, U\}$. Importantly, these molecules fold on themselves, with individual characters forming pairs, ultimately leading to the adoption of one or several stable conformation(s) called secondary structures. For a string of length $n$, a secondary structure is typically described by a set $S$ of base pairs $(i, j)$, $1 \le i < j \le n$, which all involve distinct positions and are pairwise non-crossing ($\overline{(}i, j), (k, l) \in S$ such that $i \le k \le j \le l$).

On a biophysical level, RNA folding is generally modeled as a stochastic process (kinetics) which, given sufficient time, is expected to converge to a Boltzmann distribution based on the free-energy. However, the number of secondary structures compatible with a given RNA sequence grows exponentially with its length $n$, and so does the number of local minima in the energy landscape. Such a rugged landscape practically hinders the convergence of the folding process towards its ultimate stationary distribution, motivating out-of-equilibrium studies. Toward such studies, a key quantity is the energy barrier $k_{L \to R}$ that needs to be overcome to transition between a source and destination structures. Indeed, transitions rates can be derived from $k_{L \to R}$ values, precomputed for all pairs of relevant structures, enabling a study of simplified folding landscapes.

Note that, in the following, we use $n$ for the number of vertices in the context of general graphs and for the underlying string length in the context of RNA barrier. Both values are interchangeable in the context of complexity asymptotics, assuming that the input graph is indeed bipartite (so each position may occur only once in each of $L$ and $R$), and that unused positions are ignored (each position $i$ appears in some pair of $L$ and/or $R$).

### The energy barrier problem

In this section, we consider the problem of computing the direct energy barrier separating two RNA secondary structures [21], i.e. finding the minimal amount of energy (\#broken base pairs) needed to transition between $L$ and $R$, two secondary structures, with intermediate structures being conflict-free and consisting of base pairs from $L \cup R$. Formally, the RNA ENERGY-BARRIER problem can then be stated as such:
## 4.1 Definitions

We use the permutation representation of reconfiguration scenarios, i.e. licit permutations of vertices. Note that the intersection, as well as the union, of two licit set of vertices are licit:

**Property 1** Given X, Y two licit subsets of a graph G, both X ∩ Y and X ∪ Y are licit subsets.

*Proof* Let us check that $I(X \cap Y) = L \setminus (X \cap Y) \cup (R \cap X \cap Y)$ is indeed an independent set.

Consider $r \in R$ and suppose $r \in I(X \cap Y)$. Then $r \in R \cap X \cap Y$, and since $X$ is licit, $r \in X \cap R$ implies $N(r) \cap I(X) = \emptyset$ and therefore $N(r) \subset L \cap X$. Likewise, $N(r) \subset L \cap Y$. Therefore $N(r) \subset L \cap X \cap Y$ and $I(X \cap Y)$ does not contain $N(r)$.

Likewise, consider $\ell \in L$, and suppose $\ell \in I(X \cap Y)$. Then $\ell \in L \setminus (X \cap Y)$, so either $\ell \in L \setminus X$ or $\ell \in L \setminus Y$. Since $X$ and $Y$ are licit, either $N(r) \cap (R \cap X) = \emptyset$ or $N(r) \cap (R \cap Y) = \emptyset$. In any case, $N(\ell) \cap I(X \cap Y) = \emptyset$ and $I(X \cap Y)$ is indeed an independent set.

Let us now check that $I(X \cup Y)$ is also an independent set. In a similar fashion, consider $r \in I(X \cup Y) \cap R$. $r \in R \cap (X \cup Y)$ implies $r \in R \cap X$ or $r \in R \cap Y$, which implies since $X$ and $Y$ are licit $N(r) \cap (L \setminus X) = \emptyset$ or $N(r) \cap (L \setminus Y) = \emptyset$, i.e. $N(r) \subseteq X$ or $N(r) \subseteq Y$. In any case, $N(r) \cap (L \setminus (X \cup Y)) = \emptyset$.

To finish, consider $\ell \in I(X \cup Y) \cap L$. We have $\ell \in L \setminus (X \cup Y)$, so $\ell \notin X$ and $\ell \notin Y$. Since $X$ and $Y$ are licit, $N(\ell) \cap X = \emptyset$ and $N(\ell) \cap Y = \emptyset$, so $I(X \cup Y) \cap N(\ell) = R \cap (X \cup Y) \cap N(\ell) = \emptyset$, and $I(X \cup Y)$ is indeed and independent set.

**Permutation sub-sampling.** Given a realization *P* of *G* and a set of vertices *X*, we write *P* ∩ *X* for the sub-sequence of *P* consisting of the vertices of *X*, without changing the order. Likewise, *P* \ *X* denotes the sub-sequence of *P* consisting of vertices *not* in *X*.

**Definitions: separators.** A mixed maximum independent set *I* of *G* is an independent set of *G* of maximum cardinality containing at least a vertex from both parts. Note that not every bipartite graph contains such a set. A separator *X* is a subset of *L* ∪ *R* such that *I*(*X*) is a mixed maximum independent set of *G*.

**Separators and inversions.** When otherwise specified, a bipartite graph *G* has sides *L* and *R*, and the independent set reconfiguration goes from *L* to *R*. In the proofs below however, it will be useful to also consider the instance of BISR in which *R* is reconfigured into *L*. To differentiate both, given a graph *G*, we write *G*<sub>*L*→*R*</sub> (resp. *G*<sub>*R*→*L*</sub>) or the instance of BISR in which *L* is reconfigured into *R* (resp. *R* into *L*). Likewise, we write *I*<sub>*L*→*R*</sub>(*X*) = (*L* \ *X*) ∪ (*R* ∩ *X*) to denote the independent set obtained by processing *X* starting from *L*, while *I*<sub>*R*→*L*</sub> = (*R* \ *X*) ∪ (*L* ∩ *X*) is the result of processing *X* starting from *R*. Interestingly, a separator for *G*<sub>*L*→*R*</sub> is then also a separator for *G*<sub>*R*→*L*</sub>.
RNA ENERGY-BARRIER

**Input:** Secondary structures $L$ and $R$; Energy barrier $k \in \mathbb{N}^+$

**Output:** True if there exists a sequence $S_0 \cdots S_\ell$ of secondary structures
such that

* $S_0 = L$ and $S_\ell = R$;

* $|S_i| \ge |L| - k, \forall i \in [0, \ell]$;

* $|S_i \triangle S_{i+1}| = 1, \forall i \in [0, \ell - 1]$.

False otherwise.

The problem is NP-hard [8], and the object of ongoing developments in
RNA Bioinformatics [22–25], mainly targeting efficient heuristics addressing
intricate free-energy models.

**Proposition 1** *The RNA ENERGY-BARRIER problem is equivalent to CG-BISR, the restriction of BISR to bipartite circle graphs.*

*Proof* Let $L$ and $R$ be two RNA secondary structures over $[1 \dots n]$, denoted $L = \{(l_i, r_i)\}$ and $R = \{(b_j, e_j)\}$. We can build a graph $G$ with $V = L \cup R$, and such that for $(l_i, r_i) \in L$ and $(b_j, e_j) \in R$, $(l_i, r_i)$, $(b_j, e_j) \in E$ if and only if they cross or share a position, i.e. $(l_i, r_i) \not\subseteq (b_j, e_j)$ and $(b_j, e_j) \not\subseteq (l_i, r_i)$. Consider then a circle with $n$ regularly-spaced positions on it, and the set of chords $L \cup R$. It gives a corresponding embedding $f$ for $G$, that happens to be a circle graph. Thus, there is then an exact correspondence between independent sets of $G$ and valid secondary structures composed of arcs from $L$ and $R$.

Conversely, given a bipartite circle graph $G$, its two sides $L$ and $R$ yield two well-nested arc sets that can be seen as RNA secondary structures. The correspondence is highlighted on Figure 2. $\square$

*Parameterized hardness for the barrier parameter*

Thachuk et al. [10] showed that the restriction of the RNA BARRIER problem, to vertex sets $L$ and $R$ that are both maximum independent sets of $G$, can be solved in $O(n^{O(k)})$ complexity for the barrier parameter $k$. It follows that the restriction of CG-BISR to inputs that are MIS of $G$ is in XP for the barrier parameter $k$, noting that the barrier parameter $k$ coincides with the range parameter $\rho$ in this case.

However for general instances, the range and barrier parameters, respec-
tively $\rho$ and $k = \rho - (\alpha(G) - |L|)$, may arbitrarily differ. In fact, solving both
BISR and CG-BISR for general inputs unfortunately turns out to be hard,
even for the lowest possible value of the barrier $k$, motivating our consideration
of the range parameter $\rho$ instead.

**Proposition 2** *Both BISR and CG-BISR are Para-NP-hard for the energy barrier parameter k, i.e. NP-hard even for a constant value of k (here with k = 0).*
**Property 2** Let $X$ be a separator of $G_{L \to R}$. Then $Y = G \setminus X$ is a separator of $G_{R \to L}$

*Proof* $I_{R \to L}(Y) = (R \setminus Y) \cup (L \cap Y) = (R \setminus (G \setminus X)) \cup (L \cap (G \setminus X)) = (R \cap X) \cup (L \setminus X) = I_{L \to R}(X)$, which is a mixed maximum independent set of $G_{L \to R}$ (same graph as $G_{R \to L}$) □

The two technical results presented in this section, Lemma 4.2 (separation Lemma) and Theorem 4 (merging procedure) are expressed in terms of a notion of *preferability* and *canonical schedules*. The preferability order relation allows to choose between different schedules equivalent in terms of barrier, while a canonical schedule is the “most preferable”. These two notions are defined in the following paragraphs.

**Notations and definitions: canonicity and preferability.** Formally, given a schedule $S$ for a graph $G$, and $-1 \ge -i \ge |L| - \alpha(G)$, we define $\ell_S(-i)$ as the smallest strictly positive integer, if it exists, such that $\delta(S_{\le \ell_S(i)}) = -i$. Likewise, for $i$ such that $-1 \ge -i \ge |R| - \alpha(G)$ we define $r_S(-i)$ as the largest integer $< |S|$, if it exists, such that $\delta(S_{\le r_S(-i)}) + |R| - |L| = i$.

We then write $\text{pref}_i(S) = \text{bg}(S_{\le \ell_S(-i)})$ and $\text{suff}_i(S) = \text{bg}(S_{\ge r_S(-i)}) - \delta(r_S(-i))$. The corresponding prefixes and suffixes are denoted by $\text{Pref}_i(S)$ and $\text{Suff}_i(S)$. If $\ell_S(-i)$ does not exist, then $\text{pref}_i(S) = +\infty$, and likewise for $r_S(-i)$ and $\text{suff}_i(S)$. Informally, these quantities are “the budget needed to reach level $-i$” in the forward and reverse directions.

These definitions are illustrated in Figure 3. Note that upon inverting the start set $L$ and final set $R$, then $\ell_S(-i)$, $\text{Pref}_i(S)$ and $\text{pref}_i(S)$ become $r_S(-i)$, $\text{Suff}_i(S)$, $\text{suff}_i(S)$ and vice-versa. To be more precise, given $S$ a schedule, i.e. an order on vertices, let us denote by $\overleftarrow{S}$ its reverse schedule, with opposite order. Then, we have:

$$ \text{Pref}_i(S) = \text{Suff}_i(\overleftarrow{S}) $$

and

$$ \text{pref}_i(S) = \text{suff}_i(\overleftarrow{S}) $$

Based on these quantities, we define a partial order on schedules for $G$:

**Definition 3** (preferability) Given $S$ and $S'$ two schedules for a bipartite graph $G$, we say that $S$ is *preferable* to $S'$ (denoted $S \preceq S'$) if $\text{bg}(S) \le \text{bg}(S')$ and $\forall i$, $\text{pref}_i(S) \le \text{pref}_i(S')$ and $\text{suff}_i(S) \le \text{suff}_i(S')$. In the case of an equality for all criteria, $S \preceq S'$ if $\forall i, \ell_S(-i) \le \ell_{S'}(-i)$ and $r_S(-i) \ge r_{S'}(-i)$.

Finally, we say that $S$ is strictly preferable to $S'$ if $S \preceq S'$ and $S' \not\preceq S$
*Proof* We use additional vertices in $R$ to prove this result, disconnected from the rest of the graph. Informally, such a vertex may always be inserted first in a schedule: it improves the starting IS from $|L|$ to $|L| + 1$, so the lower bound on the rest of the sequence is shifted from $|L|-k$ to $|L|-(k-1)$, effectively reducing the barrier without simplifying the instance. Thus, we build a reduction from the general version of BISR: given a bipartite graph $G$ with parts $L$ and $R$ and an integer $\rho$, we construct a new instance $G'$ with parts $L' = L$ and $R'$ equal to $R \cup N_R$ and $\rho' = \rho$. $N_R$ is composed of $|L| - (\alpha(G) - \rho)$ isolated vertices (we can assume without loss of generality that this quantity is non-negative, otherwise $(G, \rho)$ is a trivial no-instance), completely disconnected from the rest of the graph.

Note that $\alpha(G') = \alpha(G) + |N_R| = |L| + \rho$, so the barrier in $(G', \rho')$ is $k = \rho - (\alpha(G') - |L|) = 0$. A range-$\rho$ schedule for $G$ can be transformed into a range-$\rho$ schedule for $G'$ by inserting vertices from $N_R$ first, and conversely, vertices from $N_R$ can be ignored in a range-$\rho$ schedule for $G'$ to obtain a range-$\rho$ schedule for $G$. Therefore, since BISR is NP-Complete, it is also Para-NP-hard with respect to the barrier parameter $k$.

A similar result also holds for CG-BISR, also Para-NP-hard for the energy barrier parameter $k$. Indeed, in the above hardness proof for BISR, all we require is the ability to add an arbitrary number $N_R$ of isolated vertices to a bipartite circle graph. Therefore, given a bipartite circle graph $G$ with embedding $\{(i_u, j_u) \mid u \in V\}$, let us note $N$ an integer such that $\forall u \in V$, $0 \le i_u < j_u < N$. We can add $N_R$ isolated vertices by associating them with the chords $\{(N + i, N + N_R - i + 1) \mid i \in [N_R]\}$. None of these $N_R$ new chords cross with existing vertices, nor with themselves, as required. $\square$

## 3.2 Connection with Minimum Cumulative Cost Scheduling

In this section, we consider the following problem of computing a scheduling of minimal cumulative-cost over a bipartite constraint graph $G$, and connect it to BISR.

### MINIMAL CUMULATIVE COST SCHEDULING

**Input:** A bipartite constraint graph $G = (V = L \cup R, E)$; budget $k \in \mathbb{N}^+$; cost function $w: V \to \mathbb{R}$.

**Output:** True if there exists a schedule $S = [s_1, \dots, s_l]$ ordering of the nodes of $V$ such that

* $\forall P \subseteq S$, $V(P)$ is licit

* $\sum_{j=1}^i w(v_j) \le k, \forall i \in [1, \ell]$

False otherwise.

Note that the connection between the RNA energy barrier and the scheduling problem was already observed: recent unpublished work [11, 12] describe a polynomial-time algorithm for restricted input versions of BISR. More precisely, within bipartite circle graphs, they consider graphs with arboricity $\Phi = 1$ case, called “bipartite permutation graphs” in [12] and “convex
<figure><img src="image_6.png" /><figcaption>Fig. 3 Illustration of the definition of pref$_{-i}$(S) and suff$_{-i}$(S)</figcaption></figure>

Remark that this relation is neither total nor antisymmetric (there are pairs S, S' with either both S ≪ S' and S' ≪ S' or both S ≁ S' and S' ≁ S'), but it is easily seen to be transitive from the definition. We are mostly interested in the search of global optimums, as formulated below.

**Definition 4** (canonical solution) A schedule *S* that is preferable to any other schedule *S'* for *G* is called a *canonical solution* for *G*.

## 4.2 Separation lemma

Lemma 4.2 (below) on which our algorithm XP in $\rho$ is based is proved using the following “modularity” property of the balance functions. Interestingly, it is almost the same property (sub-modularity), on a different quantity (the in-degrees of vertices) on which rely the XP algorithm for directed pathwidth [1].

**Lemma 1** (modularity) Given licit subsets X and Y, we have:

$$|I(X)| + |I(Y)| = |I(X \cup Y)| + |I(X \cap Y)|$$

and

$$\delta(X \cup Y) + \delta(X \cap Y) = \delta(X) + \delta(Y)$$

*Proof* We have $I(X) = (L \setminus X) \cup (R \cap X)$. Therefore, $|I(X)| = |L \setminus X| + |R \cap X| = |L| - |L \cap X| + |R \cap X|$. Furthermore, $|(X \cup Y) \cap L| = |(X \cap L) \cup (Y \cap L)| = |X \cap L| + |Y \cap L| - |X \cap Y \cap L|$, and likewise for R. The result stems from a subtraction of one equation to the other, and an addition of $|L|$. As for the second part, it comes from the definition $\delta(X) = |L| - |I(X)|$. $\square$

Based on this “modularity”, the following separation lemma is shown by “re-shuffling” a solution into another one going through a mixed MIS.

**Lemma 2** (separation lemma) Let X be a separator of G. If S is a schedule for G, then $(S \cap X) \cdot (S \setminus X) \preceq S$.
bipartite partial orders” in [11]. Note that the specialization of our XP algo-
rithm Subtree-Schedule (Theorem 2) yields an $\mathcal{O}(n^4)$ algorithm in that case,
improving over the $\mathcal{O}(n^6 \log n)$ proposed by Kinne et al. [12].

**Proposition 3** *The MINIMAL CUMULATIVE COST SCHEDULING problem as defined above is equivalent to BISR with $w(l) = 1 \forall l \in L$ and $w(r) = -1 \forall r \in R$.*

*Proof* The formulation is equivalent to the formal definition of BISR in terms of schedule, as defined in Section 2.1. In terms of independent sets, let $\rho = |L|+\alpha(G)-k$, and let $I_i = I\{s_1, \dots, s_i\}$ for all $0 \le i \le l$. Sets $I_i$ are independent sets since the corresponding prefixes are licit, the difference between any two consecutive sets is a single vertex, and the budget constraint translates into $|I_i| \ge |L| - k = \alpha(G) - \rho$. Overall sets $I_0, \dots, I_l$ are a solution for BISR. Conversely, given such a solution for BISR, the corresponding sequence $s_1, \dots, s_l$ can be retrieved by taking $s_i = I_{i-1}\Delta I_i$, and we have the desired properties in terms of licit sets and budget, so $s_1, \dots, s_l$ is a solution for MINIMAL CUMULATIVE COST SCHEDULING. $\square$

**3.3 Connection with Directed Pathwidth**

Perhaps quite surprisingly, we establish connections between BISR and the
problem of computing the *directed pathwidth* of an associated graph. Directed
pathwidth, originally defined in [26] and attributed to Robertson, Seymour
and Thomas, represents a natural extension of the notions of pathwidth and
path decompositions to directed graphs. Like its undirected restriction, it
may alternatively be defined in terms of *graph searching* [27], *path decompo-
sitions* [27–29] or *vertex separation number* [30, 31]. An intuitive formulation
can be stated as the search for a visit order of the directed graph, using
as few active vertices as possible at each step, such that no vertex may be
deactivated until all its in-neighbors have been activated. Although an FPT
algorithm is known for the undirected pathwidth [32], it remains open whether
*DIRECTED PATHWIDTH*, the decision version of computing the directed path-
width admits a FPT algorithm. XP algorithms [17, 30] are known, and have
been implemented in practice [33].

We establish here the equivalence of BISR and DIRECTED PATHWIDTH.
Beyond enabling a direct application of DIRECTED PATHWIDTH algorithms to
the BISR problem, this equivalence is itself an interesting observation. Indeed,
it connects a structural problem, whose parameterized complexity is open,
with a reconfiguration problem of the kind that is routinely studied in param-
eterized complexity [3–6]. The formal definition of DIRECTED PATHWIDTH is
the following.

**Definition 1** [27] A *directed path decomposition* of a directed graph *H* = (*V*, *E*) is a sequence *W*₁, . . . , *W*ₚ of subsets of vertices of *H*, such that:

1. $\cup_{i \in [p]} W_i = V$.

2. For $i, j, k \in [p]$ such that $i < j < k$, $W_i \cap W_k \subseteq W_j$.
*Proof* Let us write $S' = (S \cap X) \cdot (S \setminus X)$, and start by showing $bg(S') \le bg(S)$. Let $\rho' \subseteq S'$. We first introduce the following notation: given a prefix $\rho'$ of $S'$ with $(S \cap X) \supseteq \rho'$, we write $\text{rem}_X(\rho')$ for the smallest prefix $\rho$ of $S$ such that $V(\rho \cup X) = V(\rho')$. This definition is illustrated on Figure 4.

* if $\rho' \subseteq (S \cap X)$, then $\exists \rho \subseteq S$ such that $\rho' = \rho \cap X$, and $\delta(\rho') = \delta(\rho \cap X) = \delta(\rho) + \delta(X) - \delta(\rho \cup X)$ (by the modularity property, Lemma 1). $\delta(X)$ is the smallest possible value for $\delta$, therefore $\delta(X) - \delta(\rho \cup X) \le 0$ and $\delta(\rho') \le \delta(\rho) \le bg(S)$.

* else if $(S \cap X) \supseteq \rho'$, then let $\rho = \text{rem}_X(\rho')$. We have $\delta(\rho') = \delta(\rho \cup X) = \delta(\rho) + \underbrace{\delta(X) - \delta(\rho \cap X)}_{\le 0} \le bg(S)$.

Let us now prove that $\forall i \in [1 \dots \alpha(G) - |L|]$, $\text{pref}_i(S') \le \text{pref}_i(S)$, and in the case of equality $\ell_{S'}(-i) \le \ell_S(-i)$. Let us first note that, since $\delta(X)$ reaches the minimum possible value for $\delta$ over all licit subsets, we have $\forall \sigma \subseteq (S \setminus X)$, $\delta(\sigma) \ge 0$ (otherwise, $\sigma \cup X$ would be a licit subset with $\delta(\sigma \cup X) < \delta(X)$). In addition, remark that since $\delta(X) = |L| - \alpha(G)$, $\text{pref}_i(S') \subseteq S \cap X$. Given these elements, let $\rho' \subseteq \text{pref}_i(S')$, and $\rho \supseteq S$ the smallest prefix of $S$ such that $\rho' = \rho \cap X$. We have $\delta(\rho) = \delta(\rho') + \underbrace{\delta(\rho \setminus X)}_{\ge 0}$, so

$\delta(\rho') \le \delta(\rho)$. It simply remains to show that $\rho \supseteq \text{Pref}_i(S)$ to get $\delta(\rho') \le \text{pref}_i(S)$. Let therefore $\tau$ be a strict prefix of $\rho$. We indeed have $\delta(\tau) = \underbrace{\delta(\tau \cap X)}_{>-i} + \underbrace{\delta(\tau \setminus X)}_{\ge 0} > -i$.

Therefore overall $\text{pref}_i(S') = \max_{\rho' \subseteq \text{Pref}_i(S')} \delta(\rho') \le \text{pref}_i(S)$. In addition, $\delta(\tau) > -i \forall \tau \subseteq \rho$ with $\rho \ne \tau$ implies, when $\text{pref}_i(S) < +\infty$, $\ell_S(-i) \ge \ell_{S'}(-i)$.

As for $\text{suff}_i(S')$, we have $\text{suff}_i(S') = \text{pref}_i(\overleftarrow{S'})$. By Property 2, $Y = G \setminus X$ is a separator for $G_{R \to L}$, and $\overleftarrow{S'} = (\overleftarrow{S} \cap Y) \cdot (\overleftarrow{S} \setminus Y)$. Per the arguments above, $\text{pref}_i(\overleftarrow{S'}) \le \text{pref}_i(\overleftarrow{S})$ and $\ell_{\overleftarrow{S}}(-i) \le \ell_{\overleftarrow{S}}(-i)$. Overall, $\text{suff}_i(S') = \text{pref}_i(\overleftarrow{S'}) \le \text{pref}_i(\overleftarrow{S}) = \text{suff}_i(S)$, and in the case of equality, $r_{S'}(-i) \le r_S(i)$. $\square$

Therefore, if $G$ allows for a mixed independent set, any optimal schedule can be assumed to go through this independent set. A schedule that reaches $\text{IS cardinality } \alpha(G)$ is said to be *simple*. Lemma 2 thus yields the following:

**Corollary 3** Any graph $G$ has a simple optimal schedule.

**Corollary 4** For any schedule $S$ of a bipartite graph $G$, $\exists S'$ simple such that $S' \prec S$

*Proof* Either $G$ does not allow for a mixed MIS, in which case $\alpha(G) = \max(L, R)$ and any schedule is simple, or $G$ allows for a mixed MIS and we can apply Lemma 4.2 to $S$. $\square$

This separation result will be used in Section ?? . We now turn to another algorithmic building block, that is a *merge* procedure for combining solutions for disjoint graphs into a global optimal.
3. For $u, v \in E$, $\exists i \le j$ such that $u \in W_i$, $v \in W_j$.

The width of $W_1, \dots, W_p$ is defined as $\max_{i \in [p]} |W_i| - 1$. The directed pathwidth of $H$ is the minimum possible width of a directed path decomposition of $H$.

## DIRECTED PATHWIDTH

**Input:** Directed graph $H$, integer dpw

**Output:** True if $H$ has directed pathwidth at most dpw, False otherwise.

An equivalent definition in terms of directed vertex separation number [27, 30] can be found in the literature. Note that a directed acyclic graph has directed pathwidth equal to 0 (by taking a decomposition composed of singletons with a topological order).

We show the equivalence between DIRECTED PATHWIDTH and BISR in three steps. First, we give an equivalent (rather standard) definition of directed pathwidth in terms of interval representation. Then, we prove the equivalence between DIRECTED PATHWIDTH and an input-restricted version of BISR, on graphs allowing for a perfect matching. Then, a parameterized reduction from general BISR to its input-restricted version is provided. The overall reduction is illustrated in Figure 5.

## Interval formulation of directed pathwidth

Our reduction makes use of the following equivalent definition of directed pathwidth.

**Definition 2 (Interval representation)** An interval representation of a size-$n$ directed graph $H$ associates each vertex $u \in H$ with a non-empty interval $I_u = [a_u, b_u[$, such that $\bigcup_{u \in V(H)} \{a_u, b_u\} = [1: 2n]$ (i.e. all endpoints are pairwise distinct). An interval representation is valid when $(u, v) \in E \Rightarrow a_u < b_v$. I.e. the interval of $u$ must start before the interval of $v$ ends. The width of an interval representation is $\max_{0 \le i \le 2n} |\{u| i \in I_u\}| - 1$

**Property 1** *The minimum possible width of an interval representation of a directed graph is equal to its directed pathwidth*

*Proof* Let $H = (V, E)$ be a directed graph and $\mathcal{I} = \{I_u\}_{u \in V}$ be an interval representation for $H$. For $i \in [1: 2n]$, we define $W_i = \{u \mid i \in [a_u, b_u]\}$, and argue that $W_1, \dots, W_{2n}$ is a directed path decomposition of $H$. Since $u \in W_{a_u}$, point 1 of Definition 1 is verified. For point 2, let $1 \le i < j < k \le 2n$ and $u \in W_i \cap W_k$. Thus interval $I_u$ contains both $i$ and $k$ and $I_u$ also contains $j$, so $W_i \cap W_k \subseteq W_j$. As for point 3, for $(u, v) \in E$, $a_u < b_v$, guarantees that, denoting $i = a_u$ and $j = b_v - 1$, $u \in W_i$ and $v \in W_j$ while $i \le j$.

In the other direction, let $W_1, \dots, W_p$ be a directed path decomposition of $H$. Assume without loss of generality that $|W_i \Delta W_{i+1}| = 1$ for each $i$ (otherwise, insert
## 4.3 Merge Procedure

**Merging problem.** Given two independent graphs $G_1$ and $G_2$, and two optimal orderings $S_1$ and $S_2$, it is natural to ask whether it is always sufficient to simply *interlace* $S_1$ and $S_2$ to get an optimal solution $G$, or if a *rearrangement* of $S_1$ and/or $S_2$ may be required.

In this section, we answer this question by showing that not only is rearranging is necessary in some cases, but figuring out the optimal rearrangement is NP-hard (Lemma 3). However, we also show that interlacing is enough when the two input schedules are in *canonical form*, as defined in Definition 4. The merging procedure can then be done in linear time, as shown in Theorem 4.

**Related work.** A similar merge procedure had already been designed in [22] for the cumulative cost-optimal scheduling problem, of which BIPARTITE INDEPENDENT SET RECONFIGURATION is an instance. However, the corresponding “canonical form”, *strictly-optimal schedules*, was not adaptable to algorithmic application, described in Section 6. The unpublished pre-prints [19, 28] also claimed to derive a merge procedure for the same problem. However, the merge (“COMBINE”) procedure of [28] relies on an unproven Observation (Observation 5.5 in [28]). Even if this Observation was correct, the merge procedure presented here achieves a better (linear) complexity. As for [19], it is unclear (in a similar fashion as [22]) how it could adapt to our algorithmic application.

**Lemma 3** *Given two bipartite graphs $G_1$ and $G_2$, $S_1$ and $S_2$ optimal schedules for $G_1$ and $G_2$ respectively, and an integer $k$, the problem of deciding whether $bg(G_1 \cup G_2) \le k$ is NP-hard.*

*Proof* We prove the NP-hardness by reduction from the barrier problem. Given therefore a bipartite graph $G$ with $n$ vertices and an integer $k'$, we build $G_1, G_2, S_1, S_2$ and $k$ as follows. $G_1$ consists of $G$ augmented with a $(n+1, n+1)$-biclique $B_1$, such that the $n+1$ left vertices of $B_1$ are dependencies of all the right vertices of $G$. Additionally, one left vertex $b_1$ is added as a dependency of all the right vertices of $G$. $G_2$ consists of a single biclique with $n+1$ left vertices and $k'+1$ right vertices.

Let $S_1$ start with $B_1$, followed by $b_1$, and a simplistic schedule for $G$, consisting of all the left vertices of $G$ followed by all the right vertices of $G$. As $B_1$ is a biclique, $bg(G_1) \ge n+1$ and $S_1$ is optimal. As for $S_2$, the only possible schedule consists of all its left vertices followed by all of its right vertices.

We will now show that $bg(G_1 \cup G_2) \le n+1$ if and only if $bg(G) \le k'$. To start with, if $G$ admits a schedule $S$ with $bg(S) \le k'$, then $B_1 \cdot B_2 \cdot b_1 \cdot S$ is a $n+1$-schedule for $G_1 \cup G_2$ (with $B_1, B_2$ in any order in which all left vertices are before the right vertices) and $bg(G_1 \cup G_2) \le n+1$.

In the other direction, if $bg(G_1 \cup G_2) \le n+1$, then $B_1$ is necessarily scheduled first, as scheduling any part of $B_2$ before $B_1$ would increase the baseline by a strictly positive amount and yield an overall budget > $n+1$. Likewise, scheduling any part of $\{b_1\} \cup G$ before $B_2$ would yield a barrier > $n+1$. Therefore, an optimal schedule
<figure><img src="image_7.png" /><figcaption>**Fig. 5** Equivalence between DIRECTED PATHWIDTH and BISR. Top: an instance of BISR with its optimal schedule. In the general case a maximum matching has unmatched vertices (here, highlighted vertices d and j). We add dummy vertices (respectively l and a) to obtain an equivalent instance $(G, M)$ of BISR with a perfect matching. Bottom: the graph $H(G, M)$ obtained by our reduction, and the corresponding solution for DIRECTED PATHWIDTH. A pathwidth decomposition can be represented either as an arrangement of intervals or of bags of vertices in a directed path decomposition.</figcaption></figure>

intermediate sets removing or introducing vertices one by one). Thus $p = 2n$ (each vertex is introduced and removed exactly once). For $u \in V$, we set $a_u = \min\{i \mid u \in W_i\}$ and $b_u = \max\{i \mid u \in W_i\} + 1$. We have that $a_u \le b_u$ (and that they are well-defined) from point 1 of Definition 1. For $u, v \in E$, since $\exists i \le j$ such that $u \in W_i$ and $v \in W_j$, we have $a_u \le i$ and $b_v \ge j + 1$, and therefore $a_u < b_v$. $\square$

## DPW is equivalent to BISR with a perfect matching

We make use of the following reduction. Given a bipartite graph $G$ allowing for a perfect matching $M$, the directed graph associated to $G, M$, denoted $H(G, M)$, is defined as follows:

* the vertex set of $H(G, M)$ is $M$, i.e. the edges of the matching

* $(l, r) \to (l', r')$ is an arc of $H(G, M)$ if and only if edge $(l, r')$ is in $G$.

Alternatively, $H(G, M)$ is obtained from $G, M$ by orienting the edges of $G$ from $L$ to $R$, and then contracting the edges of $M$. Note that this construction can be found in the literature, see e.g. [34, 35].
is necessary of the same form as before $B_1 \cdot B_2 \cdot b_1 \cdot S$ for some schedule $S$ of $G$. If it has barrier $\le n+1$, then necessarily $bg(S) \le k'$, concluding the proof. $\square$

The notion of preferability gives us a simple criteria to choose between different schedules with the same overall budget. This will be exploited algorithmically in our dynamic programming approach to the bipartite independent set reconfiguration problem in the case for bipartite circle graphs, presented in Section 6.

As for the merge procedure, it will exploit another aspect of canonical solutions: they start with the shortest way, if possible, to get the budget below the original baseline. This is illustrated by the following lemma.

**Definition 5** A licit subset $X$ of a graph $G$ is a *lump* if:

1. $\delta(X) < 0$

2. $\forall X' \subsetneq X$ licit, we have $\delta(X') \ge 0$

Moreover, a lump $X$ is *harmless* if its budget $bg(X)$ is minimal among all lumps, and $|X|$ is minimal among all lumps with this budget.

In other words, when ordering lumps according to the lexicographic order over $(bg(X), |X|)$, a harmless lump is an absolute minimum.

**Property 3** A lump $X$ induces a connected subgraph of $G$.

*Proof* Suppose $G[X]$ is composed of two components induced by $X_1 \subsetneq X$ and $X_2 \subsetneq X$. Both are licit, so by the definition of a lump, $\delta(X_1) \ge 0$ and $\delta(X_2) \ge 0$. However $\delta(X) = \delta(X_1) + \delta(X_2) < 0$, hence a contradiction. $\square$

**Lemma 4** If $S$ is a simple schedule for a bipartite graph $G$ and $X$ is a lump of $G$ admitting an optimal schedule $S_X$ such that $bg(S_X) \le \min(\text{pref}_{-1}(S), bg(S))$, then $S' := S_X \cdot (S \setminus X)$ is preferable to $S$. It is moreover strictly preferable if either $bg(S_X) < \text{pref}_{-1}(S)$ or $|X| < |\text{Pref}_{-1}(S)|$.

*Proof* We first recall the following notation: given a prefix $\rho'$ of $S'$ with $S_X \subseteq \rho'$, we write $\text{rem}_X(\rho')$ for the smallest prefix $\rho$ of $S$ such that $V(\rho \cup X) = V(\rho')$. Conversely, we also define for a prefix $\rho$ of $S$ $\text{add}_X(\rho)$ as the smallest prefix $\rho'$ of $S$ such that $V(\rho \cup X) = V(\rho')$. Note that $\text{add}_X$ and $\text{rem}_X$ are monotonous under the prefix relation. These definitions are illustrated in Figure 4. Note also that for any prefix $\rho$ of $S$, $\rho'' = \text{rem}_X(\text{add}_X(\rho))$ is the smallest prefix $\sigma$ of $S$ such that $V(\sigma \cup X) = V(\rho \cup X)$, so in particular $\rho'' \subseteq \rho$. For any such pair $\rho, \rho'$ with $V(\rho \cup X) = V(\rho')$, we show that $\delta(\rho') \le \delta(\rho)$. Indeed, $\delta(\rho') = \delta(\rho \cup X) = \delta(\rho) + \delta(X) - \delta(\rho \cap X)$ (per the modularity of $\delta$, Lemma 1). Since $\rho \cap X$ is licit (by Property 1) by the definition of lump we have $\delta(\rho \cap X) \ge \delta(X)$ and $\delta(\rho') \le \delta(\rho)$.
**Proposition 4** For any directed graph $H$, there exists a bipartite graph $G$ with perfect matching $M$ such that $H = H(G, M)$

*Proof* We construct a bipartite graph $G$ with sides $L, R$ as follows: for each vertex $u \in V(H)$ we introduce two vertices $l_u, r_u$ in $G$, and let $L = \{l_u | u \in V(H)\}$ and $R = \{r_u | u \in V(H)\}$. We add each edge $(l_u, r_u)$ to $G$ and to the matching $M$, and we further add an edge $(l_u, r_v)$ to $G$ for each arc $u \to v$ in $H$. Thus, $M$ is indeed a perfect matching of $G$ and we have $H = H(G, M)$. $\square$

The following result is our main structural result regarding directed path-width. Intuitively, its proof relies on interval representations, with the intuition that the number of open intervals at a given position is the number of dependencies that have been lifted, but not compensated for yet.

**Proposition 5** Let $G$ be a bipartite graph allowing for a perfect matching $M$. Then $G$ has for a range-$\rho$ schedule if and only if $H(G, M)$ has dpw $\le \rho$.

*Proof* First note that, since $G$ allows for a perfect matching, we have $|L| = |R| = |M|$, and by König's theorem, if $K$ is a minimum vertex cover of $G$, $|K| = |M|$. Since $\alpha(G) = |L| + |R| - |K|$ we have $\alpha(G) = |L| = |R|$. I.e. $L$ and $R$ are maximum independent sets of $G$.

$\Rightarrow$ Let $S$ be a range-$\rho$ schedule of $G$, then there exists a scheduling $S$ such that every prefix $P \subseteq S$ verifies $|L| + \delta(P) \le \alpha(G) + \rho$ i.e. $\delta(P) \le \rho$.

Consider a vertex $(l, r)$ of $H(G, M)$, with $(l, r)$ an edge of $M$. We associate to $(l, r)$ the interval $[a_{(l,r)}, b_{(l,r)}]$ where $a_{(l,r)}$ is such that $S[a_{(l,r)}] = l$. i.e, it corresponds to the step in the reconfiguration where $l$ is removed. Likewise, $b_{(l,r)}$ is such that $S[b_{(l,r)}] = r$.

For any edge $(l, r) \to (l', r')$ of $H$, necessarily $(l, r') \in G$, which implies that in the reconfiguration sequence, $l$ has to be removed before $r'$ is added. $l$ appears therefore earlier than $r'$ in $S$, and $a_{(l,r)} < b_{(l',r')}$. The intervals we have defined therefore form a valid interval representation of $H$.

In addition, the intervals intersecting a given position $i$ correspond to pairs $(l, r)$ where, at step $i$, $l$ has already been removed while $r$ is yet to be added.

Let $0 \le i < 2n$ and $P = S[0..i]$. The intervals containing position $i$ are exactly those for vertex $(l, r)$ such that $a_{(l,r)} \le i < b_{(l,r)}$, i.e. with $a_{(l,r)} \in P$ and $b_{(l,r)} \notin P$: they contribute 1 to the balance in $P$. For all other intervals, $a_{(l,r)}$ and $b_{(l,r)}$ are either both in $P$ or both out of $P$, so they contribute 0 to the balance: overall the balance of $P$ is exactly the width of the interval representation at position $i$. Hence the directed pathwidth of $H$ is $\max_{P \subseteq S}(\delta(P)) \le \rho$.

$\Leftarrow$ Suppose the directed graph $H(G, M)$ associated to $G, M$ has directed path-width $\le \rho$. Consider an optimal interval representation for $H$. where vertex $(l, r)$ of $H$ is associated to interval $[a_{(l,r)}, b_{(l,r)}]$. We consider the schedule $S$ of $L \cup R$ such that $\forall (l, r) S[a_{(l,r)}] = l$ and $S[b_{(l,r)}] = r$.

If $(l, r')$ is an edge of $G$, with $r$ the match of $l$ and $l'$ the match of $r'$, then the construction above ensures that $l$ is before $r'$ in $S$. For two matched vertices, this is also immediate. Then, as for two matched vertices $l, r$, the removal of $l$ is
<figure><img src="image_7.png" /><figcaption>**Fig. 4** Illustration of the definitions of $add_X$ and $rem_X$, used in the proofs of Lemmas 4.2 (only $add_X$),4 and 6. They apply to a typical situation encountered in these Lemmas: a schedule $S$ is shuffled so that a licit set $X$ is processed first. The new schedule $S'$ is valid since $X$ is licit. The purpose of $add_X$ and $rem_X$ is then to draw connections between prefixes of $S$ and corresponding prefixes in $S'$, in order to infer bounds on $bg(S')$, $pref_{-i}(S')$ or $suff_{-i}(S')$.</figcaption></figure>

We can now show that $S'$ is preferable to $S$, starting with $bg(S') \le bg(S)$. Consider a prefix $\rho'$ of $S'$. If $\rho' \subseteq S_X$, then $\delta(\rho') \le bg(X) \le bg(S)$. Otherwise, $S_X \subseteq \rho'$, and $\delta(\rho') \le \delta(\mathrm{rem}_X(\rho')) \le bg(S)$.

Then, we have $\mathrm{pref}_1(S') = bg(S_X) \le \mathrm{pref}_1(S)$ by assumption. To continue, for $i$ such that $\mathrm{pref}_{-i}(S) < +\infty$, we have $\mathrm{pref}_{-i}(S') \subseteq \mathrm{add}_X(\mathrm{pref}_{-i}(S))$ (indeed, $\delta(\mathrm{add}_X(\mathrm{pref}_{-i}(S))) \le \delta(\mathrm{pref}_{-i}(S)) = -i$, so $\mathrm{add}_X(\mathrm{pref}_{-i}(S))$ is some prefix, not necessarily smallest, of $S'$ with balance no more than $-i$). Thus, for any $\rho'$, $S_X \subseteq \rho' \subseteq \mathrm{Pref}_{-i}(S')$, we have $\delta(\rho') \le \delta(\mathrm{rem}_X(\rho'))$ and $\mathrm{rem}_X(\rho')$ is a prefix of $\mathrm{rem}_X(\mathrm{add}_X(\mathrm{Pref}_{-i}(S')))$ so $\delta(\mathrm{rem}_X(\rho')) \le \mathrm{pref}_{-i}(S')$. Overall, any prefix of $\mathrm{pref}_{-i}(S')$ has balance at most $\max(bg(S_X), \mathrm{pref}_{-i}(S))$ and $bg(S_X) \le \mathrm{pref}_1(S') \le \mathrm{pref}_{-i}(S')$ so $\mathrm{pref}_{-i}(S') \le \mathrm{pref}_{-i}(S)$.

To finish, consider if it exists an $i$ such that $\mathrm{suff}_{-i}(S) < +\infty$. By the existence of a licit subset $X$ with $\delta(X) < 0$ and of $\mathrm{Suff}_{-i}(S)$, we have the existence of a mixed maximum independent set in $G$. As $S$ is simple, it does reach this minimal balance, and there is $\rho \subseteq S$ such that $\delta(\rho) = |L| - \alpha(G)$, the lowest possible value for $\delta$. A useful consequence is that we must have $X \subseteq \rho$, as otherwise, $\delta(X \cap \rho) \ge 0$ (by definition of lump), and when reshuffling we would obtain $\delta(\rho \cup X) = \delta(\rho) + \delta(X) - \delta(X \cap \rho) \le \delta(\rho) - 1$, which is not possible by minimality of $\delta(\rho)$ over licit subsets. As a consequence $\forall i, \mathrm{Suff}_{-i}(S') = \mathrm{Suff}_{-i}(S)$ and $\mathrm{suff}_{-i}(S') = \mathrm{suff}_{-i}(S)$.

Overall, $S' = S_X \cdot S \setminus X$ is indeed preferable to $S$. Note also that if $bg(S_X) < \mathrm{pref}_1(S)$, then $\mathrm{pref}_1(S') < \mathrm{pref}_1(S)$, and if $|X| < |\mathrm{Pref}_1(S)|$, then $\ell_{S'}(-1) < \ell_S(-1)$: in both cases, $S'$ is strictly preferable to $S$.

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

Lemma 4 is akin to the “commitment lemma” of [27] and Lemma 4.6 of [28]. However, in this paper, we link this result to newly-introduced notions of preferability (Definition 3) and canonicity (Definition 4). This is the case in particular of Lemma 6. It relies itself on the following existence result for lumps, essentially saying that a balanced licit set can always be reduced to a lump.
compensated by the addition of $r$, for any prefix $P = S[0..i]$ of $S$, the balance $\delta(P)$ is
exactly the number of intervals intersecting position $i$. By assumption, we therefore
have $\delta(P) \le \rho$, so $S$ is a range-$\rho$ schedule.

☐

**Beyond the perfect-matching case**

We have proven so far a parameterized equivalence between DIRECTED PATH-
WIDTH and BISR restricted to bipartite graphs with perfect matchings. With
the goal of proving a more general equivalence result (Theorem 4), we show
that the restriction to graphs with perfect matchings can actually be lifted.

In the case where $G$ does not allow for a perfect matching, we use the
following construction of a graph $G'$ with perfect matching $M'$, denoted the
extension of graph $G$. Let $M$ be a maximum matching of $G$, and $U$ be the
set of uncovered vertices of $G$. We add sets $N_L, N_R$ of vertices to $L$ and $R$
respectively with one vertex $r_u \in N_R$ for each $u \in L \cap U$ and one vertex $l_u \in N_L$
for each $u \in R \cap U$. We further add all edges $(l, r)$ where $l \in N_L$ and $r \in R$,
or $l \in L \cup N_L$ and $r \in N_r$. We further extend the matching $M$ into $M'$ with
all edges of the form $(u, r_u)$ or $(l_u, u)$ for $u \in U: M'$ is now a perfect matching
since the additional edges cover each vertex in $U \cup N_L \cup N_R$ exactly once.

**Proposition 6** A bipartite graph $G$ has a range-$\rho$ schedule if and only if its extension $G'$ has a range-$\rho$ schedule.

*Proof* We first use König's Theorem to relate the various set sizes. First in $G'$,
$\alpha(G') = |M'| = |M| + |U|$. Then in $G$, $\alpha(G) = M + |U \cap L| + |U \cap R|$, so that $\alpha(G') =
\alpha(G)$ on one hand, $\alpha(G') = |L| + |N_L|$ on the other hand, so $|N_L| = \alpha(G) - |L|$.
This translates as follows in terms of budget: a range-$\rho$ schedule for $G$ has budget
$\rho + |L| - \alpha(G) = \rho - |N_L|$. A range-$\rho$ schedule for $G'$ has budget $\rho$.

Let $S$ be any range-$\rho$ schedule of $G$ (in particular $S$ has budget $\rho - |N_L|$ with $\rho \ge |N_L|$), then $S' = N_L \cdot S \cdot N_R$ is a range-$\rho$ schedule for $G'$, with $N_L$ and $N_R$ laid out in any order. Indeed, $S'$ satisfies the precedence constraint, and for any prefix $P'$ of $S'$, we have three possible cases: If $P' \subseteq N_L$, then $\delta(P') \le |N_L| \le \rho$. If $P' = N_L \cdot Q$ with $Q \subseteq S$, then $\delta(P) = |N_L| + \delta(Q) \le |N_L| + bg(S) \le \rho$. Otherwise, $P' = N_L \cdot S \cdot Q$ with $Q \subseteq N_R$, i.e. $\delta(Q) \le 0$, then $\delta(P) = |N_L| + \delta(S) + \delta(Q) \le |N_L| + \delta(S) \le \rho$.

Conversely, because of the all-to-all connectivity between $N_L$ and $R$ and between $L$ and $N_R$, a licit schedule $S'$ for $G'$ needs to have $N_L$ before any vertex from $R$, and have $N_R$ after all vertices from $L$. Without loss of generality, it is therefore of the form $N_L \cdot S \cdot N_R$ with $S$ a schedule of $G$. For any prefix $P$ of $S$, we have $\delta(P) = \delta(P') - |N_L|$ for $P' = N_L \cdot P \subseteq S$, so $\delta(P) \le \rho - |N_L|$ and $S$ is a range-$\rho$ schedule.

☐

**Theorem 4** BISR parameterized by the range $\rho$ is parametrically equivalent to DIRECTED PATHWIDTH parameterized by the target value dpw, with $\rho = \text{dpw} + 1$. In particular, there exists a $O(n^2)$-space, $O(pn^{2\rho})$-time XP algorithm for BISR.
20

**Lemma 5** If $X$ is a licit set with $\delta(X) < 0$, then either $X$ is a lump or there is a lump $Y \subsetneq X$ with $bg(Y) \le bg(X)$.

*Proof* The proof is by induction on $|X|$. Pick $X' \subseteq X$ licit and minimal-by-inclusion under the condition $\delta(X') < 0$. Per the minimality criteria, $X'$ is a lump. If $bg(X') \le bg(X)$, we are done.

If $bg(X') > bg(X)$, consider $S$ an optimal schedule for $X$, and $\rho$ the largest prefix of $S$ such that $\delta(\rho \cap X') = bg(X) + 1$: such a prefix exists, since any schedule of $X'$ (and in particular $S \cap X'$) reaches balance $bg(X) + 1$ at some point. Let also $\sigma$ denote the suffix of $S$ corresponding to $\rho$, i.e. such that $S = \rho \cdot \sigma$. Consider now the set $Y' = \rho \setminus X'$. We have $\delta(\rho) = \delta(Y') + \delta(\rho \cap X') = \delta(Y') + (bg(X) + 1)$ and $\delta(\rho) \le bg(X)$ so $\delta(Y') \le -1$. Overall, $Y' \cup X'$ is a licit set ($= \rho \cup X'$) with balance $\le -2$. In addition, $bg(Y' \cup X') \le bg(X)$ with the schedule $S' = \rho \cdot (\sigma \cap X')$. The definitions of $\rho, X', Y', \sigma$ and their relations to one another are illustrated in Figure 5

Then, $Z = V(\text{Pref}_{-1}(S'))$ yields a licit subset with $\delta(Z) < 0$ and $Z \subsetneq Y' \cup X'$ (as $\delta(Z) = -1$ while $\delta(S') = -2$). Therefore $|Z| < |X|$, and we can apply the induction hypothesis to it: $Z$ is either a lump or contains one. In either case, there is a lump strictly included in $X$. $\square$

**Lemma 6** If $G$ is a bipartite graph for which there exists an optimal schedule $S$ with $\text{pref}_{-1}(S) < +\infty$, then a canonical schedule $S_C$ for $G$ necessarily starts with a harmless lump $X = V(\text{Pref}_{-1}(S_C))$.

*Proof* We first show that $X = V(\text{Pref}_{-1}(S_C))$ is indeed a lump. By Lemma 5, since $X$ is licit and $\delta(X) < 0$, either it is a lump or there exists a lump $Y \subseteq X$ with $|Y| < |X|$ and $bg(Y) \le bg(X) = \text{pref}_{-1}(S_C) \le bg(G)$. Applying Lemma 4 to $S_C$ and $Y$ would yield a schedule strictly preferable to $S_C$, which is not possible. $X$ is therefore indeed a lump.

Finally, $X$ is indeed harmless. Otherwise, there would exist a lump $Y$ such that $bg(Y) < bg(X)$ or $|Y| < |X|$ if $bg(X) = bg(Y)$. By Lemma 4, $S_Y \cdot (S \setminus Y)$, with $S_Y$ an optimal schedule for $Y$ would be strictly preferable to the canonical schedule $S$, which is not possible. $\square$

**Lemma 7** If $X$ is a harmless lump of $G$ with optimal schedule $S_X$, and $S_C$ a canonical schedule for $G \setminus X$, then $S_X \cdot S_C$ is a canonical schedule for $G$

*Proof* Let $S_G$ be a schedule for $G$. We will prove that $S_X \cdot S_C \preceq S_G$.

Let us first apply Corollary 4 to get $S'_G$ simple and preferable to $S_G$. We can then apply Lemma 4 to $S'_G$ and $X$. The only criteria to verify is $bg(S_X) \le \min(\text{pref}_{-1}(S'_G), bg(S'_G))$. Since $X$ is a licit subset with $\delta(X) < 0$, $\alpha(G) \ge |I(X)| \ge |L|$, and since $S'_G$ is simple, $\text{pref}_{-1}(S'_G) < +\infty$. By Lemma 5, there exists a lump $Y$ in $V(\text{Pref}_{-1}(S'_G))$ with $bg(Y) \le \text{pref}_{-1}(S'_G)$. As $X$ is a harmless lump, $bg(S_X) \le$
*Proof* Proposition 6 in fact yields a parameterized reduction from BISR to its input-restricted version on bipartite graphs allowing for a perfect matching. The converse direction is trivial since a restricted version of any parameterized problem trivially reduces to the original problem. This input-restricted version is in turn parametrically equivalent to directed pathwidth by Propositions 4 and 5. Finally, the claimed complexity can be obtained using the known XP algorithm [17] for DIRECTED PATH-WIDTH. □

*Erratum regarding Tamaki Algorithm*

In an earlier version of this manuscript [36], we claimed that the algorithm by Tamaki [37] produces a solution in time $n^{dpw+O(1)}$ for the Directed Pathwidth, even though the paper was acknowledged by the author as being erroneous [30]. However, our “correction” turned out to be equally flawed, so the best known running time for DIRECTED PATHWIDTH is, to our knowledge, $n^{2dpw+O(1)}$. In the absence of an FPT algorithm, finding an algorithm in $n^{dpw+O(1)}$ remains an intriguing open problem. The actual counter-example to our re-implementation can be found in the repository associated with this manuscript, https://github.com/bmarchand/rnabarrier_bisr.

# 4 Algorithms

We now present our algorithms for BIPARTITE INDEPENDENT SET RECONFIGURATION. The first algorithm, parameterized by the range $\rho$, offers a similar complexity as in Theorem 4, and admits specific optimizations in the context of RNA-based instances. The second algorithm exploits the arboricity parameter $\Phi$, and is directly tailored for such applications.

## 4.1 Definitions

### Dividers

In order to provide divide-and-conquer solutions, our goal is to slice schedules into sub-instances. A *divider* is one of the two ways to do so that we propose in this manuscript. It relies on the fact (Lemma 3) that *any* maximum independent set of *G* appears in some optimal BISR solution. In the scheduling formalism, for any set *Z* such that *I*(*Z*) is a maximum independent set, there exists a schedule starting with some permutation of vertices of *Z*: given such a set *Z* (here after called *divider*), an optimal schedule can always be obtained by concatenating optimal schedules for *G*[*Z*] and *G* \ *Z*.

**Definition 3** (Divider) (see Figure 6 for an example) A *divider* *Z* is a subset of *L* ∪ *R* such that *I*(*Z*) is a Maximum Independent Set of *G* (a *divider* is necessarily licit, with $\delta(Z) = |L| - \alpha(G)$). It is a *strict divider* if in addition *I*(*Z*) ∩ *L* ≠ ∅ and *I*(*Z*) ∩ *R* ≠ ∅ (equivalently, *Z* is a *divider* other than ∅ and *L* ∪ *R*).

A schedule is *divided* if it uses a (not-necessarily strict) divider as a prefix. Equivalently, *S* is divided if $\max_{P \subseteq S} |I(P)| = \alpha(G)$.
<figure><img src="image_9.png" /><figcaption>**Fig. 5** Illustration of the objects used in the proof of Lemma 5. The purpose is to show that, given a licit set X such that $\delta(X) < 0$, if it is not a lump itself, a smaller licit set with negative balance $Z \subsetneq X$ can be found. The induction hypothesis can then be applied to Z to show that it contains a lump.</figcaption></figure>

$bg(Y) \leq \text{pref}_1(S'_G) = \min(bg(S'_G), \text{pref}_1(S'_G))$. In addition, if $bg(S_X) = bg(Y)$, we know that $|S_X| \leq |Y|$.

By Lemma 4, $S_X \cdot (S'_G \setminus X) \preceq S'_G \preceq S_G$. Let us know replace $S'_G \setminus X$ by $S_C$, a canonical schedule for $G \setminus X$, and show that we obtain a schedule preferable to $S_X \cdot (S'_G \setminus X)$. We have $\text{Pref}_1(S_X \cdot S_C) = S_X = \text{Pref}_1(S_X \cdot (S'_G \setminus X))$, and $\forall i \in [-2, \dots, |L| - \alpha(G)]$:

$$ \text{Pref}_i(S_X \cdot S_C) = S_X \cdot \text{Pref}_{i+1}(S_C) $$

and

$$ \text{Pref}_i(S_X \cdot (S'_G \setminus X)) = S_X \cdot \text{Pref}_{i+1}(S'_G \setminus X) $$

Given that $S_C$ is canonical for $G \setminus X$, it is preferable to $S'_G \setminus X$. Therefore $\forall i$, $\text{pref}_i(S_C) \leq \text{pref}_i(S'_G \setminus X)$, with $\text{Pref}_i(S_C)$ shorter in case of equality.
## Canonical schedules

Another natural division of the graph occurs when $G$ is disconnected, i.e. it is the disjoint union of two bipartite graphs. However, even in this seemingly easy setting, there is no trivial way to join solutions for each part into a solution for the whole graph: this step is the NP-hard MERGE problem studied in Section 2.3.

One of our central results is that, if the solution of each disconnected subgraph is canonical, i.e. optimal not only for the overall budget but also for additional criteria (defined below), then a canonical solution for $G$ can be obtained in linear time by interleaving fragments of both solutions. The main intuition behind a canonical solution $S$ is that, both in $S$ and $\overleftarrow{S}$, prefixes with negative balance occur before prefixes with the highest positive balance.

Let us introduce some notations and definitions. We write $k_L(G) = \alpha(G) - |L|$. Note that $-k_L(G)$ is a lower-bound for the balance: for any licit set $X \subseteq V(G)$, $\delta(X) \ge -k_L(G)$. For an integer $p$, $0 \le p \le k_L(G)$, we say that a schedule $P$ of some subset of vertices of $V(G)$ is a $p$-sequence if it is licit with $\delta(P) = -p$. We further say that $P$ is an $\infty$-sequence if it is a schedule of $G$, i.e. $V(P) = V(G)$. For a sequence $S$, write $\delta_{min}(S) = \min_{P \subseteq S}(\delta(P))$. Note that $0 \ge \delta_{min}(S) \ge -k_L(G)$, with $\delta_{min}(S) = -k_L(G)$ for divided schedules. For $p \in [0 : \delta_{min}(S)] \cup \{\infty\}$, the $p$-th prefix of $S$, denoted $S^{<p}$, is the shortest prefix of $S$ that is a $p$-sequence (i.e., $\delta(S^{<p}) = -p$ for $p < \infty$, and $S^{<\infty} = S$). Note that $S^{<0}$ is empty, and that successive $p$th prefixes are themselves prefixes of each other. For $0 < i \le j \le -\delta_{min}(S)$, we write $S^{i<j}$ for the slice $S^{<j} \setminus S^{<i-1}$, and $S^{\circ i} = S^{i<j} = S^{<i} \setminus S^{<i-1}$. In particular, $S^{1<i} = S^{<i}$. This extends to $j = \infty$ as follows: $S^{i<\infty} = S \setminus S^{<i-1}$ and $S^{\circ\infty} = S \setminus S^{<\delta_{min}(S)}$.

We say that $G$ is one-sided if $R$ is a maximal independent set ($|R| = \alpha(G)$), otherwise $G$ is two-sided. Note that all schedules in one-sided graphs are divided and satisfy $\delta(S) = \delta_{min}(S) = -k_L(G)$. Note also that when $|L| = \alpha(G)$ and $|L| > |R|$, we have $V(P) = \emptyset$ is a divider. In that case, $G$ is two-sided and $\overleftarrow{G}$ is one-sided.

**Definition 4** (Canonical schedule) A schedule $S$ of a graph $G$ is *canonical* if any of the following applies (see Figure 6 for an example):

* $S$ is *canonical one-sided* if $G$ is one-sided and for any $p \in [1 : k_L(G)] \cup \{\infty\}$ and any licit $p$-sequence $T$, $\text{bg}(S^{<p}) \le \text{bg}(T)$.

* $S$ is *canonical two-sided* if $G$ is two-sided, $S$ is divided and $S = P\overleftarrow{Q}$ with $V(P)$ divider, $P$ is canonical one-sided in $G[P]$ and $Q$ is canonical one-sided in $\overleftarrow{G}[Q]$.

## 4.2 Computing strict dividers

Our first Divide-and-Conquer strategy to the BISR problem (Algorithm 2) relies on the computation of a strict divider $Z$. For convenience and to connect it better with the state of the art, in this part, we use an independent set
22 Parameterized Independent Set Reconfiguration for RNA kinetics

As for $Suff_{-i}(S_X \cdot S_C)$ for any $i \in [-1, \dots, |R|-\alpha(G)]$, we have from the definition of a lump

$$Suff_{-i}(S_X \cdot S_C) = Suff_{-i}(S_C)$$

and

$$Suff_{-i}(S_X \cdot (S'_G \setminus X)) = Suff_{-i}(S'_G \setminus X)$$

As above, since $S_C$ is canonical, $suff_{-i}(S_C) \leq suff_{-i}(S'_G \setminus X)$ with $Suff_{-i}(S_C)$ shorter in case of equality, and the same goes for $S_X \cdot S_C$ and $S_X \cdot (S'_G \setminus X)$.

Finally,

$$ \begin{aligned} bg(S_X \cdot S_C) &= \max(bg(S_X), -1 + bg(S_C)) \\ &\leq \max(bg(S_X), -1 + bg(S'_G \setminus X)) \\ &= bg(S_X \cdot S'_G \setminus X) \end{aligned} $$

Overall, $S_X \cdot S_C \leq S_G$ and is therefore a canonical schedule. □

**Corollary 5** (existence of a canonical solution) There always exists a canonical schedule for a given bipartite graph G

*Proof* Consider S a simple optimal schedule for G. If $pref_{-1}(S) < +\infty$, then $\exists p \subseteq S$ such that $\delta(p) < 0$. By Lemma 5, either p is a lump or it contains a lump X with $bg(X) \leq bg(Y) \leq pref_{-1}(S) \leq bg(S)$. Let us pick X harmless. By Lemma 7 with $S_X$ an optimal schedule for X, and by induction, we get a canonical schedule for G.

If $suff_{-1}(S) < +\infty$, then $pref_{-1}(\overleftarrow{S}) < +\infty$. With the analysis above, we get a canonical schedule for $G_{R \to L}$ which can be reversed into a canonical schedule for G.

If none of the cases above apply, and because S is simple, then necessarily $|L| = |R|$ and G does not allow for any mixed-MIS. In that case, $suff_{-i}(S) = pref_{-i}(S) = +\infty \forall i$ and any optimal schedule is canonical. □

**Lemma 8** Let $(G_1, G_2)$ be two disjoint bipartite graphs and $(S_1, S_2)$ canonical solutions for $(G_1, G_2)$ respectively. If $pref_{-1}(S_1)$, $pref_{-1}(S_2)$, $suff_{-1}(S_1)$ and $suff_{-1}(S_2)$ are all equal to $+\infty$ then both schedules $S_1 \cdot S_2$ and $S_2 \cdot S_1$ are optimal and canonical.

*Proof* First, let us note that $pref_{-1}(S_1) = pref_{-1}(S_2) = suff_{-1}(S_1) = suff_{-1}(S_2) = +\infty$ implies $\delta(G_1) = \delta(G_2) = 0$, by definition of $pref_{-1}$ and $suff_{-1}$.

Then, $G_1$ (resp. $G_2$) cannot allow for a mixed independent set of size $> |L_1| = |R_1|$ (resp. $|L_2| = |R_2|$), as it would imply by Lemma 2 the existence of an optimal schedule with $pref_{-1}(S_1) < +\infty$ (resp, $pref_{-1}(S_2) < +\infty$). As a consequence, The maximum independent sets of G are exactly $L_1 \cup L_2$, $L_1 \cup R_2$, $R_1 \cup L_2$ and $R_1 \cup R_2$.

Both $L_1 \cup R_2$ and $R_1 \cup L_2$ are mixed maximum independent sets. Consider therefore an optimal (and therefore, canonical) schedule S for G. By Lemma 2 both $S_1 \cdot (S \setminus G_1)$ and $S_2 \cdot (S \setminus G_2)$ are preferable to S and canonical. Replacing $S \setminus G_1$ by $S_2$ and $S \setminus G_2$ by $S_1$ does not increase the budget, which is equal to $max(bg(S_1), bg(S_2))$. Since the budget is the only criteria for preferability in this case, both $S_1 \cdot S_2$ and $S_2 \cdot S_1$ are canonical. □
<figure><img src="image_8.png" /><figcaption>**Fig. 6** Top: Schedule $S = P\tilde{Q}$ is canonical on a two-sided graph $G$. In particular, $S$ is optimal with $bg(S) = 2$. Bottom: A schedule that is non-canonical as: i) It does not contain a prefix $P'$ that is a divider of $G$ ($\delta(P) = -k_L(G)$ is not reached); and ii) $S$ violates several prefix and suffix budget constraints, e.g. $T = S'^{\diamond 1}$ has $bg(T) = 2 > bg(P^{\diamond 1})$ and $T' = S'^{\prime \diamond 1}$ has $bg(T') = 3 > bg(Q^{\diamond 1})$. Schedule $S'$ is also not optimal, even though some instances admit schedules that are both optimal and non-canonical.</figcaption></figure>

formulation, that is, we look for a maximum independent set $I$ such that $I \neq L$ and $I \neq R$ (then $Z = I\Delta L$ is a strict divider of $G$).

We present two polynomial-time algorithms for strict dividers. The first runs in $O(\sqrt{|V||E|})$ on any bipartite graph, and is based on folklore knowledge on bipartite independent sets. The second is a custom dynamic programming algorithm running in $O(|V|^2)$, specific to bipartite circle graphs.

## Strict Divider of any bipartite graph

We present here a strategy, based on a decomposition taking place in two rounds. It results into Algorithm 1. The first round is based on the Dulmage-Mendelsohn decomposition of bipartite graphs. It yields a partition of the vertices of $G$ into three sets $D, A, C$, defined as such: for each vertex $v$ of $D$, there exists a maximum matching in which $v$ is not matched, $A = N(D)$ is the union of the neighborhoods of the vertices of $D$, and $C = V \setminus (D \cup A)$ contains the remaining vertices. This decomposition is illustrated on Figure 7. $D, A, C$ verify the following result:

**Theorem 5** (Dulmage-Mendelsohn decomposition, Proposition 2.1 of [38], theorem 3.2.4 of [39]) *Given $G$ bipartite graph and $D, A, C$ defined as above, we have that:*

a. $D$ is the intersection of all maximum independent sets of $G$.

A is the intersection of all minimum vertex covers of $G$.
The following Theorem is the main result of this section, and essentially states that a canonical (and therefore optimal) solution for $G = G_1 \cup G_2$ can be obtained by interleaving canonical solutions for two disjoint graphs $G_1$ and $G_2$. This suggests the merging procedure implemented by Algorithm 1, where $\text{Pref}_-(S_1)$, $\text{Pref}_-(S_2)$, $\text{Suff}_-(S_1)$ and $\text{Suff}_-(S_2)$ are treated as “canonical blocks”, i.e. are not broken up in the interleaving process.

**Theorem 4 (merge algorithm)** If $G_1$ and $G_2$ are two disjoint bipartite graphs and $S_1$ and $S_2$ two canonical solutions for $G_1$ and $G_2$ respectively, then Algorithm 1 yields a canonical solution for $G$ in $O(|S_1| + |S_2|)$.

*Proof Run-time:* Given a schedule $S$, $\text{pref}_-(S)$ and $\text{suff}_-(S)$ and (if they exist) $\text{Pref}_-(S)$, $\text{Suff}_-(S)$ can be computed in $O(|S|)$ by a simple iteration over $S$ that keeps track of the budget.

**Correctness:** We prove the correctness by induction, with the base case being when $S_1 = \emptyset$ or $S_2 = \emptyset$.

In the general case, if $\min(\text{pref}_-(S_1), \text{pref}_-(S_2)) < +\infty$, consider (w.l.o.g) that $(\text{pref}_-(S_1), \ell_{S_1}(-1)) \le_{\text{lex}} (\text{pref}_-(S_2), \ell_{S_2}(-1))$, with $\le_{\text{lex}}$ denoting the lexico-graphic order.

By Lemma 6 applied to $G_1$ and $S_1$, $\text{Pref}_-(S_1)$ is a harmless lump of $G_1$. It is therefore a lump of $G$. Let us prove it is also harmless in $G$. To that end, note that lumps are connected (Property 3), so a lump of $G$ is either a lump of $G_1$ or $G_2$. Therefore $(\text{pref}_-(S_1), \ell_{S_1}(-1)) \le_{\text{lex}} (\text{pref}_-(S_2), \ell_{S_2}(-1))$ indeed implies that $\text{Pref}_-(S_1)$ is of minimal budget among lumps of $G$, and shorter than $\text{Pref}_-(S_2)$ in case of budget equality.

Since by the induction hypothesis $\text{MERGE}(S_1 \setminus \text{Pref}_-(S_1), S_2)$ is canonical, $\text{Pref}_-(S_1) \cdot \text{MERGE}(S_1 \setminus \text{Pref}_-(S_1), S_2)$ is canonical by Lemma 7

The case $\min(\text{suff}_-(S_1), \text{suff}_-(S_2)) < +\infty$ (lines 10-16) is treated with the same arguments, given the symmetry of pref and suff when inverting $L$ and $R$, namely $\forall S \ \text{suff}_-(S) = \text{pref}_-(\overleftarrow{S})$.

As for the justification of the concatenation if none of the conditions above apply, it is brought by Lemma 8. $\square$

# 5 Parameterized algorithms for bipartite independent set reconfiguration

In this section, we apply the technical results of the previous section to the design of XP algorithms for BISR. For example, Lemma 2 is used to formulate a $O(n^2)$-space, $O(n^{2\rho})$-time algorithm for BISR, described in Section 5.1. As for Lemma 4, it allows to build a $O(n^{\Phi+1})$ algorithm for BISR when restricted to *bipartite circle graphs*, described in Section 6. Bipartite circle graphs constitute a sub-case of interest to RNA kinetics, as we shall see in more details in Section 7.
<figure><img src="image_9.png" /><figcaption>**Fig. 7** Illustration of the Dulmage-Mendelsohn (DM) decomposition (Theorem 5) on an example. We use this decomposition in Algorithm 1 to determine whether an input bipartite graph allows for a Strict Divider, i.e. a maximum independent set intersecting both sides of the graph.</figcaption></figure>

- the subgraph $G[C]$ induced by $C$ has a perfect matching, which may be deduced from restricting any maximum matching of $G$ to $C$.

b. In addition, $D$ may be computed from any maximum matching $M$ of $G$ using the following characterization ([38], lemma 2.2): $D = \overline{W}$ where $\overline{W}$ is composed of the vertices left unmatched by $M$, as well as all vertices connected to an unmatched vertex through an alternating path of even length.

This decomposition may allow to conclude in some cases (see Algorithm 1). In general however, a second round of decomposition is needed. In this second round, the set $C$, which allows for a perfect matching $M$, is further decomposed into *elementary sub-graphs* (see Section 4.1 of Lovász and Plummer [39], Theorem 4.1.1 and Exercise 4.1.5, and [40]). It consists in computing the strongly connected components of a directed graph $H(M, C)$ associated to $M$ and $C$ (same construction as in Section 3.3). The vertices of $H$ are the edges of the matching, and $(l, r) \to (l', r')$ iff $l$ is connected to $r'$ in $C$. The strongly connected components of $H$ constitute a decomposition of $G$ into elementary sub-graphs. A bipartite graph is elementary iff the sides $L, R$ are the only minimum vertex covers/maximum independent sets [39](theorem 4.1.1). If it is not elementary, then a strict divider set may be obtained by ordering the elementary sub-graphs $\{(L_i, R_i)\}_{1 \le i \le p}$ along a topological order induced by $H(C, M)$. Any set of the form $(\cup_{i \le t} R_i) \cup (\cup_{i > t} L_i)$ for some $t > 1$ is then a strict divider of $C$.

Note that with above discussion, Algorithm 1 time complexity is dominated by the computation of the maximum matching in $O(\sqrt{|V||E|})$.

## Optimizations for bipartite circle graphs

Despite the relative efficiency of Algorithm 1, computing a strict divider for a large number of successive subproblems remains the bottleneck of our algorithm. In this section we present an alternative algorithm tailored to bipartite circle graphs.
**Algorithm 1** Merge procedure for canonical schedules. $\leq_{lex}$ denotes the lexicographic order, applied here to couples of integers.

**Input:** $S_1, S_2$ canonical solutions for $G_1, G_2$ (disjoint graphs)

**Output:** a canonical solution $S$ for $G = G_1 \cup G_2$

1. **function MERGE($S_1, S_2$):**

2. ▷ If first or last canonical blocks exist: **recurse**

3. **if** $\min(\text{pref}_1(S_1), \text{pref}_1(S_2)) < +\infty$ **then**

4. **if** $(\text{pref}_1(S_1), \ell_{S_1}(-1)) \leq_{lex} (\text{pref}_1(S_2), \ell_{S_2}(-1))$ **then**

5. **return** $\text{Pref}_1(S_1) \cdot \text{MERGE}(S_1 \setminus \text{Pref}_1(S), S_2)$

6. **else**

7. **return** $\text{Pref}_1(S_2) \cdot \text{MERGE}(S_1, S_2 \setminus \text{Pref}_1(S_2))$

8. **end if**

9. **end if**

10. **if** $\min(\text{suff}_1(S_1), \text{suff}_1(S_2)) < +\infty$ **then**

11. **if** $(\text{suff}_1(S_1), r_{S_1}(-1)) \leq_{lex} (\text{suff}_1(S_2), r_{S_2}(-1))$ **then**

12. **return** $\text{MERGE}(S_1 \setminus \text{Suff}_1(S_1), S_2) \cdot \text{Suff}_1(S_1)$

13. **else**

14. **return** $\text{MERGE}(S_1, S_2 \setminus \text{Suff}_1(S_2)) \cdot \text{Suff}_1(S_2)$

15. **end if**

16. **end if**

17. ▷ If no first or last canonical block exist: **simply concatenate**

18. **return** $S_1 \cdot S_2$

19. **end function**

## 5.1 An XP algorithm in $\rho$

Lemma 2 allows for a divide-and-conquer approach: if we identify a separator $X$ in $G$, i.e. a licit subset of $G$ such that $I(X)$ is a mixed independent set, then we may independently solve the problem of finding a $\rho$-realization from $L$ to $I(X)$ and then from $I(X)$ to $R$. If no solution is found for one of them, then the converse of Lemma 2 implies that no $\rho$-realizations exists for $G$. The algorithm presented in this section is based on this approach.

**Algorithm details.** We present here a direct algorithm for BIPARTITE INDEPENDENT SET RECONFIGURATION, detailed in Algorithm 2. The main function **Realize** is recursive. Its sub-calls arise either from a split with a mixed MIS $I$ (in which case it is called on a smaller graph but with the same parameter), or from the loop over all possible starting points in the case where no separator is found (lines 13-18), in which case the parameter does reduce. The overall runtime is dominated by this loop, and is analyzed in Proposition 5 below.

**Mixed MIS algorithm.** The sub-routine allowing to find, if it exists, a maximum independent set intersecting both $L$ and $R$ is based on concepts from matching theory [29], namely the Dulmage-Mendelsohn decomposition [29, 30], as well as the decomposition of bipartite graphs with a perfect matching into elementary subgraphs [29](part 4.1). Its full details are described in the full version of the article.
**Algorithm 1 Strict Divider**

**Input:** A bipartite graph $G$ with sides $L$ and $R$. We suppose w.l.o.g that $|L| \ge |R|$.

**Output:** If it exists, a strict divider $Z$ of $G$.

1. **function** Strict Maximum Independent Set($G$):

2. $M = \text{Maximum Matching}(G)$

$\triangleright \mathcal{O}(\sqrt{|V|} \cdot |E|)$

3. $D, A, C = \text{Coarse Dulmage Mendelsohn}(M, G)$

$\triangleright \mathcal{O}(|E|)$

4. **if** $|L| > |R|$ **then**

5. **if** $R \setminus A \neq \emptyset$ **then**

6. $\triangleright//A$ is the intersection of all minimum vertex covers

7. pick $r \in R \setminus A$

8. $G' = G \setminus \{r \cup N(r)\}$

9. $M' = \text{Maximum Matching}(G')$

10. $I' = \text{Maximum Independent Set}(G', M')$

11. **return** $I' \cup \{r\}$

12. **else**

13. **return** $\perp$

$\triangleright$ // Not possible, $\emptyset$ is the only divider

14. **else if** $|L| = |R|$ **then**

15. $\{(L_i, R_i)\}_{1 \le i \le p} = \text{Fine Dulmage Mendelsohn}(M, C)$

$\triangleright \mathcal{O}(|V|^2)$

16. **if** $p=1$ **then**

17. **return** $\perp$

18. **else**

19. $s=\text{TOPOLOGICAL SORT}(\{(L_i, R_i)\})$

$\triangleright \mathcal{O}(|V| + |E|)$

20. $(L_i, R_i) = s[0]$

$\triangleright$ // first in topological sort

21. **return** $R_i \cup (\cup_{j \neq i} L_j)$

22. **function** Strict Divider($G$):

23. $I \leftarrow \text{Strict Maximum Independent Set}(G)$

24. **if** $I = \perp$ **then**

25. **return** $\perp$

26. **else**

27. **return** $L \Delta I$

On bipartite circle graphs, given a strict divider $Z$, the maximum independent set $I(Z)$ of $G = (L \cup R, E)$ is a maximum conflict-free subset of $L \cup R$ (where conflicting pairs are properly overlapping intervals), containing at least a base pair from $L$ and $R$. As is the case for many algorithmic problems involving RNA, the fact that base pairs define intervals suggests a dynamic programming approach, where subproblems are defined for arcs that can be drawn on the bipartite circle graph (i.e., intervals of $[1:n]$, where $n = 2|V|$ denotes the number of chord endpoints in an embedding of the bipartite circle graph). Let us start with a simple dynamic programming scheme allowing to compute an unconstrained maximum independent set.

A maximum conflict-free subset of $L \cup R$ can be computed by dynamic programming, using the following DP table: for each $1 \le i \le j \le n$, let $\text{MCF}_{i,j}$
**Algorithm 2** XP algorithm for BIPARTITE INDEPENDENT SET RECONFIGURATION

**Input:** bipartite graph $G$ (with sides $L$ and $R$), integer $\rho$

**Output:** a $\rho$-realization for $G$, if it exists

1: function **REALIZE**($G, \rho$):

2:

3: if $\rho < 0$ then return $\perp$

▷ // Terminal cases:

4: end if

5: if $L \cup R = \emptyset$ then return $\emptyset$

6: end if

7: if $\exists \ell \in L \text{ s.t } N(\ell) = \emptyset$ then return **REALIZE**($G \setminus \{\ell\}, \rho - 1) \cdot \ell$

8: end if

9: if $\exists r \in R \text{ s.t } N(r) = \emptyset$ then return $r \cdot \text{REALIZE}(G \setminus \{r\}, \rho - 1)$

10: end if

11:

12: $I = \text{MIXEDMIS}(G)$

▷ // Trying to find a separator

13: if $I \neq \perp$ then

14: $S = (L \setminus I) \cup (R \cap I)$

15: return **REALIZE**($G[S], \rho) \cdot \text{REALIZE}(G[V \setminus S], \rho)$

16: else

17: for $(\ell, r) \in L \times R$ do

▷ // loop over all start-end possibilities

18: if **REALIZE**($G \setminus \{\ell, r\}, \rho - 1) \neq \perp$ then

19: return $\ell \cdot \text{REALIZE}(G \setminus \{\ell, r\}, \rho - 1) \cdot r$

20: end if

21: end for

22: end if

23: end function

**Proposition 5** *Algorithm 2 runs in $O(|V|^{2\rho}\sqrt{|V||E|})$ time, while using $O(|V|^2)$ space, where $\rho$ is the difference between the minimum allowed and maximum possible independent set size, along the reconfiguration.*

*Proof* Let us start with space: throughout the algorithm, one needs only to maintain a description of $G$ and related objects (independent set $I$, maximum matching $M$, associated directed graph $H(G, M)$) for which $O(|V|^2)$ is enough.

As for time, let $C(n_1, n_2, \rho)$ be the number of recursive calls of the function **Realize** of Algorithm 2 when initially called with $|L| = n_1, |R| = n_2$, and some value of $\rho$. We will show by induction that $C(n_1, n_2, \rho) \le (n_1 + n_2)^{2\rho}$. Since each call involves one computation of a maximum matching, this will prove our result.

Given $(n_1, n_2, \rho)$, suppose therefore that $\forall (n'_1, n'_2, \rho') \ne (n_1, n_2, \rho)$ with $n'_1 \le n_1, n'_2 \le n_2, \rho' \le \rho$ we have $C(n'_1, n'_2, \rho') < (n'_1 + n'_2)^{2\rho'}$

1. If $G$ allows for a mixed maximum independent set, the instance is split into two smaller instances, yielding $C(n_1, n_2, \rho) = C(n'_1, n'_2, \rho) +$
(for maximum conflict-free) be the size of a maximum independent subset of all base pairs included in $[i : j]$.

**Lemma 1** MCF$_{1,n}$ can be computed in $O(n^2)$ time

*Proof* The main observation is that if a maximum independent set included in $[i : j]$ contains a pair of the form $(i, k)$, then all other pairs are either included in $[i+1, k-1]$ or $[k+1, j]$ (since otherwise those two pairs would form a conflict). This leads to the following recurrence formula:

$MCF_{i,j} = 0 \quad \text{if } j \le i$, else:

$$MCF_{i,j} = \max \begin{cases} MCF_{i+1,j} \\ \max_{\substack{(i,k) \in L \cup R \\ \text{such that } k \le j}} 1 + MCF_{i+1,k-1} + MCF_{k+1,j} \end{cases}$$

Note that the last $\max$ is over at most two possible pairs $(i, k)$ (1 from $L$ and 1 from $R$), per the fact that $L$ and $R$ are both independent. $\square$

We then need to obtain strict dividers of $G$: we thus apply the following modifications to the DP scheme above while retaining the same complexity. In addition to the interval, we index the table by two booleans, $\alpha$ and $\beta$ which, when true, further restrict the optimization to subsets with at least one pair from $L$ (iff $\alpha = \text{True}$) or $R$ (iff $\beta = \text{True}$):

$$MCF_{i,j}^{\alpha, \beta} = \begin{cases} 0 & \text{if } (\alpha, \beta) = (\text{False}, \text{False}) \\ -\infty & \text{otherwise} \end{cases} \quad \text{if } i \ge j, \text{ else:}$$

$$MCF_{i,j}^{\alpha, \beta} = \max \begin{cases} MCF_{i+1,j}^{\alpha, \beta} \\ \max_{\substack{(i,k) \in E \\ \alpha', \alpha'', \beta', \beta'' \in \mathbb{B}^4 \\ \text{s.t. } \alpha \Rightarrow \alpha' \lor \alpha'' \lor ((i,k) \in L) \\ \text{and } \beta \Rightarrow \beta' \lor \beta'' \lor ((i,k) \in R)}} 1 + MCF_{i+1,k-1}^{\alpha', \beta'} + MCF_{k+1,j}^{\alpha'', \beta''} \end{cases}$$

Through a suitable memorization, the system can be used to compute in $O(n^2)$ the maximum cardinality $MCF_{1,n}^{\text{True, True}}$ of a subset over the whole sequence. A backtracking procedure is then used to rebuild the maximal subset.

## 4.3 Divider-Schedule: An XP algorithm in $\rho$

We present here an XP algorithm in $\rho$ for BIPARTITE INDEPENDENT SET RECONFIGURATION, Divider-Schedule.

The algorithm is based on a divide-and-conquer approach: if we identify a strict divider $Z$ in $G$, then we may independently solve the problem of finding a range-$\rho$ schedule in two subinstances, one from $L \cap Z$ to $R \cap Z$ and one from $L \setminus Z$ to $R \setminus Z$. Correctness follows from Lemma 4 (Section 5.1), that shows that if any solution exists, then one is found with any strict divider $Z$. When no strict divider is available, then it can be seen that the whole schedule always
$C(n'_1, n''_2, \rho)$ with $n'_1 + n''_1 = n_1$ and $n_2 = n'_2 + n''_2$. And $C(n_1, n_2, \rho) \le ((n'_1 + n''_2)^{2\rho} + (n'_1 + n''_2)^{2\rho}) \le (n'_1 + n''_1 + n'_2 + n''_2)^{2\rho} \le (n_1 + n_2)^{2\rho}$.

2. else, we have the following relation: $C(n_1, n_2, \rho) = n_1n_2 \cdot C(n_1-1, n_2-1, \rho-1)$. Which yields:

$$ \begin{aligned} C(n_1, n_2, \rho) &= n_1n_2 \cdot C(n_1-1, n_2-1, \rho-1) \\ &\le n^2 \cdot n^{2(\rho-1)} \quad \text{by induction hypothesis} \\ &\le n^{2\rho} \end{aligned} $$

□

The exponential part ($O(n^{2\rho})$) of the worst case complexity of Algorithm 2 is in fact tight, as it is met with a complete bi-clique $K_{n,n}$ with sides of size $n$. Indeed, in this case, no mixed MIS is found in any of the recursive calls.

# 6 RNA case: bipartite circle graphs

## 6.1 RNA basics and arboricity parameter

**RNA structures.** RiboNucleic Acids (RNAs) are biomolecules of outstanding interest for molecular biology, which can be represented as strings over an alphabet $\Sigma := \{A, C, G, U\}$. Importantly, these strings may *fold* on themselves to adopt one or several conformation(s), also called *structures*. For a string of length $N$, a conformation is typically described by a set $S$ of base pairs $(i, j)$, with $1 \le i < j \le N$. Then, a standard class of conformations to consider in RNA bioinformatics are *secondary structures*, which are pairwise non-crossing $(\not\in(i, j), (k, l) \in S$ such that $i \le k \le j \le l$, in particular, they involve distinct positions). Due to this non-crossing property, secondary structures are in bijection with *well-parenthesized* strings, as illustrated in Figure 6 (B).

**RNA Energy barrier problem.** In this section, we more precisely work on the problem of finding a reconfiguration pathway between two *secondary structures* (i.e conflict-free sets of base pairs). The reconfiguration may only involve secondary structures, and remain of energy as low as possible. We work with a simple energy model consisting of the opposite of *number of base pairs* in a configuration $(-N_{bps})$. The RNA ENERGY-BARRIER problem can then be stated as such:

**RNA ENERGY-BARRIER**

**Input:** Secondary structures $L$ and $R$; Energy barrier $k \in \mathbb{N}^+$

**Output:** True if there exists a sequence $S_0 \cdots S_\ell$ of secondary structures such that

* $S_0 = L$ and $S_\ell = R$;

* $|S_i| \ge |L| - k, \forall i \in [0, \ell]$;

* $|S_i \triangle S_{i+1}| = 1, \forall i \in [0, \ell - 1]$.

False otherwise.
has a balance between 1 and $\rho$ (except at the very beginning and very end), effectively reducing the range of the balance to $\rho - 1$: in this case a recursive call with smaller range can be performed, but one needs to first enumerate all possible starting points for the overall schedule (lines 12-14 of Algorithm 2).

**Algorithm 2** Divider-Schedule for BIPARTITE INDEPENDENT SET RECONFIGURATION

**Input:** A bipartite graph $G$ (with sides $L$ and $R$), integer $\rho$

**Output:** A range-$\rho$ schedule for $G$, if it exists

1. **function** DIVIDER-SCHEDULE($G, \rho$):

2. &nbsp;&nbsp;&nbsp;&nbsp;**if** $\rho < 0$ **then** return $\perp$

3. &nbsp;&nbsp;&nbsp;&nbsp;**if** $L \cup R = \emptyset$ **then** return $\emptyset$

4. &nbsp;&nbsp;&nbsp;&nbsp;**if** $\exists l \in L$ s.t $N(l) = \emptyset$ **then** return Divider-Schedule($G \setminus \{l\}, \rho - 1) \cdot l$

5. &nbsp;&nbsp;&nbsp;&nbsp;**if** $\exists r \in R$ s.t $N(r) = \emptyset$ **then** return $r \cdot \text{ Divider-Schedule}(G \setminus \{r\}, \rho - 1)$

6. &nbsp;&nbsp;&nbsp;&nbsp;$I = \text{STRICTMAXIMUMINDEPENDENTSET}(G)$

7. &nbsp;&nbsp;&nbsp;&nbsp;**if** $I \neq \perp$ **then**

8. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$Z = (L \setminus I) \cup (R \cap I)$ &nbsp;&nbsp;&nbsp;&nbsp;▷ Retrieve explicitly the divider

9. &nbsp;&nbsp;&nbsp;&nbsp;**return** Divider-Schedule($G[Z], \rho) \cdot \text{ Divider-Schedule}(G[V \setminus Z], \rho)$

10. &nbsp;&nbsp;&nbsp;&nbsp;▷ Lemma 4

11. &nbsp;&nbsp;&nbsp;&nbsp;**else**

12. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**for** $(l, r) \in L \times R$ **do** &nbsp;&nbsp;&nbsp;&nbsp;▷ Loop over all start-end possibilities

13. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** Divider-Schedule($G \setminus \{l, r\}, \rho - 1) \neq \perp$ **then**

14. &nbsp;&nbsp;&nbsp;&nbsp;**return** $l \cdot \text{ Divider-Schedule}(G \setminus \{l, r\}, \rho - 1) \cdot r$

**Proposition 7** Divider-Schedule (Algorithm 2) runs in $O(|V|^{2\rho} \sqrt{|V|} |E|)$ time (or $O(|V|^{2\rho} |V|^2)$ time for bipartite circle graphs), while using $O(|V|^2)$ space.

*Proof* Let us start with space: throughout the algorithm, one needs only to maintain a description of $G$ and related objects (independent set $I$, maximum matching $M$, associated directed graph $H(G, M)$) for which $O(|V|^2)$ is enough.

As for time, let $C(n_1, n_2, \rho)$ be the number of recursive calls of the function Divider-Schedule of Algorithm 2 when initially called with $|L| = n_1$, $|R| = n_2$, and some value of $\rho$. We will show by induction that $C(n_1, n_2, \rho) \le (n_1 + n_2)^{2\rho}$. Since each call involves one computation of a maximum matching, this will prove our result.

Given $(n_1, n_2, \rho)$, suppose therefore that $\forall(n'_1, n'_2, \rho') \neq (n_1, n_2, \rho)$ with $n'_1 \le n_1, n'_2 \le n_2, \rho' \le \rho$ we have $C(n'_1, n'_2, \rho') < (n'_1 + n'_2)^{2\rho'}$

1. If $G$ allows for a strict divider, the instance is split into two smaller instances, yielding $C(n_1, n_2, \rho) = C(n'_1, n_2, \rho) + C(n''_1, n'_2, \rho)$ with $n'_1 + n''_1 = n_1$ and $n_2 = n'_2 + n''_2$, and

$$C(n_1, n_2, \rho) \le ((n'_1 + n'_2)^{2\rho} + (n''_1 + n''_2)^{2\rho}) \\ \le (n'_1 + n''_1 + n'_2 + n''_2)^{2\rho} \le (n_1 + n_2)^{2\rho}.$$
**Problem motivation.** Since the number of secondary structures available to a given RNA grows exponentially with *n*, RNA energy landscapes are noto- riously *rugged*, i.e. feature many local minima, and the folding process of an RNA from its *synthesis* to its theoretical final state (a thermodynamic equi- librium around low energy conformations) can be significantly slowed down. Consequently, some RNAs end up being degraded before reaching this final state. This observation motivates the study of RNA kinetics, which encompass all time-dependent aspects of the folding process. In particular, it is known (Arrhenius law) that the energy barrier is the dominant factor influencing the transition rate between two structures, with an exponential dependence.

**BISR on circle graphs.** Two arcs $(i, j)$ and $(k, l)$ are said to be in *conflict* or *crossing* if $i \le k \le j \le l$ or $k \le i \le l \le j$ (i.e. when there is not one of them nested in the other). It simply means that they cannot be both present at the same time in an RNA secondary structure.

To capture this constraint in reconfiguring RNA secondary structures, we define the *conflict graph* $G(L, R)$ as having $L \cup R$ as vertices, and an edge connecting two arcs if they are in conflict. $L$ and $R$ being two valid secondary structures, the graph is bipartite. More generally, a valid secondary structure is then an *independent set* of $G(L, R)$. Reconfiguring $L$ into $R$ while minimizing energy along the way then consists in solving BISR on $G(L, R)$. The following proposition characterizes the set of bipartite graphs that emerge from this construction, as *bipartite circle graph*. A circle graph is an intersection-graph of chords of a circle.

**Proposition 6** *The RNA ENERGY BARRIER problem as defined above is BISR restricted to bipartite circle graphs*

*Proof* Given $L$ and $R$ two well-nested arc sets (i.e. two RNA secondary structures) over $[1...n]$, denoted $L = \{(l_i, r_i)\}$ and $R = \{b_j, e_j\}$. Consider a circle with $n$ regularly-spaced positions on it, and the set of chords $L \cup R$. The associated circle graph (chord-intersection graph) is exactly the conflict-graph $G(L, R)$. There is then an exact correspondance between independent sets of $G(L, R)$ and valid secondary structures composed of arcs from $L$ and $R$.

Conversely, given a bipartite circle graph, its two sides $L$ and $R$ yield two well-nested arc sets that can be seen as RNA secondary structures. The correspondance is highlighted on Figure 6. □

**Notations for base-pair relations.** Given two base-pairs $(i, j)$ and $(k, l)$, we write $(k, l) \subset (i, j)$ if $(k, l)$ is *nested* in $(i, j)$, i.e. if $i < k < l < j$. One may see this notation as “the interval $[k, l]$ is a proper subset of the interval $[i, j]$”. For two non-conflicting base-pairs, if no one of them is nested in the other, we write $(i, j) \parallel (k, l)$, which means either $i < j < k < l$ or $k < l < i < j$.

**Arboricity ($\Phi$).** Given an RNA secondary structure $S$ (a set of well-nested base-pairs) the arboricity $\Phi$ of $S$ is the number of “terminal” base-pairs, i.e.
2. Otherwise, we have the following relation: $C(n_1, n_2, \rho) = n_1 n_2 \cdot C(n_1 - 1, n_2 - 1, \rho - 1)$. Which yields:

$$ 
\begin{aligned}
C(n_1, n_2, \rho) &= n_1 n_2 \cdot C(n_1 - 1, n_2 - 1, \rho - 1) \\
&\le n^2 \cdot n^{2(\rho-1)} \quad \text{by induction hypothesis} \\
&\le n^{2\rho}
\end{aligned}
$$

As the more costly operation is the maximum independent set computation in $O(\sqrt{|V||E|})$ time in general and in $O(|V|^2)$ time for bipartite circle graph according to Section 4.2, we obtain the complexity result. □

**Remark 1** The exponential part ($O(n^{2\rho})$) of the worst-case complexity of Algorithm 2 is in fact tight, as it is met with a complete bi-clique $K_{n,n}$ with sides of size $n$. Indeed, in this case, no strict divider is found in any of the recursive calls.

## 4.4 Canonical Merge: A linear algorithm for merging canonical schedules

Even though the MERGE problem is NP-hard in general (as seen in part 2.3) we obtain a polynomial-time algorithm restricted to canonical input sequences, that further produces canonical solutions. This algorithm is described in Canonical Merge (Algorithm 3) and proven to be linear in Theorem 8. See Figure 8 for an illustration. For the correctness, the fact that such a merge returns a canonical solution is, to our knowledge, challenging to prove and is stated in Theorem 7 (Section 5.6). The main intuition is that an optimal solution can always be edited into a canonical one that uses slices from both input sub-solutions. Thus, it suffices to recursively select the first slice as the one with lowest budget (and similarly in the two-sided case, select the last slice with lowest budget).

**Proposition 8** *Canonical Merge (Algorithm 3) terminates in time $O(|C_1| + |C_2|)$.*

*Proof* Given $i \in \{1, 2\}$, $bg(C_i^{\downarrow 1})$, $bg(\overleftarrow{C_i}^{\downarrow 1})$ and (if they exist) $C_i^{\downarrow 1}$, $\overleftarrow{C_i}^{\downarrow 1}$ can be computed in $O(|C_i|)$ (time and space) by an iteration over $C_i$ that keeps track of the budget. Note that these values need to be recorded for successive recursive calls to obtain a linear running time. □

## 4.5 Subtree-Schedule: An XP algo in $\Phi$ for circle graphs

We present here an XP algorithm in the arboricity parameter $\Phi$ for BIPARTITE INDEPENDENT SET RECONFIGURATION (Algorithm 4), for BISR restricted to bipartite circle graphs, that we denote Subtree-Schedule.

The Divide-and-Conquer strategy is sketched in Figure 9. A schedule is sliced into two sub-instances delimiting distinct “inside” and “outside” around
<figure><img src="image_10.png" /><figcaption>**Fig. 6** Conflict bipartite graph (D) associated with an instance of the RNA ENERGY-BARRIER problem, consisting of an initial (A) and final (B) structure, both represented as an arc-annotated sequence (C). The sequence of valid secondary structures, achieving minimum energy barrier can be obtained from the solution given in Figure 6.</figcaption></figure>

the number of base-pairs that do not contain any nested base-pair. A formal definition is given below:

**Definition 6** The arboricity $\Phi(S)$ of a set of well-nested base-pairs is:

$$ \Phi(S) = |\{(i, j) \in S \mid \nexists(k, l) \in S \text{ with } (k, l) \subset (i, j)\}| $$

When seeing an RNA secondary structure as a set of well-parenthesized strings (Figure 6.A for instance), it is the number of matching opening/closing parenthesis symbols that only have dots between them.

**Separating inside and outside sub-instances.** Given $L$ and $R$ two well-nested arc sets, and $\ell = (i, j)$ an element of $L$. $\ell$ defines naturally “inside” and “outside” sub-instances in $L$ and $R$, that are only connected through $N(\ell)$, the elements of $R$ in conflict with $\ell$. Formally these “inside” and “outside” sub-instances are $(L_{\text{IN}}^{\ell}, R_{\text{IN}}^{\ell})$ and $(L_{\text{OUT}}^{\ell}, R_{\text{OUT}}^{\ell})$ with $L_{\text{IN}}^{\ell} = \{\ell' \in L \mid \ell' \subset \ell\}$, $R_{\text{IN}}^{\ell} = \{\ell' \in R \mid \ell' \subset \ell\}$, $L_{\text{OUT}}^{\ell} = \{\ell' \in L \mid \ell \subset \ell' \text{ or } \ell \parallel \ell'\}$ and $R_{\text{OUT}}^{\ell} = \{\ell' \in R \mid \ell \subset \ell' \text{ or } \ell \parallel \ell'\}$ Note that $\{\ell\}, L_{\text{IN}}^{\ell}, L_{\text{OUT}}^{\ell}$ form a partition of $L$, and $N(\ell), R_{\text{IN}}^{\ell}, R_{\text{OUT}}^{\ell}$ form a partition of $R$.

## 6.2 An XP algorithm for $\Phi$

**Dynamic programming table.** The algorithm we present in this Section (Algorithm 3) is based on dynamic programming, using a memorization strategy. There is therefore a table in which solutions to partial instances are stored. Given $L, R$ input secondary structures to the RNA ENERGY BARRIER problem, the indices to this table are sets of the form $\{\ell, \ell_1 \dots \ell_p\}$, with $\ell \in L \cup \{(1, N)\}$ and $\ell_i \in L$, such that $\forall i \ell_i \subset \ell$, and $\forall i \neq j, \ell_i \parallel \ell_j$.
**Algorithm 3** Canonical Merge

**Input:** $C_1, C_2$ canonical solutions for $G_1, G_2$ (disjoint graphs)

**Output:** A canonical solution $S$ for $G = G_1 + G_2$

1. **function** CMERGE($C_1, C_2$):

2. &nbsp;&nbsp;&nbsp;&nbsp;**if** $C_1^{\triangle1} \neq \bot$ or $C_2^{\triangle1} \neq \bot$ **then**

3. &nbsp;&nbsp;&nbsp;&nbsp;**if** $C_2^{\triangle1} = \bot$ or $\text{bg}(C_1^{\triangle1}) \leq \text{bg}(C_2^{\triangle1})$ **then**

4. &nbsp;&nbsp;&nbsp;&nbsp;**return** $C_1^{\triangle1} \cdot \text{CMERGE}(C_1 \setminus C_1^{\triangle1}, C_2)$

5. &nbsp;&nbsp;&nbsp;&nbsp;**else**

6. &nbsp;&nbsp;&nbsp;&nbsp;**return** $C_2^{\triangle1} \cdot \text{CMERGE}(C_1, C_2 \setminus C_2^{\triangle1})$

7. &nbsp;&nbsp;&nbsp;&nbsp;**if** $\overleftarrow{C_1}^{\triangle1} \neq \bot$ or $\overleftarrow{C_2}^{\triangle1} \neq \bot$ **then**

8. &nbsp;&nbsp;&nbsp;&nbsp;**if** $\overleftarrow{C_2}^{\triangle1} = \bot$ or $\text{bg}(\overleftarrow{C_1}^{\triangle1}) \leq \text{bg}(\overleftarrow{C_2}^{\triangle1})$ **then**

9. &nbsp;&nbsp;&nbsp;&nbsp;**return** CMERGE($C_1 \setminus \overleftarrow{C_1}^{\triangle1}, C_2$) $\cdot \overleftarrow{C_1}^{\triangle1}$

10. &nbsp;&nbsp;&nbsp;&nbsp;**else**

11. &nbsp;&nbsp;&nbsp;&nbsp;**return** CMERGE($C_1, C_2 \setminus \overleftarrow{C_2}^{\triangle1}$) $\cdot \overleftarrow{C_2}^{\triangle1}$

12. &nbsp;&nbsp;&nbsp;&nbsp;**return** $C_1 \cdot C_2$ ▷ If no first or last slice exists: concatenate

a vertex $\ell \in L$, such as the embeddings of the sub-instances are only connected through the chords that form $N(\ell)$. Node $\ell$ is assumed to be the last-scheduled node from $L$, so the end of the schedule is $\ell \cdot N(\ell)$ without loss of generality, and the rest of the instance consists of two disjoint subgraphs. This specific node $\ell$ is found through enumeration. The solutions for the two sub-instances are next merged into a single solution. By ensuring the canonical property of the schedule in a bottom-up manner, we are thus able to use the Canonical Merge algorithm (Algorithm 3, Section 4.4) that is linear in time and space.

Given $\ell \in L$, let ($L_{\text{IN}}^{\ell}, R_{\text{IN}}^{\ell}$) and ($L_{\text{OUT}}^{\ell}, R_{\text{OUT}}^{\ell}$) be inside and outside sub-instances (with respect to $\ell$):

$$L_{\text{IN}}^{\ell} := \{\ell' \in L \mid \ell' \subset \ell\},$$

$$R_{\text{IN}}^{\ell} := \{\ell' \in R \mid \ell' \subset \ell\},$$

$$L_{\text{OUT}}^{\ell} := \{\ell' \in L \mid \ell \subset \ell' \text{ or } \ell \parallel \ell'\}, \quad \text{and} \quad R_{\text{OUT}}^{\ell} := \{\ell' \in R \mid \ell \subset \ell' \text{ or } \ell \parallel \ell'\}.$$

Note that $\{\ell\}, L_{\text{IN}}^{\ell}, L_{\text{OUT}}^{\ell}$ form a partition of $L$, and $N(\ell), R_{\text{IN}}^{\ell}, R_{\text{OUT}}^{\ell}$ form a partition of $R$, and there is no edge between $L_{\text{IN}}^{\ell} \cup R_{\text{IN}}^{\ell}$ and $L_{\text{OUT}}^{\ell} \cup R_{\text{OUT}}^{\ell}$.

A subtree of $L$ is a set $\{\ell, \ell_1 \dots \ell_p\}$ with $\ell \in L \cup \{(1, N)\}$ and $\ell_i \in L$, such that $\forall i \ell_i \subset \ell$, and $\forall i \neq j, \ell_i \parallel \ell_j$. Note that $(1, N)$ is included as a global pair encompassing all chords of $L$ and is used as a starting point for the recursion. We use $ST(L)$ to denote the set of all subtrees.

We use here a dynamic programming table, in which solutions to partial instances are stored. Indices to the dynamic programming table are subtrees in $ST(L)$, and the partial instance associated to a subtree $\{\ell, \ell_1 \dots \ell_p\}$ is $L', R'$ with

$$L' = L_{\text{IN}}^{\ell} \cap \left[ \bigcap_{1 \le i \le p} L_{\text{OUT}}^{\ell_i} \right] \quad \text{and} \quad R' = R_{\text{IN}}^{\ell} \cap \left[ \bigcap_{1 \le i \le p} R_{\text{OUT}}^{\ell_i} \right].$$
<figure><img src="image_11.png" /><figcaption>**Fig. 7** Illustration of Algorithm 3. Given a sub-instance L, R (bordered by gray ovals, top figure), each $\ell \in L$ is tried (middle figure), yielding two smaller sub-instances corresponding to the outside and inside of $\ell$ (bottom left and right figures). After solving each sub-instance independently, using the DP-table for memorization, a solution is obtained for $(L, R)$ by merging both solutions and appending $\ell$ and all its neighborhood (which were not part of any sub-instance). Here the arboricity is 3 (there are 3 minimal arcs in L), so any border uses at most 4 arcs, giving the upper bound of $\binom{n}{4}$ on the number of sub-instances</figcaption></figure>

The reason $(1, N)$ is a possible value for $\ell$ is that it defines an interval to which partial instances are restricted. Originally, there is no restriction and $\ell = (1, N)$. The partial instance associated to such a set is $L', R'$ with

$L' = L_{\text{IN}}^{\ell} \cap \left[ \bigcap_{1 \le i \le p} L_{\text{OUT}}^{\ell_i} \right]$ and $R' = R_{\text{IN}}^{\ell} \cap \left[ \bigcap_{1 \le i \le p} R_{\text{OUT}}^{\ell_i} \right]$. We also denote these structures by $L(\ell, \ell_1, \dots, \ell_p)$ and $R(\ell, \ell_1, \dots, \ell_p)$.

Informally, seeing L as a tree structure, the arcs $\{\ell, \ell_1, \dots, \ell_p\}$ define a “sub-tree” of L. $\ell$ sets the root of this sub-tree, while $\ell_1, \dots, \ell_p$ cut out some branches. Let us write

$$ST(L) = \{(\ell, \ell_1, \dots, \ell_p) \in (L \cup \{(1, N)\}) \times L^p \mid \forall i \ \ell_i \subset \ell \text{ and } \forall i \neq j \ \ell_i \parallel \ell_j\}$$

for the set of all such “sub-trees”, i.e. the set of all indices to the dynamic programming table.

**Lemma 9** Given an RNA structure L of arboricity $\Phi$, $|ST(L)| = O(\frac{n^{\Phi+1}}{\Phi!})$
<figure><img src="image_10.png" /><figcaption>**Fig. 8** Example of Canonical Merge between two one-sided graphs $G_1$ and $G_2$ with canonical schedules $S_1$ and $S_2$. Prefixes are chosen and scheduled iteratively (thus linearly) from $S_1$ or $S_2$ favoring when possible the one with smallest budget. As can be seen scheduling $S_2^{\circ 1}$ before $S_1^{\circ 1}$ would have been detrimental to the final budget (2 instead of 1). In a more general two-sided case, Canonical Merge handles the suffixes similarly.</figcaption></figure>

We also denote these structures by $L(\ell, \ell_1, \dots, \ell_p)$ and $R(\ell, \ell_1, \dots, \ell_p)$.

**Proposition 9** *The Subtree-Schedule algorithm (Algorithm 4) runs in O($n^{\Phi+3}$) time and O($n^{\Phi+2}$) space.*

*Proof* The initial call to Subtree-Schedule $(L, R)$ corresponds to the sybtree $\ell = (1, N)$ and $\{\ell_1 \dots \ell_p\} = \emptyset$. Then, consider a call of Subtree-Schedule on two structures $L(\ell, \ell_1, \dots, \ell_p)$, $R(\ell, \ell_1, \dots, \ell_p)$ respectively equal to

$$L_{\text{IN}}^{\ell} \cap \left[ \bigcap_{1 \le i \le p} L_{\text{OUT}}^{\ell_i} \right] \quad \text{and} \quad R_{\text{IN}}^{\ell} \cap \left[ \bigcap_{1 \le i \le p} R_{\text{OUT}}^{\ell_i} \right],$$

for $(\ell, \ell_1, \dots, \ell_p) \in \mathcal{ST}(L)$. The recursive calls to the “inside” and “outside” of some $\ell' \in L'$ (line 8) will give rise to the instances corresponding to the elements of $\mathcal{ST}(L)$ $(\ell', \{\ell_i \mid \ell_i \subset \ell'\})$ (inside) and $(\ell, \ell', \{\ell_i \mid \ell_i \parallel \ell'\})$ (outside).
30

Parameterized Independent Set Reconfiguration for RNA kinetics

**Proof** Let us start by noting that in an RNA structure, each arc is either terminal or contains a terminal arc nested in it. The set $\{\ell_i\}_{1\le i\le p}$ being composed of arcs mutually not nested in one another, each of them contains (or is) a different terminal arc. As there are less than $\Phi$ terminal arcs in total, given $\ell$, there are less than $\binom{n}{\Phi}$ possibilities for $\ell_1...\ell_p$. Multiplied by the number of possibilities for $\ell$, we get an upper bound of $(n+1) \cdot \binom{n}{\Phi} = O(\frac{n^{\Phi+1}}{\Phi!})$. □

**Theorem 7** *Algorithm 3 outputs a canonical (and therefore optimal) schedule in time $O(\frac{n^{\Phi+2}}{\Phi!})$.*

**Proof Run-time.** The initial call to SCHEDULE($L, R$) corresponds to the entry $\ell = (1, N)$ and $\{\ell_1...\ell_p\} = \emptyset$. Then, consider a call of SCHEDULE on two structures $L(\ell, \ell_1, ..., \ell_p), R(\ell, \ell_1, ..., \ell_p)$ respectively equal to $L_{\text{IN}}^{\ell} \cap [\bigcap_{1\le i\le p} L_{\text{OUT}}^{\ell_i}]$ and $R_{\text{IN}}^{\ell} \cap [\bigcap_{1\le i\le p} R_{\text{OUT}}^{\ell_i}]$, for $(\ell, \ell_1, ..., \ell_p) \in \text{ST}(L)$. The recursive calls to the “inside” and “outside” of some $\ell' \in L'$ (line 14-15) will give rise to the instances corresponding to the elements of $\text{ST}(L)$ $(\ell', \{\ell_i | \ell_i \subset \ell'\})$ (inside) and $(\ell, \ell', \{\ell_i | \ell_i \parallel \ell'\})$ (outside). By induction, all recursive calls to SCHEDULE are of these forms, and the indices to the memorization table are elements of $\text{ST}(L)$. Conversely, any element $(\ell, \ell_1, ..., \ell_p)$ of $\text{ST}$ sees its corresponding instance $L(\ell, \ell_1, ..., \ell_p), R(\ell, \ell_1, ..., \ell_p)$ emerge in some recursive call (e.g. taking the inside of $\ell$ in the first recursive call and then the outside of $\ell_1...\ell_p$). Their number is smaller than $O(\frac{n^{\Phi+2}}{\Phi!})$ by Lemma 9. Let now we call $c(L, R)$ the computational cost of SCHEDULE($L, R$), and $i(L, R)$ the “internal” cost of SCHEDULE, i.e. of all lines of Algorithm 3 except lines 18-19 (recursive calls). Given $\ell \in L$, we write $L_{\text{IN}}^{\ell}, R_{\text{IN}}^{\ell}$ and $L_{\text{OUT}}^{\ell}, R_{\text{OUT}}^{\ell}$ the sub-instances composed of arcs strictly inside or outside of $\ell$. Then, we have:

$$c(L, R) = i(L, R) + \sum_{\ell \in L} c(L_{\text{IN}}^{\ell}, R_{\text{IN}}^{\ell}) + c(L_{\text{OUT}}^{\ell}, R_{\text{OUT}}^{\ell})$$

Which, by induction, given the discussion above, allows to show that:

$$c(L, R) = \sum_{(\ell, \ell_1, ..., \ell_p) \in \text{ST}(L)} i(L(\ell, \ell_1, ..., \ell_p), R(\ell, \ell_1, ..., \ell_p))$$

$i(L, R)$ is $O(n^2)$ (linear MERGE for each $\ell \in L$), which yields $O(\frac{n^{\Phi+2}}{\Phi!})$ overall.

**Correctness.** By Corollary 5, a canonical schedule $S$ for $G$ exists. Some element $\ell \in L$ is necessarily processed last, such that $S = S' \cdot \ell \cdot N(\ell)$. When $\ell$ is considered as part of the for loop line 17 of Algorithm 1, the candidate solution is $S'' \cdot \ell \cdot N(\ell)$, with $S'' = \text{MERGE}(S_{\text{IN}}, S_{\text{OUT}})$. Sequence $S''$ is canonical by induction and the correctness of MERGE (Theorem 4). Thus, $S'' \ll S'$ and the candidate solution is preferable to $S$, and therefore canonical. □
**Algorithm 4** Subtree-Schedule for CG-BISR

**Input:** A bipartite circle graph $G$ (with sides $L$ and $R$)

**Output:** A canonical schedule for $G$

**Global:** Dyn. prog. table $M: (L, R) \to S$, storing subtree solutions.

1. **if** $(L, R)$ is in $M.keys()$ **then** ▷ If already computed then return;

2. **return** $M[(L, R)];$

3. $M[(L, R)] = L \cdot R$ ▷ Initializing $M[(L, R)]$ with a simple value

4. **if** $\exists r \in R$ such that $N(r) = \emptyset$ **then**

5. $M[(L, R)] = r \cdot \text{Subtree-Schedule}(G \setminus \{r\})$

6. **return** $M[(L, R)]$

7. **for** $\ell$ in $L$ **do** ▷ $\ell$ defines an inside and an outside

8. $S_{IN} = \text{Subtree-Schedule}(G[L_{IN}^{\ell} \cup R_{IN}^{\ell}])$

9. $S_{OUT} = \text{Subtree-Schedule}(G[L_{OUT}^{\ell} \cup R_{OUT}^{\ell}])$

10. $S' = \text{CMERGE}(S_{IN}, S_{OUT}) \cdot \ell \cdot N(\ell)$

11. **if** $\forall p \in [1, \delta_{min}(S')]$, $\text{bg}(S'^{<p}) \le \text{bg}(M[(L, R)]^{<p})$ **and**

12. $\forall p \in [1, \delta_{min}(\overleftarrow{S}')]$, $\text{bg}(\overleftarrow{S'}^{<p}) \le \text{bg}(\overleftarrow{M[(L, R)]}^{<p})$ **then**

13. $M[(L, R)] = S'$ ▷ Memorize canonical schedules

14. **return** $M[(L, R)]$

By induction, all recursive calls to Subtree-Schedule are of these forms, and the indices to the memorization table are elements of $ST(L)$. Moreover, elements $\ell_1, \dots, \ell_p$ are pairwise-parallel, so $p \le \Phi$ (each $\ell_i$ has at least one nested leaf that is not nested under any $\ell_j, j \ne i$). Thus the number of such tuples $(\ell, \ell_1, \dots, \ell_p)$ is $|ST(L)| \le n^{\Phi+1}$.

Let now we call $c(L, R)$ the computational cost of Subtree-Schedule$(L, R)$, and $i(L, R)$ the “internal” cost of Subtree-Schedule, i.e. of all lines of Algorithm 4 except lines 9-10 (recursive calls). Given $\ell \in L$, we write $L_{IN}^{\ell}$, $R_{IN}^{\ell}$ and $L_{OUT}^{\ell}$, $R_{OUT}^{\ell}$ the sub-instances composed of arcs strictly inside or outside of $\ell$. Then, we have:

$$c(L, R) = i(L, R) + \sum_{\ell \in L} c(L_{IN}^{\ell}, R_{IN}^{\ell}) + c(L_{OUT}^{\ell}, R_{OUT}^{\ell})$$

Which, by induction, given the discussion above, allows to show that:

$$c(L, R) = \sum_{(\ell, \ell_1, \dots, \ell_p) \in ST(L)} i(L(\ell, \ell_1, \dots, \ell_p), R(\ell, \ell_1, \dots, \ell_p))$$

The internal cost $i(L, R)$ is in $O(n^2)$ (linear CMERGE for each $\ell \in L$), which yields $O(n^{\Phi+3})$ time overall. In terms of space, we keep the schedule solution (of size $\le n$) for each subtree in $ST(L)$, leading to a $O(n^{\Phi+2})$ space complexity. $\square$

# 5 Correctness proofs and technical lemmata

## 5.1 A division lemma

The correctness of Divider-Schedule, our algorithm XP in $\rho$, follows from the application of a division Lemma 3. It critically uses a submodularity property for the balance functions, which we first establish below.
**Algorithm 3** XP algorithm in $\Phi$ for BIPARTITE INDEPENDENT SET RECONFIGURATION

**Input:** bipartite circle graph $G$ (with sides $L$ and $R$)

**Output:** a canonical schedule for $G$

**Global variable:** Dynamic programming table $M: (L, R) \to S$, storing input/output pairs for SCHEDULE.

1: **function** SCHEDULE($L, R$):

2: &nbsp;&nbsp;&nbsp;&nbsp;**if** ($L, R$) is in $M.keys()$ **then**

>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;▷ If already computed then return;

3: &nbsp;&nbsp;&nbsp;&nbsp;**return** $M[(L, R)];$

4: &nbsp;&nbsp;&nbsp;&nbsp;**end if**

5: &nbsp;&nbsp;&nbsp;&nbsp;**$M[(L, R)] = L \cdot R$**

>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;▷ Initializing $M[(L, R)]$ with a simple value

6: &nbsp;&nbsp;&nbsp;&nbsp;**if** $L = \emptyset$ **then**

7: &nbsp;&nbsp;&nbsp;&nbsp;**return** $M[(L, R)]$

8: &nbsp;&nbsp;&nbsp;&nbsp;**end if**

9: &nbsp;&nbsp;&nbsp;&nbsp;**if** $\exists r \in R$ such that $N(r) = \emptyset$ **then**

10: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**$M[(L, R)] = r \cdot SCHEDULE(L, R \setminus \{r\})$**

11: &nbsp;&nbsp;&nbsp;&nbsp;**return** $M[(L, R)]$

12: &nbsp;&nbsp;&nbsp;&nbsp;**end if**

13: &nbsp;&nbsp;&nbsp;&nbsp;**for** $\ell$ in $L$ **do**

14: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**$S_{IN} = SCHEDULE(L_{IN}, R_{IN})$** ▷ $\ell$ defines an inside and an outside

15: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**$S_{OUT} = SCHEDULE(L_{OUT}, R_{OUT})$**

16: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**$S' = MERGE(S_{IN}, S_{OUT}) \cdot \ell \cdot N(\ell)$**

17: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** $S' \preceq M[(L, R)]$ **then**

>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;▷ If $S'$ is preferable to $M[(L, R)]$

18: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**$M[(L, R)] = S'$**

19: &nbsp;&nbsp;&nbsp;&nbsp;**end if**

20: &nbsp;&nbsp;&nbsp;&nbsp;**end for**

21: &nbsp;&nbsp;&nbsp;&nbsp;**return** $M[(L, R)]$

22: &nbsp;&nbsp;&nbsp;&nbsp;**end function**

# 7 Benchmarks and Applications

In this section, we report benchmark results for all of our algorithms. We first explain some details about the algorithm we implemented for directed pathwidth. Then, we present a general benchmark of Algorithm 2 and the directed pathwidth approach, on random (Erdös-Rényi) bipartite graphs.

Last, we compare Algorithm 3 with the directed pathwidth approach on bipartite circle graphs, i.e. RNA instances.

**Code availability.** The code used for our benchmarks, including a Python/C++ implementation of our two algorithms, is available at https://gitlab.inria.fr/bmarchan/bisr-dpw (Algorithm 2 and directed pathwidth algorithm [27]) and https://gitlab.inria.fr/bmarchan/barrier-subtree (for Algorithm 3).
**Lemma 2** (submodularity) Given licit subsets X and Y, we have that both X ∩ Y and X ∪ Y are licit. Moreover, the corresponding independent sets have the following bounds on their sizes:

$$|I(X)| + |I(Y)| = |I(X \cup Y)| + |I(X \cap Y)|$$

and

$$\delta(X \cup Y) + \delta(X \cap Y) = \delta(X) + \delta(Y).$$

Moreover, if X is a divider of G, then

$$\delta(X \cup Y) \leq \delta(Y) \quad \text{and} \quad \delta(X \cap Y) \leq \delta(Y).$$

*Proof* Let us verify that $I(X \cap Y) = L \setminus (X \cap Y) \cup (R \cap X \cap Y)$ is indeed an independent set. Consider $r \in R$ and suppose $r \in I(X \cap Y)$. Then $r \in R \cap X \cap Y$, and since X is licit, $r \in X \cap R$ implies $N(r) \cap I(X) = \emptyset$ and therefore $N(r) \subset L \cap X$. Likewise, $N(r) \subset L \cap Y$. Therefore $N(r) \subset L \cap X \cap Y$ and $I(X \cap Y)$ does not intersect $N(r)$.

Likewise, consider $\ell \in L$, and suppose $\ell \in I(X \cap Y)$. Then $\ell \in L \setminus (X \cap Y)$, so either $\ell \in L \setminus X$ or $\ell \in L \setminus Y$. Since X and Y are licit, either $N(r) \cap (R \cap X) = \emptyset$ or $N(r) \cap (R \cap Y) = \emptyset$. In any case, $N(\ell) \cap I(X \cap Y) = \emptyset$ and $I(X \cap Y)$ is indeed an independent set.

Let us now check that $I(X \cup Y)$ is also an independent set. In a similar fashion, consider $r \in I(X \cup Y) \cap R$. $r \in R \cap (X \cup Y)$ implies $r \in R \cap X$ or $r \in R \cap Y$, which implies since X and Y are licit $N(r) \cap (L \setminus X) = \emptyset$ or $N(r) \cap (L \setminus Y) = \emptyset$, i.e. $N(r) \subseteq X$ or $N(r) \subseteq Y$. In any case, $N(r) \cap (L \setminus (X \cup Y)) = \emptyset$.

To finish, consider $\ell \in I(X \cup Y) \cap L$. We have $\ell \in L \setminus (X \cup Y)$, so $\ell \notin X$ and $\ell \notin Y$. Since X and Y are licit, $N(\ell) \cap X = \emptyset$ and $N(\ell) \cap Y = \emptyset$, so

$$I(X \cup Y) \cap N(\ell) = R \cap (X \cup Y) \cap N(\ell) = \emptyset$$

and $I(X \cup Y)$ is indeed and independent set. So both sets $X \cap Y$ and $X \cup Y$ are indeed licit, we can now turn to the relation between their independent set sizes.

We have $I(X) = (L \setminus X) \cup (R \cap X)$. Therefore we have

$$|I(X)| = |L \setminus X| + |R \cap X| = |L| - |L \cap X| + |R \cap X|.$$

Furthermore we have

$$|(X \cup Y) \cap L| = |(X \cap L) \cup (Y \cap L)| = |X \cap L| + |Y \cap L| - |X \cap Y \cap L|.$$

and likewise for R. The result stems from a subtraction of one equation to the other, and an addition of $|L|$. The relation between the balances follow from the definition, i.e. $\delta(X) = |L| - |I(X)|$.

Finally, if X is a divider, then $I(X)$ is a maximum independent set, then $|I(X \cap Y)| \geq |I(X)|$ and $|I(X \cup Y)| \geq |I(X)|$, which then respectively yield $\delta(X \cup Y) \leq \delta(Y)$ and $\delta(X \cap Y) \leq \delta(Y)$. $\square$

The correctness of Divider-Schedule is shown by “re-shuffling” a solution into another one starting necessarily with a strict divider. Thus reshuffling is described below, and allows to obtain a simple merge algorithm when a strict divider can be found.

Given a schedule S of G and a set of vertices X, we write $S \cap X$ for the sub-sequence of S consisting of the vertices of X, without changing the order. Likewise, $S \setminus X$ denotes the sub-sequence of S consisting of vertices not in X.
<figure><img src="image_12.png" /><figcaption>**Fig. 8** (top panel) Average run-time (seconds, log-scale) of our algorithms on random Erdös-Rényi bipartite graphs, with a probability of connection such that the average degree of a vertex is 5 (i.e $p = 5/n$). (bottom panel) Average parameter value of generated instances, as a function of input size.</figcaption></figure>

## 7.1 Implementation details

**Directed pathwidth.** We implemented and used an algorithm from Tamaki [1], with a runtime of $O(n^{\rho+2})$. This algorithm was originally published in 2011 [1]. In 2015, H.Tamaki and other authors described this algorithm as “flawed” in [12], and replaced it with another XP algorithm for directed pathwidth, with a run-time of $O(\frac{mn^{2\rho}}{(\rho-1)!})$.

Upon further analysis from our part, and discussions with H. Tamaki and the corresponding author of [12], it appears a small modification allowed to make the algorithm correct. In a nutshell, the algorithm involves pruning actions, and these need to be carried out as soon as they are detected. In [1], temporary solutions were accumulated before a general pruning step. With this modification, the analysis presented in [1] applies without modification, and yields a time complexity of $O(n^{\rho+2})$. The space complexity is unchanged at $O(n^{\rho+1})$. For completeness, a detailed re-derivation of the results of [1] is included in the full version of the article.

**Mixed-MIS algorithm implementation.** On Figure 8, the “m-MIS”-curve, corresponds to our

mixed-MIS-based algorithm in $O(n^{2\rho}\sqrt{|V||E|})$. Compared to the algorithm presented in Algorithm 2, a more efficient rule is used in the non-separable case: we loop over all possible $r \in R$ and add $N(r) \cdot r$ to the schedule (instead of a single vertex $\ell \in L$).

## 7.2 Random bipartite graphs

**Benchmark details.** Figure 8 shows, as a function of the number of vertices, the average execution time of both our algorithms (top panel), as well as the
32 Bipartite IS Reconfiguration: General and RNA-inspired Algorithms

**Definition 5** (Schedule reshuffling) For a schedule $S$ and $X \subseteq V$, the reshuffling of $S$ wrt. set $X$ is the schedule $S' = (S \cap X) \cdot (S \setminus X)$.

**Lemma 3** (Division Lemma) Let $Z$ be a divider of $G$. If $S$ is a licit sequence for $G$, then both $S \cap Z$ and $(S \cap Z) \cdot (S \setminus Z)$ are licit sequences with smaller or equal balance and budget than $S$

*Proof* Write $S' = (S \cap Z) \cdot (S \setminus Z)$. for the reshuffling of $S$ wrt. set $Z$. Consider $P'$ any prefix of $S'$, then there exists a prefix $P$ of $S$ such that:

$$V(P') = V(P) \cap Z \text{ if } P' \subseteq Z$$

$$V(P') = V(P) \cup Z \text{ otherwise } (Z \supset P)$$

In both cases, $V(P')$ is licit by Lemma 2 since $V(P)$ and $Z$ are licit, and moreover $\delta(P') \le \delta(P) \le \text{bg}(S)$ since $Z$ is a divider. So in particular

$$\delta(S \cap Z) \le \delta(S) \qquad (\text{picking } P' = S \cap Z \text{ and } P = S)$$

$$\text{bg}(S \cap Z) \le \text{bg}(S) \qquad (\text{maximizing over all prefixes of } S \cap Z)$$

$$\delta(S') \le \delta(S) \qquad (\text{picking } P' = S' \text{ and } P = S)$$

$$\text{bg}(S') \le \text{bg}(S) \qquad (\text{maximizing over all prefixes of } S')$$

□

Therefore, if $G$ allows for a strict divider, any optimal schedule can be assumed to start with this strict divider, i.e. it is divided. Thus the following corollary immediately follows from Lemma 3.

**Corollary 1** Any graph $G$ has a divided optimal schedule.

**Lemma 4** (Strict Divider Merge) Let $G$ be the union of two disjoint subgraphs $G_1 = L_1 \cup R_1$ and $G_2 = L_2 \cup R_2$ with respective optimal schedules $S_1$ and $S_2$. If $X = L_1 \cup R_1$ is a divider of $G$, then $S_1 \cdot S_2$ is an optimal schedule for $G$.

*Proof* Let $S'$ be the reshuffling of $S$ wrt. set $X$, then by Lemma 3, we have $\text{bg}(S') \le \text{bg}(S)$. Moreover, $S'$ starts with a licit schedule of $G_1$ and ends with a licit schedule of $G_2$, so $\text{bg}(S_1 \cdot S_2) \le \text{bg}(S')$, and $S_1 \cdot S_2$ is also a solution for $G$. □

## 5.2 Correctness of Divider-Schedule

**Theorem 6** *Divider-Schedule (Algorithm 2) is correct and returns a divided schedule.*

*Proof* We show by induction that Divider-Schedule yields an optimal schedule over the graph $G$. The algorithm distinguishes two cases.
<figure><img src="image_13.png" /><figcaption>**Fig. 9** (left) Execution time of Algorithm 3 on pairs of random RNA secondary structures. Points are colored as a function of the smallest arboricity Φ between the two structures. As expected, exact computing the energy barrier between the structures tends to become more expensive for larger values of Φ. (right) Comparison with a scatter plot of the execution times of Algorithm 3 and our implementation of [27] (directed pathwidth algorithm), on random pairs of RNA secondary structures. The color of the points denote the arboricity (Φ) value while the size is the directed pathwidth (range ρ). Surprisingly, the execution time of the directed pathwidth algorithm, whose complexity is $O(n^{ρ+2})$, does not correlate with the value of ρ. It suggests the existence of a structural property of directed graphs emerging from RNA instances making [27] faster.</figcaption></figure>

distribution of parameter values (ρ - bottom panel), on a class of random bipartite graphs. These graphs are generated according to an Erdös-Rényi distribution (each pair of vertices has a constant probability *p* of forming an edge). We use a connection probability of *d*/*n*, dependent on the number of vertices. It is such that the average degree of vertices is *d*. The data of our benchmark (Figure 8) has been generated with *d* = 5.

**Comments on Figure 8.** The difference in trend between the execution times of the two algorithms is quite coherent with the difference in their exponents ($n^{ρ+2}$ vs. $n^{2ρ+2.5}$).

## 7.3 random RNA instances (bipartite circle graphs)

**Benchmark details.** Figure 9 shows the average execution time of Algorithm 3 on random RNA instances, and compares it with the directed pathwidth algorithm (right panel). Random instances are generated according to the following model: two secondary structures *L*, *R* are chosen *uniformly* at random (within the space of all possible secondary structure). Base pairs are constrained to occur between nucleotides separated by a distance of at least $θ = 1$ (left panel) and $θ = 3$ (right panel).

**Random secondary structure generation.** The random RNA secondary structure of Figure 9 are obtained by *uniform sampling* of well-parenthesized strings of a given length *N*. Two parameters control the probability distributions: the minimal distance $θ$ between an opening bracket and its corresponding closing bracket and the probability $p_{pb}$ of being base-paired.
If a strict divider Z is found, we can apply Lemma 3 with a divided optimal schedule S (that always exists thanks to Corollary 1) and divider Z. One can apply Lemma 4 with distinct subgraphs reduced to divider Z (i.e. G[Z]) and G excluding Z (i.e. G \ Z) yielding a correct concatenated schedule by induction.

If no strict divider is found, then $\alpha(G) = \max(|L|, |R|)$. Without loss of generality, an optimal schedule S can be written as $\ell \cdot S' \cdot r$ where $\ell \in L, r \in R$ and $S'$ is optimal in $G \setminus \{l, r\}$. Note that $\alpha(G \setminus \{l, r\}) < \alpha(G)$ since otherwise a maximal independent set in the subgraph would yield a strict divider of G. So $S'$ has range $\rho - 1$. As the enumeration of $\ell$ and $r$ is exhaustive, the algorithm outputs some solution $\ell \cdot S'' \cdot r$ that is optimal since $S''$ is optimal by induction. $\square$

## 5.3 Slices and canonical schedules

The rest of Section 5 is devoted to the correctness proof of algorithms Canonical Merge and Subtree-Schedule. Both proofs use the concept of canonical schedule (itself based on slices) as defined in Section 4.1. We first state some useful properties of both concepts in the subsections below. We then prove two important lemmata in Sections 5.4 and 5.5: respectively, that all graphs admit a canonical schedule (Lemma 8) and that a Merge solution can always be obtained by combining slices from both input canonical solutions (Lemma 18). Finally, we conclude with the final correctness proofs in Section 5.6.

### 5.3.1 Properties of slices

The following proposition and subsequent corollaries are our main tools used to compare slice budgets.

**Proposition 10** Given S with $\delta_{min}(S) = -k$, we have, for any $p \in [1:k] \cup \{\infty\}$, for any prefix P of $S^{\triangle p}$:

$$bg(S^{\triangle p}) = \max(bg(P), bg(S^{\triangle p} \setminus P) + \delta(P))$$

(see Figure 10 for illustration)

*Proof* By definition of the budget:

$$ \begin{align*} bg(S^{\triangle p}) &= \max_{Q \subseteq S^{\triangle p}} \delta(Q) \\ &= \max(\max_{Q \subseteq P \subseteq S^{\triangle p}} \delta(Q), \max_{P \subseteq Q \subseteq S^{\triangle p}} \delta(Q)) \text{ as } Q \text{ and } P \text{ both prefixes of } S^{\triangle p} \\ &= \max(\max_{Q \subseteq P} \delta(Q), \delta(P) + \max_{Q' \subseteq S^{\triangle p} \setminus P} \delta(Q')) \text{ with } \delta \text{ definition} \\ &= \max(bg(P), \delta(P) + bg(S^{\triangle p} \setminus P)) \text{ with bg definition} \end{align*} $$

$\square$

**Corollary 2** Given S with $\delta_{min}(S) = -k$, we have, for any $p \in [1:k] \cup \{\infty\}$, for any $0 < q \le p,$
## 7.4 RNA specific optimizations

**Dynamic Programming and RNA.** Given two secondary structures L and R, a mixed MIS of G(L, R) is a maximum conflict-free subset of L ∪ R, containing at least a base pair from L and R. As is the case for many algorithmic problems involving RNA, the fact that RNAs are strings and that base pairs define intervals suggests a dynamic programming approach to the mixed maximum independent set problem in RNA conflict graphs. Subproblems will correspond to intervals of the RNA string. Let us start with a simple dynamic programming scheme allowing to compute an unconstrained MIS.

**Unconstrained MIS DP scheme.** A maximum conflict-free subset of L ∪ R can be computed by dynamic programming, using the following DP table: for each 1 ≤ i ≤ j ≤ n, let MCF$_{i,j}$ be the size of a maximum conflict-free subset of all base pairs included in [i, j].

**Lemma 10** MCF$_{1,n}$ can be computed in time O(n²)

*Proof* We have the following recurrence formula:

$$MCF_{i,i'} = 0, \forall i' < i$$

$$MCF_{i,j} = \max \left\{ \begin{array}{l} MCF_{i+1,j} \\ \max_{(i,k) \in L \cup R} 1 + MCF_{i+1,k-1} + MCF_{k+1,j} \end{array} \right.$$

Note that the last max is over at most two possible pairs (i, k) (1 from L and 1 from R), per the fact that L and R are both conflict-free. □

**Mixed MIS DP scheme.** The following modifications to the DP scheme above allow to compute a mixed MIS of G(L, R) while retaining the same complexity. In addition to the interval, we index the table by Boolean α and β which, when true, further restricts the optimization to subsets with > 0 pair from L (iff α = True) or R (iff β = True):

$$MCF_{i,i'}^{\alpha, \beta} = \begin{cases} 0 & \text{if } (\alpha, \beta) = (\text{False, False}) \\ -\infty & \text{otherwise} \end{cases}, \forall i' < i$$

$$MCF_{i,j}^{\alpha, \beta} = \max \left\{ \begin{array}{l} MCF_{i+1,j}^{\alpha, \beta} \\ \max_{\substack{i', \alpha', \beta', \beta'' \in \mathbb{B}^4 \\ (i,k) \in E}} (1 + MCF_{i+1,k-1}^{\alpha', \beta'} + MCF_{k+1,j}^{\alpha'', \beta''}) \\ \quad \left| \begin{array}{l} \text{if } \neg \alpha \lor \alpha' \lor \alpha'' \lor ((i,k) \in L) \\ \text{and } \neg \beta \lor \beta' \lor \beta'' \lor ((i,k) \in R) \end{array} \right. \end{array} \right.$$

Through a suitable memorization, the system can be used to compute in O(n²) the maximum cardinality MCF$_{1,n}^{\text{True, True}}$ of a subset over the whole sequence. A backtracking procedure is then used to rebuild the maximal subset.

## 8 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 ρ of possible
<figure><img src="image_11.png" /><figcaption>**Fig. 9** Illustration of Subtree-Schedule (Algorithm 4). Given a sub-instance $L, R$ (top figure, with white ovals indicating the inner border of the subtree), each $\ell \in L$ is tried, yielding two smaller sub-instances corresponding to the outside and inside of $\ell$ (middle figures). After solving each sub-instance independently (bottom graphs), using the DP-table for memorization, a solution is obtained for $(L, R)$ by merging both solutions and appending $\ell$ and all its neighborhood. Here the arboricity is 3 (there are 3 minimal arcs in $L$), so any border uses at most 4 arcs, giving the upper bound of $\binom{n}{4}$ on the number of sub-instances</figcaption></figure>

<figure><img src="image_12.png" /><figcaption>**Fig. 10** Budget decomposition (with Proposition 10) around a prefix $P$ of $S^{\square 4}$. The maximal budget of $S^{\square 4}$ is reached as the budget of $P$ or as the budget of $S^{\square 4} \setminus P$ taking into account the difference $\delta(P)$ at the start of $S^{\square 4} \setminus P$.</figcaption></figure>
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 a indirect $O(n^{\rho+1})$-space, $O(n^{\rho+2})$-time algorithm [27] 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/\Phi!})$ in space and $O(n^{\Phi+2}/\Phi!)$ 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 [31] and [11] to try to formulate an “obstacle theory” for directed pathwidth might be an interesting avenue.

# Appendix A Mixed MIS in bipartite graphs

Our Divide-and-Conquer strategy to the BISR problem relies on the computation of maximum independent sets containing at least one vertex in each part of the input bipartite graph.

We informally call *mixed bipartite maximum independent set* (Mixed-MIS) the problem of deciding whether an input bipartite graph $G$ has a maximum independent set intersecting both of its parts. It is trivially polynomial, as one may check for each pair $(l, r) \in L \times R$, whether $I' \cup \{l, r\}$ is a maximum independent set of $G$; with $I'$ maximum independent set of $G'$, and $G'$ obtained from $G$ by removing $l, r$ as well as their neighborhoods.

As a maximum independent set of a bipartite graph may be derived from a maximum matching, this simple strategy yield a $O(|V|^2 \cdot \sqrt{|V||E|})$ algorithm for our Mixed-MIS problem.

We present here a more efficient strategy, based on a decomposition taking place in two rounds. It results into Algorithm 4. The first round is based on the Dulmage-Mendelsohn decomposition of bipartite graphs. It yields a partition of the vertices of $G$ into three sets $D, A, C$, defined as such: for each vertex $v$ of $D$, there exists a maximum matching in which $v$ is not matched, $A = N(D)$ is the union of the neighborhoods of the vertices of $D$, and $C = V \setminus (D \cup A)$ contains the remaining vertices. $D, A, C$ verify the following result:
$$bg(S^{\langle q \rangle}) = \max(bg(S^{\langle q-1 \rangle}), bg(S^{\langle q \rangle}) - (q-1))$$

*Proof* Apply Proposition 10 with prefix $S^{\langle q-1 \rangle}$ with $\delta(S^{\langle q-1 \rangle}) = -(q-1)$ by definition. □

**Corollary 3** Given $S$ with $\delta_{min}(S) = -k$, we have, for any $p \in [1:k] \cup \{\infty\}$,

$$bg(S^{\langle q \rangle}) = \max_{i \in [1:k]} (bg(S^{\langle i \rangle}) - (i-1))$$

*Proof* This is obtained by applying Corollary 2 $p$ times. □

**Corollary 4** Given $S$ with $\delta_{min}(S) = -k$, we have, for any $p \in [1:k] \cup \{\infty\}$,

$$bg(S) = \max(bg(S^{\langle q \rangle}, bg(S \setminus S^{\langle q \rangle}) - p)$$

*Proof* It is done by substituting $p$ by $\infty$ and $q$ by $p$ in Corollary 2. □

### 5.3.2 Properties of canonical schedules

We first prove a property on dividers:

**Property 2** If $Z$ is a divider over a graph $G$ then $\alpha(G[Z]) = |G[Z] \cap R|$

*Proof* It is a consequence of the divider definition. Suppose by contradiction that there exists a divider $Z'$ over $G$ with $|I(Z') \cap G[Z]| > |G[Z] \cap R|$, then we can replace the nodes in $I(Z)$ that are also in $G[Z] \cap R$ by nodes in $I(Z') \cap G[Z]$. We achieve a maximum independent set of higher cardinality for $G$ which is a contradiction and thus $\alpha(G[Z]) = G[Z] \cap R$. □

The property below follows for canonical two-sided schedules.

**Property 3** If $S$ is a canonical two-sided schedule, then $S = P \overleftarrow{Q}$ where $P$ and $Q$ are canonical one-sided schedules over respectively $G[P]$ and $\overleftarrow{G[Q]}$, with additionally $V(Q) \neq \emptyset$.
**Theorem 8** (Dulmage-Mendelsohn decomposition, Proposition 2.1 of [30], theorem 3.2.4 of [29]) *Given G bipartite graph and D, A, C defined as above, we have that:*

a. $D$ is the intersection of all maximum independent sets of $G$.

- $A$ is the intersection of all minimum vertex covers of $G$.

- the subgraph $G[C]$ induced by $C$ has a perfect matching, which may be deduced from restricting any maximum matching of $G$ to $C$.

b. In addition, $D$ may be computed from any maximum matching $M$ of $G$ using the following characterization ([30], lemma 2.2): $D = \overline{W}$ where $\overline{W}$ is composed of the vertices left unmatched by $M$, as well as all vertices connected to an unmatched vertex through an alternating path of even length.

This decomposition may allow to conclude in some cases (see Algorithm 4). In general, however, a second round of decomposition is needed. In this second round, the set $C$, which allows for a perfect matching $M$, is further decomposed into *elementary sub-graphs* (section 4.1 of [29], theorem 4.1.1 and exercise 4.1.5) and [32]. It consists in computing the strongly connected components of a directed graph $H(M, C)$ associated to $M$ and $C$ (same construction as in Section 3). The vertices of $H$ are the edges of the matching, and $(l, r) \to (l', r')$ iff $l$ is connected to $r'$ in $C$. The strongly connected components of $H$ constitute a decomposition of $G$ into elementary sub-graphs. A bipartite graph is elementary iff the sides $L, R$ are the only minimum vertex covers/maximum independent sets [29](theorem 4.1.1). If it is not elementary, then a mixed maximum independent set may be obtained by ordering the elementary sub-graphs $\{(L_i, R_i)\}_{1 \le i \le p}$ along a topological order induced by $H(C, M)$. Any set of the form $(\cup_{i \le l} R_i) \cup (\cup_{i > t} L_i)$ for some $t > 1$ is then a mixed maximum independent set of $C$.

The discussion above results in Algorithm 4, whose run-time is dominated by the computation of maximum matching in $O(\sqrt{|V||E|})$.

# Appendix B Delayed proofs

## B.1 Making an interval representation *nice*

Let $\{(a_u, b_u) | u \in V\}$ be an interval representation for a directed graph $H$ with vertex set $V$. We explain here how to turn it into a nice interval representation:

If an integer $n$ is such that $a_{u_0} = \dots = a_{u_l} = b_{v_0} = \dots = b_{v_p} = n$, we may
modify the representation as such:

* Interval bounds associated to integers $> n$ are increased by $p+l-1$, to make room for “spreading” $a_{u_1} \dots a_{u_l}, b_{v_1} \dots b_{v_p}$.

* $\forall i, a_{u_i}$ is set to $n+i$ and $b_{v_i}$ to $l+i$.

None of these modifications change the way intervals intersect one another, leaving the width unchanged. The representation is then “packed” into
36 Bipartite IS Reconfiguration: General and RNA-inspired Algorithms

Proof By definition of a canonical two-sided schedule (Definition 4), $S = P \overleftarrow{Q}$, with $V(Q) \neq \emptyset$, $V(P)$ (potentially empty) divider, $P$ canonical, and $Q$ canonical in $\overleftarrow{G}[Q]$. In addition, thanks to Property 2, $G[P]$ is a one-sided graph and with $P$ canonical by assumption, $P$ is indeed canonical one-sided. Note that $Q$ is a divider of $\overleftarrow{S}$ and with same property 2, $\overleftarrow{G}[Q]$ and $Q$ canonical we have $Q$ canonical one-sided, which concludes the proof. $\square$

The following properties follow from the definition:

**Proposition 11** Any canonical sequence of $G$ is optimal.

Proof We take $S$ canonical, suppose first that $S$ is canonical one-sided. By definition with $p = \infty$, we have that any licit schedule $T$ is a licit $p$-sequence so $bg(S) = bg(S^{\leftarrow\infty}) \le bg(T)$ and $S$ is optimal. Suppose now that $S$ is canonical two-sided: $S = P \overleftarrow{Q}$ with $P$ and $Q$ canonical one-sided in the corresponding subgraphs. Pick any licit schedule $T$. As $G$ is two-sided, we apply Lemma 3 with divider $Z = V(P)$ and we write $T' = (T \cap Z) \cdot (T \setminus Z)$: $bg(T') \le bg(T)$. We now show that $bg(S) \le bg(T')$. As $V(T \cap Z) = V(P)$ (and thus $\delta(T \cap Z) = \delta(P)$), we just have to show that (1) $bg(P) \le bg(T \cap Z)$ and (2) $bg(\overleftarrow{Q}) \le bg(T \setminus Z)$ (consequence of the definition, using a similar decomposition as in Proposition 10). With $P$ and $Q$ canonical one-sided (with Proposition 3), we have exactly (1) and for (2) we have $bg(Q) \le bg(\overleftarrow{T} \setminus Z)$ that can be rewritten

$$ \begin{aligned} \mathrm{bg}(\overleftarrow{Q}) &= |L \cap Q| - |R \cap Q| + \mathrm{bg}(Q) \\ &\le |L \cap Q| - |R \cap Q| + \mathrm{bg}(\overleftarrow{T} \setminus Z) = \mathrm{bg}(T \setminus Z) \end{aligned} $$

which concludes the proof. $\square$

**Proposition 12** If $G$ has $|L| = |R| = \alpha(G)$, then any optimal sequence is canonical.

Proof With $|R| = \alpha(G)$, $G$ is one-sided. With $|L| = \alpha(G)$, we have $k_M(L) = 0$. To show that $S$ optimal is canonical, we thus just have to show that $bg(S^{\leftarrow\infty}) \le bg(T)$ given any schedule $T$. With $S$ optimal $bg(S) \le bg(T)$ and $bg(S) = bg(S^{\leftarrow\infty})$, we indeed have the property and $S$ is canonical. $\square$

**Proposition 13** If $T$ is a canonical one-sided schedule for $G$ and $S$ an optimal schedule such that for all $p \in [1 : k_L(G)] \cup \{\infty\}$, there exists $q \le p$ such that $bg(S^{\diamond p}) \le bg(T^{\diamond q})$, then $S$ is canonical one-sided.

Proof As $T$ is canonical one-sided and $\forall p \in [1 : k_L(G)] \cup \{\infty\}$, $\forall U$ $p$-sequence, $bg(T^{\diamond p}) \le bg(U)$. To show that $S$ is canonical, we just have to show that $\forall p \in [0 : k_L(G)] \cup \{\infty\}$, $bg(S^{\diamond p}) \le bg(T^{\diamond p})$. Given $p \in [1 : k_L(G)] \cup \{\infty\}$

$$ \mathrm{bg}(S^{\diamond p}) = \max_{i \in [1:p]} (\mathrm{bg}(S^{\diamond i}) - (i-1)) \quad \text{with Corollary 3} $$
**Algorithm 4** Mixed bipartite maximum independent set

**Input:** a bipartite graph $G$ with sides $L$ and $R$. We suppose w.l.o.g that $|L| \ge |R|$.

**Output:** If it exists, a Maximum Independent Set $I$ of $G$ intersecting both $L$ and $R$.

1: $M = \text{MAXIMUMMATCHING}(G) \quad \triangleright O(\sqrt{|V|} \cdot |E|)$

2:

3: $I = \text{MAXIMUMINDEPENDENTSET}(G, M) \quad \triangleright O(|E|)$

4: **if** ($I \cap L \neq \emptyset$) **and** ($I \cap R \neq \emptyset$) **then**

5: **return** $I$

6: **end if** \quad $\triangleright$ // Now $|I| = \max(|L|, |R|)$ and $I = L$ or $I = R$

7:

8: $D, A, C = \text{COARSEDULMAGE MENDELSOHN}(M, G) \quad \triangleright O(|E|)$

9: **if** $|L| > |R|$ **then**

10: **if** $R \setminus A \neq \emptyset$ **then**

11: $\triangleright$//A is the intersection of all minimum vertex covers

12: pick $r \in R \setminus A$

13: $G' = G \setminus \{r \cup N(r)\}$

14: $M' = \text{MAXIMUMMATCHING}(G')$

15: $I' = \text{MAXIMUMINDEPENDENTSET}(G', M')$

16: **return** $I' \cup \{r\}$

17: **else**

18: **return** $\perp$; \quad $\triangleright$ // Not possible, $L$ is the only MIS

19: **end if**

20: **else if** $|L| = |R|$ **then**

21: $\triangleright$ // $L$ and $R$ are two MIS. So necessarily $D = \emptyset, A = \emptyset, C = G$

22: $\{(L_i, R_i)\}_{1 \le i \le p} = \text{FINEDULMAGE MENDELSOHN}(M, C) \quad \triangleright O(|V|^2)$

23: **if** $p=1$ **then**

24: **return** $\perp$

25: **else**

26: $\triangleright$ Topological sort of the SCCs of $H$

27: $s=\text{TOPOLOGICALSORT}(\{(L_i, R_i)\}) \quad \triangleright O(|V| + |E|)$

28: $(L_i, R_i) = s[0] \quad \triangleright$ // first in topological sort

29: **return** $R_i \cup (\cup_{j \neq i} L_j)$

30: **end if**

31: **end if**

$[1...2|V(H)|]$ by taking the interval bounds in order and setting them to their final position.