Generating facets for the cut polytope of a graph by triangular elimination |
| |
Authors: | David Avis Hiroshi Imai Tsuyoshi Ito |
| |
Institution: | (1) School of Computer Science, McGill University, 3480 University Street, Montreal, QC, Canada, H3A 2A7;(2) Department of Computer Science, Graduate School of Information Science and Technology, The University of Tokyo, 7-3-1 Hongo, Bunkyo-ku, Tokyo 113-0033, Japan;(3) ERATO-SORST Quantum Computation and Information Project, Japan Science and Technology Agency, 5-28-3 Hongo, Bunkyo-ku, Tokyo 113-0033, Japan |
| |
Abstract: | The cut polytope of a graph arises in many fields. Although much is known about facets of the cut polytope of the complete
graph, very little is known for general graphs. The study of Bell inequalities in quantum information science requires knowledge
of the facets of the cut polytope of the complete bipartite graph or, more generally, the complete k-partite graph. Lifting is a central tool to prove certain inequalities are facet inducing for the cut polytope. In this paper
we introduce a lifting operation, named triangular elimination, applicable to the cut polytope of a wide range of graphs.
Triangular elimination is a specific combination of zero-lifting and Fourier–Motzkin elimination using the triangle inequality.
We prove sufficient conditions for the triangular elimination of facet inducing inequalities to be facet inducing. The proof
is based on a variation of the lifting lemma adapted to general graphs. The result can be used to derive facet inducing inequalities
of the cut polytope of various graphs from those of the complete graph. We also investigate the symmetry of facet inducing
inequalities of the cut polytope of the complete bipartite graph derived by triangular elimination.
|
| |
Keywords: | Cut polytope Lifting Facet Graph Fourier– Motzkin elimination |
本文献已被 SpringerLink 等数据库收录! |
|