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,940 | New Results for the Complexity of Resilience for Binary Conjunctive Queries with Self-Joins | 2020 | PODS | 5.8131196e-05 |
| 7,162 | Probabilistic Query Evaluation: The Combined FPRAS Landscape | 2023 | PODS | 4.8085863e-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 |
|---|---|---|---|---|
| 603 | On the Complexity of Bounded-Variable Queries | 1995 | PODS | 0.00019334592 |
| 1,662 | Conjunctive Queries over Trees | 2004 | PODS | 0.00010966423 |
| 5,301 | Running Tree Automata on Probabilistic XML | 2009 | PODS | 5.5749031e-05 |
| 6,410 | Queries with Difference on Probabilistic Databases | 2011 | VLDB | 5.0682868e-05 |
| 6,996 | Tractable Lineages on Treelike Instances: Limits and Extensions | 2016 | PODS | 4.8629707e-05 |
| 7,738 | Symmetric Weighted First-Order Model Counting | 2015 | PODS | 4.6590737e-05 |
Previous
Page 1 / 1
Next