A short note on the counting complexity of conjunctive queries
A short note on the counting complexity of conjunctive queries
This note closes a minor gap in the literature on the counting complexity of conjunctive queries by showing that queries that are not free-connex do not have a linear time counting algorithm under standard complexity assumptions. More generally, it is shown that the so-called quantified star size is a lower …