Information Technology Reference
In-Depth Information
Covering Partial Cubes with Zones
B
B
Jean Cardinal
1(
)
and Stefan Felsner
2(
)
1
Universite Libre de Bruxelles (ULB), Brussels, Belgium
jcardin@ulb.ac.be
2
Technische Universitat Berlin, Berlin, Germany
felsner@math.tu-berlin.de
Abstract.
A partial cube is a graph having an isometric embedding
in a hypercube. Partial cubes are characterized by a natural equivalence
relation on the edges, whose classes are called
. The number of zones
determines the minimal dimension of a hypercube in which the graph
can be embedded. We consider the problem of covering the vertices of
a partial cube with the minimum number of zones. The problem admits
several special cases, among which are the problem of covering the cells
of a line arrangement with a minimum number of lines, and the problem
of finding a minimum-size fibre in a bipartite poset. For several such
special cases, we give upper and lower bounds on the minimum size of
a covering by zones. We also consider the computational complexity of
those problems, and establish some hardness results.
zones
1
Introduction
As an introduction and motivation to the problems we consider, let us look at
two puzzles.
Hitting a consecutive pair.
Given
asetof
n
elements, how many pairs
of them must be chosen so that every
permutation of the
n
elements has two
consecutive elements forming a chosen
pair?
Guarding cells of a line arrange-
ment.
Given an arrangement of
n
straight lines in the plane, how many
lines must be chosen so that every cell
of the arrangement is bounded by at
least one of the chosen line?
While different, the two problems can
be cast as special cases of a general
problem involving
partial cubes
.The
n
-dimensional hypercube
Q
n
is the
graph with the set
101111
0
101111
1
111111
1
101110
0
1
101110
111110
1
001110
0
101010
0
111010
1
001010
0
101010
1
101100
1
111100
1
001100
0
001100
1
101000
111000
1
1
001000
0
001000
1
100000
1
110000
1
000000
1
Fig. 1.
A partial cube with vertex labels
representing an isometric embedding in
Q
7
and a highlighted zone.
n
{
0
,
1
}
of binary words of length
n
as vertex set, and an
