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)
Incoming Non-self Citations Over Time
Authors
- 1. Antoine Amarilli
- 2. Mikaël Monet
- 3. Pierre Senellart
Incoming Citations (Sorted by Pagerank)
Showing 2 of 2 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 4,937 | New Results for the Complexity of Resilience for Binary Conjunctive Queries with Self-Joins | 2020 | PODS | 5.8187108e-05 |
| 7,163 | Probabilistic Query Evaluation: The Combined FPRAS Landscape | 2023 | PODS | 4.8132033e-05 |
Previous
Page 1 / 1
Next
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 |
|---|---|---|---|---|
| 602 | On the Complexity of Bounded-Variable Queries | 1995 | PODS | 0.00019352415 |
| 1,663 | Conjunctive Queries over Trees | 2004 | PODS | 0.00010977096 |
| 5,296 | Running Tree Automata on Probabilistic XML | 2009 | PODS | 5.5802694e-05 |
| 6,415 | Queries with Difference on Probabilistic Databases | 2011 | VLDB | 5.0731258e-05 |
| 6,997 | Tractable Lineages on Treelike Instances: Limits and Extensions | 2016 | PODS | 4.8676446e-05 |
| 7,739 | Symmetric Weighted First-Order Model Counting | 2015 | PODS | 4.663547e-05 |
Previous
Page 1 / 1
Next