Join Sampling under Acyclic Degree Constraints and (Cyclic) Subgraph Sampling

Ru Wang, Yufei Tao

Given a join with an acyclic set of degree constraints, we show how to draw a uniformly random sample from the join result in $O(polymat/\max \{1,\mathrm{OUT}\})$ expec…