Bipartite Independent Set Reconfiguration: General and RNA-Inspired Parameterized Algorithms

Computing the energy barrier 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 On2-space, On2ρ+2.5-time algorithm for the range ρ, and a OnΦ+2-space, OnΦ+3-time algorithm for the arboricity Φ. We demonstrate the practicality of our algorithms on benchmarks respectively consisting of random Erdös-Rényi bipartite graphs, random pairs of RNA structures and experimentally-supported instances of RNA kinetics.