Compact linear programs for 2SAT

DOI10.1016/J.EJC.2018.02.011MaRDI QIDQ2311345zbMATH OpenOpenAlexWikidataFDO

Authors Hans Raj Tiwary, David Avis

Publication date 10 July 2019

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1702.06723

zbMATH Keywords

multicommodity flows, superpolynomial extension complexity

Mathematics Subject Classification ID

Integer programming (90C10) Applications of mathematical programming (90C90)

Abstract: For each integer $n$ we present an explicit formulation of a compact linear program, with $O(n^3)$ variables and constraints, which determines the satisfiability of any 2SAT formula with $n$ boolean variables by a single linear optimization. This contrasts with the fact that the natural polytope for this problem, formed from the convex hull of all satisfiable formulas and their satisfying assignments, has superpolynomial extension complexity. Our formulation is based on multicommodity flows. We also discuss connections of these results to the stable matching problem.

Recommendations

• Linear programs for constraint satisfaction problems
• A compact linear program for testing optimality of perfect matchings.
• Network flow and 2-satisfiability
• Expressing combinatorial optimization problems by linear programs
• scientific article; zbMATH DE number 956857

Cites work

• A generalization of extension complexity that captures P
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• A new fixed point approach for stable networks and stable marriages
• An efficient algorithm for the “stable roommates” problem
• Network flow and 2-satisfiability
• Stable marriage and roommates problems with restricted edges: complexity and approximability
• The Structure of the Stable Roommate Problem: Efficient Representation and Enumeration of All Stable Assignments

Cited in

(3)

• Polynomial size linear programs for problems in \textsc{P}
• On deciding the non‐emptiness of 2SAT polytopes with respect to First Order Queries
• scientific article; zbMATH DE number 2090050 (Why is no real title available?)

This page was built for publication: Compact linear programs for 2SAT

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2311345)