Rapid Mixing of Subset Glauber Dynamics on Graphs of Bounded Tree-Width

被引：0
作者：
Bordewich, Magnus [1 ]
Kang, Ross J. [1 ]
机构：
[1] Univ Durham, Durham, England
来源：
AUTOMATA, LANGUAGES AND PROGRAMMING, ICALP, PT I | 2011年 / 6755卷
基金：
英国工程与自然科学研究理事会;
关键词：
Markov chain Monte Carlo; graph polynomials; subset expansion; tree-width; canonical paths; randomised approximation schemes; rapid mixing; MARKOV-CHAINS; TIME; POLYNOMIALS; INVARIANTS; MODELS; NUMBER;
D O I：
暂无
中图分类号：
TP31 [计算机软件];
学科分类号：
081202 ; 0835 ;
摘要：
Motivated by the 'subgraphs world' view of the ferromagnetic Ising model, we develop a general approach to studying mixing times of Glauber dynamics based on subset expansion expressions for a class of graph polynomials. With a canonical paths argument, we demonstrate that the chains defined within this framework mix rapidly upon graphs of bounded tree-width. This extends known results on rapid mixing for the Tutte polynomial, the adjacency-rank (R-2-)polynomial and the interlace polynomial.
引用
收藏
页码：533 / 544
页数：12
相关论文
共 46 条
[31]   Learning Bayesian Networks with Bounded Tree-Width via Guided Search [J].
Nie, Siqi ;
de Campos, Cassio P. ;
Ji, Qiang .
THIRTIETH AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE, 2016, :3294-3300
[32]   Farrell polynomials on graphs of bounded tree width [J].
Makowsky, JA ;
Mariño, JP .
ADVANCES IN APPLIED MATHEMATICS, 2003, 30 (1-2) :160-176
[33]   Canonizing Graphs of Bounded Tree Width in Logspace [J].
Elberfeld, Michael ;
Schweitzer, Pascal .
33RD SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2016), 2016, 47
[34]   Tree-width of graphs without a 3 x 3 grid minor [J].
Birmele, E. ;
Bondy, J. A. ;
Reed, B. A. .
DISCRETE APPLIED MATHEMATICS, 2009, 157 (12) :2577-2596
[35]   Almost Linear Time Computation of the Chromatic Polynomial of a Graph of Bounded Tree-Width [J].
Fuerer, Martin .
LATIN 2010: THEORETICAL INFORMATICS, 2010, 6034 :49-59
[36]   Learning Bounded Tree-width Bayesian Networks using Integer Linear Programming [J].
Parviainen, Pekka ;
Farahani, Hossein Shahrabi ;
Lagergren, Jens .
ARTIFICIAL INTELLIGENCE AND STATISTICS, VOL 33, 2014, 33 :751-759
[37]   A Note on Total and List Edge-Colouring of Graphs of Tree-Width 3 [J].
Lang, Richard .
GRAPHS AND COMBINATORICS, 2016, 32 (03) :1055-1064
[38]   Vertex partitioning problems on graphs with bounded tree width [J].
Aravind, N. R. ;
Kalyanasundaram, Subrahmanyam ;
Kare, Anjeneya Swami .
DISCRETE APPLIED MATHEMATICS, 2022, 319 :254-270
[39]   Rapid mixing of Glauber dynamics via spectral independence for all degrees [J].
Chen, Xiaoyu ;
Feng, Weiming ;
Yin, Yitong ;
Zhang, Xinyuan .
2021 IEEE 62ND ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS 2021), 2022, :137-148
[40]   An Improved Isomorphism Test for Bounded-tree-width Graphs [J].
Grohe, Martin ;
Neuen, Daniel ;
Schweitzer, Pascal ;
Wiebking, Daniel .
ACM TRANSACTIONS ON ALGORITHMS, 2020, 16 (03)
12345