Algorithms for Planar F-Deletion and Satisfi­ability

Parameterized algorithms measure running time against both the input size and some structural parameter, so that the combinatorial explosion depends only on that parameter and not on the whole input. I apply that lens in two settings. On graphs, Planar F-Deletion gives one meta-algorithm for a whole family of deletion problems, Vertex Cover and Feedback Vertex Set included, built on a simple randomized algorithm and protrusion-based preprocessing. On formulas, I ask why SAT solvers succeed on huge industrial instances and look at backdoors: small sets of variables whose assignment leaves something easy, including heterogeneous backdoors and backdoors to small treewidth. There is also a brief look at manipulation in voting.