An improved algorithm for the red–blue hitting set problem with the consecutive ones property

Let S be a set of elements. We say that a collection C of subsets of S has the consecutive ones property if there exist a linear order on S and a 0–1 matrix M, where Mij=1 if and only if the jth element is in the ith set in C, such that all 1's appear consecutively in each row of M. A set X∈C is hit by a subset S′⊆S if X∩S′≠∅. Let Cr (red collection) and Cb (blue collection) be two collections of subsets of S respectively. The red–blue hitting set problem asks for a subset S′⊆S such that all sets in the blue collection are hit by S′, while the number of sets in the red collection hit by S′ has to be minimum. We present a shortest-path based algorithm with time complexity O(|Cb||S|+|Cr||S|+2|S|) for this problem with Cr∪Cb having the consecutive ones property, which improves the previous time bound O(|Cr||Cb|2|S|) by Dom et al. (2008) [8].