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

• Published in: Information processing letters 2010-09, Vol.110 (20), p.845-848
• Main Authors: Chang, Maw-Shang, Chung, Hsiao-Han, Lin, Chuang-Chieh
• Format: Article
• Language: English
• Subjects: Algorithms; Collection; Complexity; Complexity theory; Consecutive ones property; Covering problem; Design of algorithms; Hitting set; Matrix; Optimization algorithms; Shortest path; Shortest path algorithms; Shortest-path problems; Studies
• ISSN: 0020-0190; 1872-6119
• DOI: 10.1016/j.ipl.2010.07.010

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 i j = 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 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 ′ ⊆ 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 ( | C b | | S | + | C r | | S | + | S | 2 ) for this problem with C r ∪ C b having the consecutive ones property, which improves the previous time bound O ( | C r | | C b | | S | 2 ) by Dom et al. (2008) [8].