Some observations on holographic algorithms (Q1616615)

The author introduces a notion of \textit{diversity} for families of finite functions in terms of the number of different functions that can be obtained by fixing some variables. He then first shows how known reductions for many NP-complete problems yield characterizations in terms of this notion. He furthermore introduces a notion of \textit{elementary reduction to matchgrids}, generalizing the one of the author [``Accidental algorithms'', in: Proceedings of the 47th annual IEEE symposium on foundations of computer science, FOCS'06. Los Alamitos, CA: IEEE Computer Society. 509--517 (2006)], specific to reductions from 3CNF, and shows that such a reductions also imposes constraints in terms of diversity. Finally, using the three-element basis \textbf{b3} from [the author, SIAM J. Comput. 37, No. 5, 1565--1594 (2008; Zbl 1152.05010)], the paper presents polynomial-time algorithms for problems for planar undirected graphs of degree three, namely, computing the parity of the number of solutions for feedback vertex sets, connected vertex covers, and vertex 3-colorings up to permutations of colors.