Linear Datalog and Bounded Path Duality of Relational Structures

Abstract

In this paper we systematically investigate the connections between logics with a finite number of variables, structures of bounded pathwidth, and linear Datalog Programs. We prove that, in the context of Constraint Satisfaction Problems, all these concepts correspond to different mathematical embodiments of a unique robust notion that we call bounded path duality. We also study the computational complexity implications of the notion of bounded path duality. We show that every constraint satisfaction problem $\csp(\best)$ with bounded path duality is solvable in NL and that this notion explains in a uniform way all families of CSPs known to be in NL. Finally, we use the results developed in the paper to identify new problems in NL.

Cited by in corpus (8)

• Approximating the partition function of the ferromagnetic Potts model
• A Characterisation of First-Order Constraint Satisfaction Problems
• The Complexity of Approximately Counting Stable Matchings
• Approximating the Tutte polynomial of a binary matroid and other related combinatorial polynomials
• The Complexity of Approximately Counting Stable Roommate Assignments
• Maximal Digraphs With Respect to Primitive Positive Constructibility
• Symmetric Linear Arc Monadic Datalog and Gadget Reductions
• The Smallest Hard Trees