2016/11/05 by Andrei Nikolaev, Nikolaev, Andrei
Mathematics · #52B12 #90C57 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:52B12 #msc:90C57
paper · pdf · doi:10.48550/arxiv.1611.01645
22 pages
arxiv created 2017/03/22 · arxiv updated 2017/03/23
Following the seminal work of Padberg on the Boolean quadric polytope BQP and its LP relaxation BQPLP, we consider a natural extension: SATP and SATPLP polytopes, with BQPLP being projection of the SATPLP face (and BQP -- projection of the SATP face). We consider a problem of integer recognition: determine whether a maximum of a linear objective function is achieved at an integral vertex of a polytope. Various special instances of 3-SAT problem like NAE-3-SAT, 1-in-3-SAT, weighted MAX-3-SAT, and others can be solved by integer recognition over SATPLP. We describe all integral vertices of SATPLP. Like BQPLP, polytope SATPLP has the Trubin-property being quasi-integral (1-skeleton of SATP is a subset of 1-skeleton of SATPLP). However, unlike BQP, not all vertices of SATP are pairwise adjacent, the diameter of SATP equals 2, and the clique number of 1-skeleton is superpolynomial in dimension. It is known that the fractional vertices of BQPLP are half-integer (0, 1 or 1/2 valued). We show that the denominators of SATPLP fractional vertices can take any integral value. Finally, we describe polynomially solvable subproblems of integer recognition over SATPLP with constrained objective functions. Based on that, we solve some cases of edge constrained bipartite graph coloring.