In the 2-satisfiability problem, or 2SAT, the input is a system of constraints between pairs of Boolean variables, and the problem is to find a truth assignment satisfying all the constraints. Although the usual formulation writes the constraints as disjunctions (Boolean or), it’s convenient and equivalent to use implications instead, where each side of an implication can be either one of the variables or its negation. If you encode the variables as numbers, with \(1\) for true and \(0\) for false, then the negation of a variable \(x\) is \(1-x\) and the implication \(x\rightarrow y\) can be encoded as the linear inequality \(x\le y\). If we forget the restriction that the values are \(0\) or \(1\), this system of inequalities defines a convex polytope, which can be thought of as a relaxation of the given 2SAT problem. Each solution to the 2SAT problem corresponds to a vertex of this polytope but there might be other vertices as well, with fractional coordinates. We don’t want those; it’s more useful to have a polytope all of whose coordinates are integers, coming from solutions to the underlying 2SAT problem. When does this happen (without adding extra inequalities)?

I’m pretty sure the answer has been known, at least implicitly, for a long time, and that there are no new ideas in the rest of this post. See e.g. the answer to this very closely related question on relaxations of the vertex cover problem and note that vertex cover can be formulated as 2SAT, with a variable per vertex and two constraints per edge of the input graph. But when I looked for it, I found it difficult to find references that give the answer explicitly. So here it is. The following conditions are equivalent:

  • The given 2SAT instance has an integral relaxation.
  • The given 2SAT instance has two solutions that are the complements of each other (each variable is true in one of the solutions and false in the other).
  • The compatibility graph of the given 2SAT instance is bipartite.

Here, the compatibility graph is an undirected graph defined by Feder in “Network Flow and 2-Satisfiability” (Algorithmica 1994). It has a vertex for each literal (a variable or its negation). The two vertices for a variable and its negation are connected by an edge, called a “trivial edge”. Additionally, for each implication \(x\rightarrow y\), the two literals \(x\) and \(\lnot y\) cannot both be true, and we add an edge between them.

If the compatibility graph is bipartite, two-color it, make the vertices of one color be true, and make the vertices of the other color be false. Then this gives a solution to the 2SAT instance whose complement is also a solution. So the third condition implies the second condition.

The relaxation of any 2SAT instance contains the point whose coordinates all equal \(\tfrac12\), and if the given instance has an integral relaxation then this point can be represented as a weighted average of integer solutions. An odd cycle in the compatibility graph would prevent that from being possible. For any point in the relaxation, and any literal, we consider the value of the literal to be either its coordinate value (if it represents a variable) or one minus that value (if it represents a negated variable). If some cycle has odd length \(\ell\), then each integer point in the weighted average could only have total value at most \((\ell-1)/2\) on the literals of the cycle, so their weighted average would also be at most \((\ell-1)/2\), less than the cycle’s total value of \(\ell/2\) in the all-\(\tfrac12\) solution. So the first condition implies the third condition.

Finally, suppose that there are two complementary solutions, and flip the variables if necessary so that these are the all-false and all-true assignments to the variables. (This flipping simplifies the problem without changing any of the three conditions.) Consider any fractional solution \(S\), and construct from it a probability distribution on truth assignments as follows: choose a uniformly random number \(x\in [0,1]\), set to true the variables whose coordinate value is at least \(x\), and set to false the remaining variables. All truth assignments generated in this way solve the 2SAT problem, because any violation of an implication constraint in the 2SAT problem would translate to a violation of the corresponding coordinate inequality constraint in the relaxation. The given fractional solution \(S\) is a weighted average of the resulting collection of 2SAT solutions, where the weight of a solution is the probability of generating it. Therefore, the second condition implies the first condition.

(Discuss on Mastodon)