A bound on the \(k\)-gonality of facets of the hypermetric cone and related complexity problems (Q1803268): Difference between revisions

After a short introduction the authors give a complete description of \(L\)-polytopes (or Delaunay polytopes) related to facets. Upper bounds on the \(k\)-gonality of facet defining inequalities and on the number of facets of the hypermetric cone are studied. In the last chapter applications to computational complexity are discussed. The problem determining hypermetricity lies in co-NP. The authors give other related problems which are in co-NP (testing minimality of a lattice vector, \((2m+1)\)-gonality testing) and NP-hard (strong hypermetricity, (largest) complete bipartite subgraph).