Input: | H-description of a polyhedron P Ì Q^{d}, c Î Q^{d}, C Î Q |
---|---|
Output: | "Yes" if there is a vertex v of P with c^{T}v = C; "No" otherwise |
Status (general): | Strongly NP-complete |
---|---|
Status (fixed dim.): | Polynomial time |
Proved to be NP-complete by Chandrasekaran, Kabadi, and Murty [11] and strongly NP-complete by Fukuda, Liebling, and Margot [22]. The problem remains strongly NP-complete even if the input is restricted to polytopes [22]. |
Related problems: | 25, 26 |
---|