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

corresponds to an acyclic orientation, and adjacent cells are exactly those that
differ by a single edge. This observation, in particular, shows that H is connected.
The graph H and the notion of edge flippability have been studied by Fukuda
et al. [ 11 ] and more recently by Cordovil and Forge [ 6 ].
The partial cube covering problem now becomes the following: given a graph
G =( V,E ), find a smallest subset S ↆ E such that for every acyclic orientation

of G , there exists e ∈ S such that flipping the orientation of e does not create a

cycle (Fig. 3 ).

2.3 Median Graphs

A median graph is an undirected graph in which every three vertices x , y ,and
z have a unique median , i.e., a vertex μ ( x, y, z ) that belongs to shortest paths
between each pair of x , y ,and z . Median graphs form structured subclass of
partial cubes that has been studied extensively, see [ 5 ] and references therein.
Since the star and the hypercube are median graph there are no non-trivial upper
or lower bounds for the zone cover problem on this class. We use a construction
of median graphs to prove hardness of the zone cover problem.

2.4 Distributive Lattices

Cover graphs of distributive lattices 2
are partial cubes. From Birkhoff's rep-
resentation theorem (a.k.a. Funda-
mental Theorem of Finite Distributive
Lattices) we know that there is a poset
P such that the vertices of the partial
cube are the downsets of P , the zones
of the partial cube in turn correspond
to the elements of P .
The problem becomes: given a
poset P , find a smallest subset S of
its elements such that for every downset D of P , there exists v

{1,2,3,4,6}

4 5 6

{1,2,4}

1 2 3

{3}

Fig. 4. A poset (left) and the cover graph
of its lattice of down-sets (right).

∈ S such that

either D ∪{ v } or D \{ v } is a downset, distinct from D .

2.5 Trees

Trees with n edges are partial cubes of dimension exactly n . Since every zone
contains exactly one edge, the partial cube covering problem on trees boils down
to the edge cover problem on trees. There are instances attaining the lower and
upper bounds of n/ 2and n 1, moreover, there is a simple dynamic programming

algorithm that computes an optimal cover in linear time.

−

2 For a very good introduction to terminology related to partial orders and lattices
we refer to Chapter 3 of Stanley, Enumerative Combinatorics Vol. I [ 17 ].