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 zones. 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 following:cover the cells of a line arrangement with a minimum number of lines,select a smallest subset of edges in a graph such that for every acyclic orientation, there exists a selected edge that can be flipped without creating a cycle,find a smallest set of incomparable pairs of elements in a poset such that in every linear extension, at least one such pair is consecutive,find a minimum-size fibre in a bipartite poset.We give upper and lower bounds on the worst-case minimum size of a covering by zones in several of those cases. We also consider the computational complexity of those problems, and establish some hardness results.
@article{10_37236_5076,
author = {Jean Cardinal and Stefan Felsner},
title = {Covering partial cubes with zones},
journal = {The electronic journal of combinatorics},
year = {2015},
volume = {22},
number = {3},
doi = {10.37236/5076},
zbl = {1343.05120},
url = {http://geodesic.mathdoc.fr/articles/10.37236/5076/}
}
TY - JOUR
AU - Jean Cardinal
AU - Stefan Felsner
TI - Covering partial cubes with zones
JO - The electronic journal of combinatorics
PY - 2015
VL - 22
IS - 3
UR - http://geodesic.mathdoc.fr/articles/10.37236/5076/
DO - 10.37236/5076
ID - 10_37236_5076
ER -
%0 Journal Article
%A Jean Cardinal
%A Stefan Felsner
%T Covering partial cubes with zones
%J The electronic journal of combinatorics
%D 2015
%V 22
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/5076/
%R 10.37236/5076
%F 10_37236_5076
Jean Cardinal; Stefan Felsner. Covering partial cubes with zones. The electronic journal of combinatorics, Tome 22 (2015) no. 3. doi: 10.37236/5076
