Showing cs.DMShow all
2 papers · 1 filter
cs.DM2023
Counting Answers to Unions of Conjunctive Queries: Natural Tractability Criteria and Meta-Complexity
Jacob Focke, Leslie Ann Goldberg, Marc Roth +1
We study the problem of counting answers to unions of conjunctive queries (UCQs) under structural restrictions on the input query. Concretely, given a class C of UCQs, the problem…
cs.DM2023
The Weisfeiler-Leman Dimension of Conjunctive Queries
Andreas Göbel, Leslie Ann Goldberg, Marc Roth
The Weisfeiler-Leman (WL) dimension of a graph parameter is the minimum such that, if and are indistinguishable by the -dimensional WL-algorithm then $f(G_1)…