Nested and co-nested formulas are two classes of CNF instances that can be characterized in terms of outerplanar graphs. For these classes, linear time algorithms are known for SAT and (unweighted) Max-SAT. In this paper we devise linear time algorithms for a general optimization version of SAT. Moreover, we show that a general probabilistic version of SAT reduces to solving a system of linear inequalities where the number of variables and constraints is linear in the size of the formula.
Optimization and probabilistic satisfiability on nested and co-nested formulas / Pretolani, Daniele. - In: ANNALS OF OPERATIONS RESEARCH. - ISSN 0254-5330. - STAMPA. - 188:(2011), pp. 371-387. [10.1007/s10479-008-0502-3]