Conjunctive Queries on Probabilistic Graphs: Combined Complexity

Summary: Classifies combined complexity of conjunctive queries on probabilistic binary instances (probabilistic graph homomorphism/CSP), pinpointing which features—labels, disconnectedness, branching, edge directions—make evaluation tractable or #P-hard. Combines automata→d‑DNNF and β‑acyclic lineage compilations for tractable cases and X‑property, graded DAGs and coding reductions for hardness, yielding a rich complexity map. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1732
Venue: PODS
Year: 2017
Pagerank: 5.5638493e-05
Overall Rank: 7,706 | 47.14%
DOI: 10.1145/3034786.3056121

Incoming Non-self Citations Over Time

Authors

1. Antoine Amarilli (Télécom Paris; Université Paris-Saclay)
2. Mikaël Monet (INRIA; Télécom Paris; Université Paris-Saclay)
3. Pierre Senellart (INRIA; PSL University; École normale supérieure)

BibTeX Citation

@inproceedings{amarilli_pods17,
        address = {New York, NY, USA},
        series = {{PODS} '17},
        title = {{Conjunctive Queries on Probabilistic Graphs: Combined Complexity}},
        url = {https://dl.acm.org/doi/10.1145/3034786.3056121},
        doi = {10.1145/3034786.3056121},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Amarilli, Antoine and Monet, Mikaël and Senellart, Pierre},
        year = {2017}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,670	New Results for the Complexity of Resilience for Binary Conjunctive Queries with Self-Joins	2020	PODS	6.5734205e-05
7,317	Probabilistic Query Evaluation: The Combined FPRAS Landscape	2023	PODS	5.6466593e-05

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
763	On the Complexity of Bounded-Variable Queries	1995	PODS	0.00014230134
1,564	Conjunctive Queries over Trees	2004	PODS	0.00010349456
5,346	Running Tree Automata on Probabilistic XML	2009	PODS	6.257995e-05
6,527	Queries with Difference on Probabilistic Databases	2011	VLDB	5.8509088e-05
7,640	Tractable Lineages on Treelike Instances: Limits and Extensions	2016	PODS	5.5766474e-05
8,084	Symmetric Weighted First-Order Model Counting	2015	PODS	5.4910538e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,707	The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints	2015	PODS
2	7,430	Solving a Special Case of the Intensional vs Extensional Conjecture in Probabilistic Databases	2020	PODS
3	4,301	Read-Once Functions and Query Evaluation in Probabilistic Databases	2010	VLDB
4	2,831	Secondary-Storage Confidence Computation for Conjunctive Queries with Inequalities	2009	SIGMOD
5	12,549	Query Evaluation with Soft-Key Constraints	2008	PODS
6	4,187	Maximally Joining Probabilistic Data	2007	PODS
7	8,626	Charting the Tractability Frontier of Certain Conjunctive Query Answering	2013	PODS
8	7,640	Tractable Lineages on Treelike Instances: Limits and Extensions	2016	PODS
9	7,317	Probabilistic Query Evaluation: The Combined FPRAS Landscape	2023	PODS
10	1,041	The Dichotomy of Conjunctive Queries on Probabilistic Structures	2007	PODS