Dekel Tsur

In the BICLUSTER EDITING (resp., FLIP CONSENSUS TREE) problem the input is a bipartite graph G=(V₁,V₂,E) and an integer k, and the goal is to decide whether there is a set F⊆V₁×V₂ such that the graph (V₁,V₂,E△F) does not contain an induced path on four vertices (resp., an induced path on five vertices whose endpoints are in V₂). In this paper we give algorithms for BICLUSTER EDITING and FLIP CONSENSUS TREE whose running times are O^⁎(2.22^k) and O(3.24^k), respectively. This improves over the O^⁎(2.636^k)-time algorithm for BICLUSTER EDITING of Tsur [IPL 2021] and the O^⁎(3.68^k)-time algorithm for FLIP CONSENSUS TREE of Komusiewicz and Uhlmann [Algorithmica 2014].