TY - JOUR

T1 - Independent Sets and Hitting Sets of Bicolored Rectangular Families

AU - Soto, José A.

AU - Telha, Claudio

N1 - Publisher Copyright:
© 2021, The Author(s), under exclusive licence to Springer Science+Business Media, LLC part of Springer Nature.

PY - 2021/6

Y1 - 2021/6

N2 - 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.

AB - 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.

KW - Axis-parallel rectangles

KW - Hitting set

KW - Independent set

KW - Jump number

KW - Axis-parallel rectangles

KW - Hitting set

KW - Independent set

KW - Jump number

UR - http://www.scopus.com/inward/record.url?scp=85101154957&partnerID=8YFLogxK

U2 - 10.1007/s00453-021-00810-1

DO - 10.1007/s00453-021-00810-1

M3 - Article

AN - SCOPUS:85101154957

VL - 83

SP - 1918

EP - 1952

JO - Algorithmica

JF - Algorithmica

SN - 0178-4617

IS - 6

ER -