Abstract
Let S be a set and let C b (blue collection) and C r (red collection) be two collections of subsets of S. The MDH problem is to find a subset S′ ⊆ S such that S′ ∩ B ≠ ∅ for all B ∈ C b and |S′ ∩ R|≤ k for all R ∈ C r , where k is a given non-negative integer. The RBSC problem is to find a subset S′ ⊆ S with S′ ∩ B ≠ ∅ for all B ∈ C b which minimizes |{R |R ∈ C r , S′ ∪ R ≠ ∅}|. In this paper, improved algorithms are proposed for the MDH problem with k = 1 and all sets in C b having size two and the RBSC problem with C b ∪ C r having the consecutive ones property. For the first problem, we give an optimal O(|S|+|C b | + Σ R∈Cr |R|)-time algorithm, improving the previous O(|S|+|C b | + Σ R∈Cr |R| 2 ) bound by Dom et al. Our improvement is obtained by presenting a new representation of a dense directed graph, which may be of independent interest. For the second problem, we give an O(|C b |+|C r |lg|S|+|S|lg|S|)-time algorithm, improving the previous O(|C b ||S|+|C r ||S|+|S| 2 ) bound by Chang et al. © 2012 Springer-Verlag.