Covering partial cubes with zones (Q888589)

Summary: 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 \textit{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:{ } \(\bullet\) cover the cells of a line arrangement with a minimum number of lines, { } \(\bullet\) 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, { } \(\bullet\) 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, { } \(\bullet\) 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.