We look at dynamic programming algorithms for propositional model counting, also called #SAT, and MaxSAT. Tools from graph structure theory, in particular treewidth, have been used to successfully identify tractable cases in many subfields of AI, including SAT, Constraint Satisfaction Problems (CSP), Bayesian reasoning, and planning. In this paper we attack #SAT and MaxSAT using similar, but more modern, graph structure tools. The tractable cases will include formulas whose class of incidence graphs have not only unbounded treewidth but also unbounded clique-width. We show that our algorithms extend all previous results for MaxSAT and #SAT achieved by dynamic programming along structural decompositions of the incidence graph of the input formula. We present some limited experimental results, comparing implementations of our algorithms to state-of-the-art #SAT and MaxSAT solvers, as a proof of concept that warrants further research.

The Independent Set problem is NP-hard in general, however polynomial time algorithms exist for the problem on various specific graph classes. Over the last couple of decades there has been a long sequence of papers exploring the boundary between the NP-hard and polynomial time solvable cases. In particular the complexity of Independent Set on P5-free graphs has received significant attention, and there has been a long list of results showing that the problem becomes polynomial time solvable on sub-classes of P5-free graphs. In this paper we give the first polynomial time algorithm for Independent Set on P5-free graphs. Our algorithm also works for the Weighted Independent Set problem.

In this paper, we study the point-set-embeddability-problem, i.e., given a planar graph and a set of points, is there a mapping of the vertices to the points such that the resulting straight-line drawing is planar? It was known that this problem is NP-hard if the embedding can be chosen, but becomes polynomial for triangulated graphs of treewidth 3. We show here that in fact it can be answered for all planar graphs with a fixed combinatorial embedding that have constant treewidth and constant face-degree.