Some characteristics of the simple Boolean quadric polytope extension

Following the seminal work of Padberg on the Boolean quadric polytope $BQP$ and its LP relaxation $BQ{P}_{LP}$, we consider a natural extension: $SATP$ and $SAT{P}_{LP}$ polytopes, with $BQ{P}_{LP}$ being projection of the $SAT{P}_{LP}$ 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 $SAT{P}_{LP}$. We describe all integral vertices of $SAT{P}_{LP}$. Like $BQ{P}_{LP}$, polytope $SAT{P}_{LP}$ has the Trubin-property being quasi-integral (1-skeleton of $SATP$ is a subset of 1-skeleton of $SAT{P}_{LP}$). 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 $BQ{P}_{LP}$ are half-integer (0, 1 or 1/2 valued). We show that the denominators of $SAT{P}_{LP}$ fractional vertices can take any integral value. Finally, we describe polynomially solvable subproblems of integer recognition over $SAT{P}_{LP}$ with constrained objective functions. Based on that, we solve some cases of edge constrained bipartite graph coloring.