Covering Partial Cubes with Zones - Discrete and Computational Geometry and Graphs - page 5

Table 1. Worst-case bounds and complexities for the special cases of the partial cube
covering problem. When used, n denotes the dimension of the partial cube.

Partial cube Lower bound Upper bound Complexity

( √ n Arrangements of n n − o ( n )(Theorem 1 ) n − ʩ log n )[ 1 ] -

R 2 lines in

n − ʩ ( n 1 /d )
(Theorem 2 )

Arrangements of n
hyperplanes in R

- -

d

Acyclic orientations - Minimum edge cut

(Theorem 4 )

Recognition is
coNP-complete,
even for complete
graphs
(Theorem 3 )

Median graphs 1 n NP-complete

(Corollary 2 ),
APX-hard
(Corollary 3 )

Distributive lattices
with representative
poset of n elements

- 2 n/ 3 (Corollary 4 ) Recognition is

coNP-complete
(Corollary 5 )
ʣ

P
2

-complete
(Corollary 6 )

Trees with n edges n/ 2 n − 1 P(minedgecover)

3 Line Arrangements

Recall that we have defined a guarding set for an arrangement of lines as a subset
of the lines n so that every cell of the arrangement is bounded by at least one
of the chosen lines. We first give a lower bound on the size of a guarding set for
an arrangement of lines.

Theorem 1. The minimum number of lines needed to guard the cells of any
arrangement of n lines is n − o ( n ) .

Proof. The proof is a direct consequence of known results on the following prob-
lemfromErdos: given a set of points in the plane with no four points on a line,
find the largest subset in general position, that is, with no three points on a line.
Let ʱ ( n ) be the minimum size of such a set over all arrangements of n points.
Furedi observed [ 12 ] that ʱ ( n )= o ( n ) follows from the density version of the
Hales-Jewett theorem [ 13 ]. But this directly proves that we need at least n o ( n )

lines to guard all cells of an arrangement. The reduction is the one observed by
Ackerman et al. [ 1 ]: consider the line arrangement that is dual to the point set,
and slightly perturb it so that each triple of concurrent lines forms a cell of size
three. Now the complement of any guarding set is in general position in the
primal point set.

−

d , with d = O (1), there

We now show that for arrangements of hyperplanes in R

ʩ ( n 1 /d ). The proof is along the

always exists a guarding set of size at most n −

lines of the proof given in [ 3 ] for the d = 2 case.