TY - GEN
T1 - Fast and Perfect Sampling of Subgraphs and Polymer Systems
AU - Blanca, Antonio
AU - Cannon, Sarah
AU - Perkins, Will
N1 - Publisher Copyright:
© Antonio Blanca, Sarah Cannon, and Will Perkins.
PY - 2022/9/1
Y1 - 2022/9/1
N2 - We give an efficient perfect sampling algorithm for weighted, connected induced subgraphs (or graphlets) of rooted, bounded degree graphs. Our algorithm utilizes a vertex-percolation process with a carefully chosen rejection filter and works under a percolation subcriticality condition. We show that this condition is optimal in the sense that the task of (approximately) sampling weighted rooted graphlets becomes impossible in finite expected time for infinite graphs and intractable for finite graphs when the condition does not hold. We apply our sampling algorithm as a subroutine to give near linear-time perfect sampling algorithms for polymer models and weighted non-rooted graphlets in finite graphs, two widely studied yet very different problems. This new perfect sampling algorithm for polymer models gives improved sampling algorithms for spin systems at low temperatures on expander graphs and unbalanced bipartite graphs, among other applications.
AB - We give an efficient perfect sampling algorithm for weighted, connected induced subgraphs (or graphlets) of rooted, bounded degree graphs. Our algorithm utilizes a vertex-percolation process with a carefully chosen rejection filter and works under a percolation subcriticality condition. We show that this condition is optimal in the sense that the task of (approximately) sampling weighted rooted graphlets becomes impossible in finite expected time for infinite graphs and intractable for finite graphs when the condition does not hold. We apply our sampling algorithm as a subroutine to give near linear-time perfect sampling algorithms for polymer models and weighted non-rooted graphlets in finite graphs, two widely studied yet very different problems. This new perfect sampling algorithm for polymer models gives improved sampling algorithms for spin systems at low temperatures on expander graphs and unbalanced bipartite graphs, among other applications.
UR - http://www.scopus.com/inward/record.url?scp=85139157434&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85139157434&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.APPROX/RANDOM.2022.4
DO - 10.4230/LIPIcs.APPROX/RANDOM.2022.4
M3 - Conference contribution
AN - SCOPUS:85139157434
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2022
A2 - Chakrabarti, Amit
A2 - Swamy, Chaitanya
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 25th International Conference on Approximation Algorithms for Combinatorial Optimization Problems and the 26th International Conference on Randomization and Computation, APPROX/RANDOM 2022
Y2 - 19 September 2022 through 21 September 2022
ER -