Independent and Hitting Sets of Rectangles Intersecting a Diagonal Line

José R. Correa, Laurent Feuilloley, José A. Soto

Introduction

In computational geometry, managing axis-parallel rectangles is a foundational task with applications ranging from VLSI design to map labeling. Two central optimization problems in this domain are the Maximum Independent Set (MIS)—finding the largest collection of non-overlapping rectangles—and the Minimum Hitting Set (MHS)—finding the smallest set of points that intersects every rectangle in a given family.

A family of axis-parallel rectangles intersecting a common diagonal line.

While these problems are NP-hard for general rectangles, researchers often look for restricted settings that remain theoretically interesting yet computationally tractable. This paper investigates "diagonal-intersecting families," where every rectangle must intersect a common diagonal line (e.g., $y = -x$). This constraint serves as a critical stepping stone toward resolving broader questions like Wegner’s Conjecture, which posits that the "duality gap"—the ratio between the sizes of the MHS and the MIS—is bounded by a small constant.

Complexity and the Boundary of Hardness

The authors identify a sharp transition in computational complexity based on how rectangles relate to the diagonal.

  1. Diagonal-Lower-Intersecting: If rectangles intersect the diagonal but are restricted to the region below it, the problem is solvable in polynomial time.
  2. General Diagonal-Intersecting: If rectangles can cross the diagonal to both sides, the MIS problem becomes NP-complete.

To prove NP-completeness for the general case, the researchers employed a reduction from Planar 3-SAT. They constructed complex "gadgets"—variable and clause components made of rectangles—that mimic logical operations. This demonstrates that even with the diagonal constraint, the structural complexity of rectangle overlaps can encode hard logical problems.

The Harpoon Algorithm

For the tractable "diagonal-lower-intersecting" subclass, the paper introduces a significant algorithmic improvement. Previous solutions required $O(n^3)$ time. The authors developed a dynamic programming approach that achieves $O(n^2)$ time by utilizing a geometric structure they call a harpoon.

Geometric constructions illustrating 'harpoon' regions and the dynamic programming approach for independent sets.

A harpoon is a specific region defined by a pair of rectangles. By calculating optimal solutions for these regions and leveraging amortized analysis, the authors show that the cost of computing solutions across all harpoons is effectively constant per rectangle, leading to the quadratic speedup. This algorithm also extends to the Maximum Weight Independent Set (WMIS) problem, where each rectangle has an associated value.

Tightening the Duality Gap

A major contribution of this work is the refinement of the duality gap for diagonal-intersecting families. The duality gap represents the efficiency of hitting sets relative to independent sets.

  • Previous Bounds: The best-known upper bound for the duality gap in this class was 6.
  • New Bounds: The authors improved this upper bound to 4. They also established a lower bound of 2 by exhibiting specific rectangle families (such as the "doubled 6-cycle") where the hitting set must be at least twice the size of the independent set.

These results are summarized across different subclasses:

  • Diagonal-touching: Gap between 1.5 and 2.
  • Diagonal-lower-intersecting: Gap between 2 and 3.
  • General diagonal-intersecting: Gap between 2 and 4.

Conclusion

This research clarifies the algorithmic landscape for rectangles constrained by a diagonal line. By providing an $O(n^2)$ algorithm for the lower-intersecting case and proving NP-completeness for the general case, the authors delineate the limits of efficiency. Furthermore, tightening the duality gap to a factor of 4 brings us closer to understanding Wegner’s Conjecture. Future work remains in determining the exact complexity of the Minimum Hitting Set problem for these classes and developing methods to recognize the intersection graphs of these geometric families.

Summary updated

BibTeX
@inproceedings{correa2014independent,
  author = {José R. Correa and Laurent Feuilloley and José A. Soto},
  title = {{Independent and Hitting Sets of Rectangles Intersecting a Diagonal Line}},
  booktitle = {LATIN},
  year = {2014},
  doi = {10.1007/978-3-642-54423-1\_4},
}
Figure