Go backward to 17 Facet System Verification for Simple PolytopesGo up to 3 Combinatorial StructureGo forward to 19 US-Orientation |
XHTML 1.0 |

Input: | The (abstract) graph G of a simple polytope _{P}P |
---|---|

Output: | An AOF-orientation of G_{P} |

Status (general): | Open |
---|---|

Status (fixed dim.): | Open |

(Simple) polytopes admit AOF-orientations because every linear
function in general position induces an AOF-orientation.
In [32] it is shown that one can formulate the problem
as a combinatorial optimization problem, for which a strongly dual
problem in the sense of combinatorial optimization exists (see the
comments to Problem 16). Thus, the
AOF-orientations of G, i.e., there
are polynomial size proofs for both cases an orientation being an
AOF-orientation or not (provided that the integrity of the input
data is guaranteed). However, it is unknown if it is possible to
check in polynomial time if a given orientation is an AOF-orientation._{P} In dimensions one and two the problem is trivial. For a
three-dimensional polytope A polynomial time algorithm would lead to a polynomial algorithm for Problem 17 (see [32]). By duality of polytopes, the problem is equivalent to the problem of finding a shelling order of the facets of a simplicial polytope from the upper two layers of its face lattice. It is unknown whether it is possible to find in polynomial time a shelling order of the facets, even if the polytope is given by its entire face lattice. With this larger input, however, it is possible to check in polynomial time whether a given ordering of the facets is a shelling order. |

Related problems: | 17, 19, 35 |
---|

Why are some symbols not displayed correctly? |