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

Lemma 3. Every fibre is a guarding set. In particular, g ( P ) ≤ f ( P ) .

Proof. Consider a poset P =( V, ≤ ) and one of its downset D ↆ V .Let F :=

V D , A := max( D ), and B := min( F ), i.e., A is the antichain of maximal

elements in the order induced by D and B is the antichain of minimal elements
in the order induced by F . By definition, a guarding set is a hitting set for the
collection of subsets A

\

B constructed in this way.
Let us now consider the subset A

∪

B B , where B

∪ ↆ A ∪ := { b ∈ B : b

is incomparable to a, . This set is easily shown to be a maximal antichain.

Hence, it must be hit by any fibre.

∀ a ∈ A }

Duffus, Kierstead, and Trotter [ 8 ] have shown that every poset on n elements
has a fibre of size at most 2 n/ 3. This directly yields the following.

Corollary 4. For every n -element poset P , g ( P ) ≤ 2 n/ 3 .

We now consider a special case for which the notions of guarding set and fibre
coincide. A poset is bipartite if P = min( P ) ∪ max( P ), i.e., if the height of P is

at most 2.

Lemma 4. For a bipartite poset P ,aset S is a guarding set for P if and only
if it is a fibre of P .

Proof. We know from Lemma 3 that every fibre is a guarding set. The other
direction is as follows.
Consider a guarding set S and let A be any maximal antichain of P .Let
T := A

max( P ), and let D be the downset generated by T . As a downset D is
guarded, hence either an element of T is hit by S , or an element of min( P

∩

\ D )

is hit, but since A is maximal A = T ∪ min( P \ D ), hence A is hit. Therefore, S

is a fibre.

6.2 Complexity

Lemma 4 yields two interesting corollaries on the complexity of recognizing and
finding guarding sets.

Corollary 5. Given a poset P and a subset S of its elements, the problem of
deciding whether S is a guarding set is coNP-complete. This holds even if P is
bipartite.

Proof. Recognition of fibres in bipartite posets has been proved coNP-complete
by Duffus et al. [ 8 ]. From Lemma 4 , this is the same problem as recognizing
guarding sets.

Corollary 6. Given a poset P and an integer k , the problem of deciding whether
there exists a guarding set of size at most k is ʣ 2 -complete. This holds even if
P is bipartite.