Go backward to 7 Number of VerticesGo up to 2 Coordinate DescriptionsGo forward to 9 Recognizing Integer Polyhedra |
XHTML 1.0 |

Input: | Polytope P given as {, a set x ∈ R^{s} : A x =
b, x ≥ 0}S ⊆ {1, …, s} |
---|---|

Output: | "Yes" if there is a feasible basis with an index set
containing S, "No" otherwise |

Status (general): | NP-complete |
---|---|

Status (fixed dim.): | Polynomial time |

See Murty [49] (Garey and Johnson [23], Problem
[MP4]). For fixed dimension, one can enumerate all bases in
polynomial time.
The problem can be reformulated as follows. Let |

Why are some symbols not displayed correctly? |