Constructive Upper Bounds on the Rectangle Eliminating Number in Grid Graphs
摘要
The hitting set is a fundamental concept in graph theory and combinatorial optimization. In this paper, we study a special class of the hitting set problem in grid graphs. Given an \(n\times m\) grid graph \(G=(V,E)\) , a rectangle eliminating set is an edge subset \(A\subseteq E\) such that \(G-A\) contains no rectangular outlines. The minimum cardinality of the rectangle eliminating set is the rectangle eliminating number, denoted by S(n, m). We derive several upper bounds for S(n, m) by periodic sampling, binary decomposition and hybrid constructions. In particular, for square grids, we show that \(S(n,n) \le \frac{2n^2}{3} + \frac{40}{3}\sqrt{2} \cdot \sqrt{n} + 3\) when \(n \ge 32\) .