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 M-ij = 1 if and only if the jth element is in the ith set in C. such that all l's appear consecutively in each row of M. A set X is an element of C is hit by a subset S' subset of S if X boolean AND S' not equal 0. Let C-r (red collection) and C-b (blue collection) be two collections of subsets of S respectively. The red-blue hitting set problem asks for a subset S' subset of 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(vertical bar C-b parallel to S vertical bar + vertical bar C-r parallel to S vertical bar + vertical bar S vertical bar(2)) for this problem with C-r boolean OR C-b having the consecutive ones property, which improves the previous time bound O(vertical bar C-r parallel to C-b parallel to S vertical bar(2)) by Dom et al. (2008) [8]. (C) 2010 Elsevier B.V. All rights reserved.