A bicolored rectangular family BRF is the collection of all axis-parallel rectangles formed by selecting a bottom-left corner from a finite set of points A and an upper-right corner from a finite set of points B. We devise a combinatorial algorithm to compute the maximum independent set and the minimum hitting set of a BRF that runs in O(n2.5logn)-time, where n= | A| + | B|. This result significantly reduces the gap between the Ω (n7) -time algorithm by Benczúr (Discrete Appl Math 129 (2–3):233–262, 2003) for the more general problem of finding directed covers of pairs of sets, and the O(n2) -time algorithms of Franzblau and Kleitman (Inf Control 63(3):164–189, 1984) and Knuth (ACM J Exp Algorithm 1:1, 1996) for BRFs where the points of A lie on an anti-diagonal line. Furthermore, when the bicolored rectangular family is weighted, we show that the problem of finding the maximum weight of an independent set is NP-hard, and provide efficient algorithms to solve it on important subclasses.
|Número de páginas||35|
|Estado||Publicada - jun. 2021|
Nota bibliográficaFunding Information:
The first author was partially supported by ANID-CHILE via FONDECYT 1181180, and PIA AFB170001. The second author was partially supported by ANID-CHILE via FONDECYT 11200616 and by the FSR Incoming Post-doctoral Fellowship of the Catholic University of Louvain (UCL), funded by the French Community of Belgium. The authors gratefully acknowledge Prof. Andreas S. Schulz for many stimulating discussions during the early stages of this paper.
© 2021, The Author(s), under exclusive licence to Springer Science+Business Media, LLC part of Springer Nature.
- Axis-parallel rectangles
- Hitting set
- Independent set
- Jump number