Variable entropy-based warning propagation algorithm for solving minimum cut problem

doi:10.11772/j.issn.1001-9081.2025070904

Journal of Computer Applications ›› 2026, Vol. 46 ›› Issue (9): 2931-2937.DOI: 10.11772/j.issn.1001-9081.2025070904

• Advanced computing • Previous Articles

Variable entropy-based warning propagation algorithm for solving minimum cut problem

Simin HU¹, Xiaofeng WANG¹^,², Hongsheng DING¹(), Jiahuan SONG¹, Xiaona SUO¹, Dong YAN¹

^1.School of Computer Science and Engineering，North Minzu University，Yinchuan Ningxia 750021，China
^2.Key Laboratory of Image and Graphics Intelligent Processing of State Ethnic Affairs Commission，（North Minzu University），Yinchuan Ningxia 750021，China

Received:2025-08-11 Revised:2025-09-11 Accepted:2025-09-12 Online:2025-11-05 Published:2026-09-10
Contact: Hongsheng DING
About author:HU Simin， born in 1996， M. S. candidate. Her research interests include algorithm analysis and design.
WANG Xiaofeng， born in 1980， Ph. D.， associate professor. His research interests include machine learning， artificial intelligence.
DING Hongsheng， born in 1977， M. S.， associate professor. His research interests include computer organization and architecture.
SONG Jiahuan， born in 2001， M. S. candidate. His research interests include algorithm analysis and design.
SUO Xiaona， born in 1998， M. S. candidate. Her research interests include algorithm analysis and design.
YAN Dong， born in 1999， M. S. candidate. His research interests include algorithm analysis and design.
Supported by:
Natural Science Foundation of Ningxia(2024AAC03165);Ningxia Youth Top Talent Project(2021)

基于变量熵的警示传播算法求解最小割问题

胡思敏¹, 王晓峰¹^,², 丁红胜¹(), 宋家欢¹, 锁小娜¹, 颜冬¹

^1.北方民族大学计算机科学与工程学院，银川 750021
^2.图像图形智能处理国家民委重点实验室（北方民族大学），银川 750021

通讯作者: 丁红胜
作者简介:胡思敏（1996—），女，陕西西安人，硕士研究生，CCF会员，主要研究方向：算法分析与设计
王晓峰（1980—），男（回族），甘肃会宁人，副教授，博士，CCF会员，主要研究方向：机器学习、人工智能
丁红胜（1977—），男，甘肃甘谷人，副教授，硕士，主要研究方向：计算机组织与结构
宋家欢（2001—），男（满族），河北承德人，硕士研究生，CCF会员，主要研究方向：算法分析与设计
锁小娜（1998—），女（回族），宁夏吴忠人，硕士研究生，CCF会员，主要研究方向：算法分析与设计
颜冬（1999—），男（满族），辽宁本溪人，硕士研究生，CCF会员，主要研究方向：算法分析与设计。
基金资助:
宁夏自然科学基金资助项目(2024AAC03165);宁夏青年拔尖人才项目(2021)

Abstract

Abstract:

The Minimum Cut Problem （MCP） is a classic NP （Nondeterministic Polynomial） -hard problem with broad applications in image segmentation and network reliability analysis. Warning Propagation （WP） algorithm， a factor graph-based inference method， has shown good scalability and structural adaptability when solving combinatorial optimization problems. However， its effectiveness on MCP is limited by path selection， factor graph construction， and convergence. Therefore， an Entropy-based Warning Propagation （EWP） algorithm was proposed to solve MCP. First， a Hidden Markov Model （HMM） -driven jump-point mechanism was introduced to select core propagation regions. At the same time， a batch-mapping factor graph transformation way was employed to reduce graph structural dimensionality effectively. Finally， a propagation freezing strategy that combined marginal probability and variable entropy was adopted to accelerate convergence. Experimental results demonstrate that EWP achieves good performance on graphs with different sizes， and especially has significant potential in large-scale graph optimization problems.

Key words: Minimum Cut Problem (MCP), Warning Propagation (WP) algorithm, Hidden Markov Model (HMM), factor graph, variable entropy

摘要：

最小割问题（MCP）是图论中的经典NP（Nondeterministic Polynomial）-难问题，在图像分割和网络可靠性分析等方面具有广泛应用。警示传播（WP）算法作为基于因子图的推理方法，在求解组合优化问题时表现出较强的可扩展性与结构适应能力；然而，该算法在求解MCP时，它的传播路径选择、因子图构建和收敛性方面仍存在不足。为此，提出一种基于变量熵的警示传播（EWP）算法求解MCP。首先，通过引入基于隐马尔可夫模型（HMM）驱动的跳点机制选取核心传播区域；同时，利用批量映射的因子图转换方式有效压缩图结构的维度；最后，结合边缘概率与变量熵的冻结传播策略，引导信息传播过程更快地收敛。实验结果表明，EWP算法在多种图规模中表现出良好性能，尤其在大规模图优化问题中具有较大的应用潜力。

关键词: 最小割问题, 警示传播算法, 隐马尔可夫模型, 因子图, 变量熵

CLC Number:

TP301.6

Simin HU, Xiaofeng WANG, Hongsheng DING, Jiahuan SONG, Xiaona SUO, Dong YAN. Variable entropy-based warning propagation algorithm for solving minimum cut problem[J]. Journal of Computer Applications, 2026, 46(9): 2931-2937.

胡思敏, 王晓峰, 丁红胜, 宋家欢, 锁小娜, 颜冬. 基于变量熵的警示传播算法求解最小割问题[J]. 《计算机应用》唯一官方网站, 2026, 46(9): 2931-2937.

Figures/Tables 8

Fig. 1 Instances of minimum cut problem

Fig. 2 Process of converting undirected graph into factor graph

Tab. 1 Random graph parameters with different numbers of nodes

n	m	α
10	30	3.0
20	50	2.5
50	115	2.3
100	240	2.4
200	520	2.6
500	1 050	2.1

Fig. 3 Convergence probability of EWP algorithm with different n

Fig. 4 Comparison of convergence probability between WP and EWP algorithms with n=10

Fig. 5 Factor graph conversion time of EWP algorithm with different n

Tab. 2 Comparison of solution time for different algorithms

n	不同算法的求解时间/ms
n	D算法	WP算法	EWP算法
100	0.01	0.39	0.02
200	0.07	0.41	0.09
300	0.14	0.35	0.16
400	0.27	0.30	0.20
500	0.33	0.29	0.21
600	0.35	0.29	0.22

Fig. 6 Comparison of running time of different algorithms under different node sizes

References 44

[1]	Boykov Y， Veksler O， Zabih R. Fast approximate energy minimization via graph cuts ［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2001， 23（11）： 1222-1239.
[2]	Boykov Y， Funka-Lea G. Graph cuts and efficient ND image segmentation ［J］. International Journal of Computer Vision， 2006， 70（2）： 109-131.
[3]	Ramesh V， Nagarajan S， Jung J J， et al. Max-flow min-cut algorithm with application to road networks ［J］. Concurrency and Computation： Practice and Experience， 2017， 29（11）： No.e4099.
[4]	Caccetta L， Hill S P. An application of branch and cut to open pit mine scheduling ［J］. Journal of Global Optimization， 2003， 27（2/3）： 349-365.
[5]	Karger D R. A randomized fully polynomial time approximation scheme for the all terminal network reliability problem ［C］// STOC 1995. New York： ACM， 1995： 11-17.
[6]	Ramanathan A， Colbourn C J. Counting almost minimum cutsets with reliability applications ［J］. Mathematical Programming， 1987， 39（3）： 253-261.
[7]	Botafogo R A. Cluster analysis for hypertext systems ［C］// SIGIR 1993. New York： ACM， 1993： 116-125.
[8]	Chatterjee S， Gilbert J R， Schreiber R， et al. Array distribution in data-parallel programs ［C］// LCP 1995. Berlin： Springer， 1995： 76-91.
[9]	Griffing A R， Lynch B R， Stone E A. Structural properties of the minimum cut of partially-supplied graphs ［J］. Discrete Applied Mathematics， 2014， 177： 152-157.
[10]	Abdolahzadeh A， Aman M， Tayyebi J. Minimum st-cut interdiction problem ［J］. Computers and Industrial Engineering， 2020， 148： No.106708.
[11]	Fox K， Panigrahi D， Zhang F. Minimum cut and minimum k-cut in hypergraphs via branching contractions ［C］// SODA 2019. Philadelphia， PA： SIAM， 2019： 881-896.
[12]	Karger D R， Stein C. A new approach to the minimum cut problem ［J］. Journal of the ACM， 1996， 43（4）： 601-640.
[13]	Ghaffari M， Nowicki K. Massively parallel algorithms for minimum cut ［C］// PODC 2020. New York： ACM， 2020： 119-128.
[14]	Mukhopadhyay S， Nanongkai D. Weighted min-cut： sequential， cut-query， and streaming algorithms ［C］// STOC 2020. New York： ACM， 2020： 496-509.
[15]	Gawrychowski P， Mozes S， Weimann O. A note on a recent algorithm for minimum cut ［C］// SOSA 2021. Philadelphia， PA： SIAM， 2021： 74-79.
[16]	Beideman C， Chandrasekaran K， Wang W. Approximate minimum cuts and their enumeration ［C］// SOSA 2023. Philadelphia， PA： SIAM， 2023： 36-41.
[17]	Aissi H， Mahjoub A R. On the minimum s-t cut problem with budget constraints ［J］. Mathematical Programming， 2024， 203（1/2）： 421-442.
[18]	Wei W， Liu Y， Zhang Q. An optimal pruned traversal tree-based fast minimum cut solver in dense graph ［J］. Information Sciences， 2024， 652： No.119768.
[19]	Niaparast H， Moseley B， Singh K. Faster global minimum cut with predictions ［C］// ICML 2025. New York： JMLR.org， 2025： 46305-46319.
[20]	Kenneth-Mordoch Y， Krauthgamer R. Cut-query algorithms with few rounds ［C］// ESA 2025. Wadern： Leibniz-Zentrum für Informatik， 2025： No.100.
[21]	Braunstein A， Mézard M， Zecchina R. Survey propagation： an algorithm for satisfiability ［J］. Random Structures and Algorithms， 2005， 27（2）： 201-226.
[22]	王晓峰，许道云.警示传播算法收敛的充分条件［J］.软件学报， 2016， 27（12）： 3003-3013.
	Wang Xiaofeng， Xu Daoyun. Sufficient conditions for convergence of the warning propagation algorithm ［J］. Journal of Software， 2016， 27（12）： 3003-3013.
[23]	Cooley O， Lee J， Ravelomanana J B. Warning Propagation： stability and subcriticality ［PP/OL］. V2. arXiv （2024-05-24）［2025-08-20］. .
[24]	王辛，王晓峰，李卫民.一种求解最小割的警示传播算法［J］.电子学报， 2019， 47（11）： 2386-2391.
	Wang Xin， Wang Xiaofeng， Li Weiming. A warning propagation algorithm for solving minimum cut ［J］. Acta Electronica Sinica， 2019， 47（11）： 2386-2391.
[25]	Loeliger H A. An introduction to factor graphs ［J］. IEEE Signal Processing Magazine， 2004， 21（1）： 28-41.
[26]	Kschischang F R， Frey B J， Loeliger H A. Factor graphs and the sum-product algorithm ［J］. IEEE Transactions on Information Theory， 2001， 47（2）： 498-519.
[27]	Feige U， Mossel E， Vilenchik D. Complete convergence of message passing algorithms for some satisfiability problems ［J］. Theory of Computing， 2013， 9（19）： 617-651.
[28]	Shannon C E. A mathematical theory of communication ［J］. The Bell System Technical Journal， 1948， 27（3）： 379-423.
[29]	Cover T M， Thomas J A. Elements of information theory ［M］. New York： John Wiley & Sons， 1991.
[30]	Peng H， Long F， Ding C. Feature selection based on mutual information criteria of max-dependency， max-relevance， and min-redundancy ［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2005， 27（8）： 1226-1238.
[31]	Jaynes E T. Information theory and statistical mechanics ［J］. Physical Review， 1957， 106（4）： No.620.
[32]	Quinlan J R. Induction of decision trees ［J］. Machine Learning， 1986， 1（1）： 81-106.
[33]	Eddy S R. Hidden Markov models ［J］. Current Opinion in Structural Biology， 1996， 6（3）： 361-365.
[34]	Xu K， Li C， Tian Y， et al. Representation learning on graphs with jumping knowledge networks ［C］// ICML 2018. New York： JMLR.org， 2018： 5453-5462.
[35]	Harabor D， Grastien A. Online graph pruning for pathfinding on grid maps ［C］// AAAI 2011. Palo Alto： AAAI Press， 2011： 1114-1119.
[36]	Hamilton W L， Ying R， Leskovec J. Inductive representation learning on large graphs ［C］// NeurIPS 2017. Red Hook： Curran Associates Inc.， 2017： 1025-1035.
[37]	Shervashidze N， Schweitzer P， van Leeuwen E J， et al. Weisfeiler-Lehman graph kernels ［J］. Journal of Machine Learning Research， 2011， 12： 2539-2561.
[38]	Wainwright M J， Jordan M I. Graphical models， exponential families， and variational inference ［J］. Foundations and Trends in Machine Learning， 2008， 1（1/2）： 1-305.
[39]	Goodfellow I， Bengio Y， Courville A， et al. Deep learning ［M］. Cambridge： MIT Press， 2016.
[40]	Hoshino E A. The minimum cut cover problem ［J］. Electronic Notes in Discrete Mathematics， 2011， 37： 255-260.
[41]	Liberti L， Alfandari L， Plateau M C. Edge cover by connected bipartite subgraphs ［J］. Annals of Operations Research， 2011， 188（1）： 307-329.
[42]	Stoer M， Wagner F. A simple min-cut algorithm ［J］. Journal of the ACM， 1997， 44（4）： 585-591.
[43]	Karger D R. Global min-cuts in RNC， and other ramifications of a simple min-cut algorithm ［C］// SODA 1993. Philadelphia， PA： SIAM， 1993： 21-30.
[44]	Bhardwaj N， Lovett A J M， Sandlund B. A simple algorithm for minimum cuts in near-linear time ［C］// SWAT 2025. Wadern： Leibniz-Zentrum für Informatik， 2025： No.12.

Variable entropy-based warning propagation algorithm for solving minimum cut problem

基于变量熵的警示传播算法求解最小割问题

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 8

References 44

Related Articles 15

Recommended Articles

Metrics

[1]	Hao GAO, Qingke ZHANG, Xianglong BU, Junqing LI, Huaxiang ZHANG. Teaching-learning-based optimization algorithm based on cooperative mutation and Lévy flight strategy and its application [J]. Journal of Computer Applications, 2023, 43(5): 1355-1364.
[2]	HUO Weigang, WANG Huifang. Time series anomaly detection method based on autoencoder and HMM [J]. Journal of Computer Applications, 2020, 40(5): 1329-1334.
[3]	LI Tianzheng, WANG Chuntao. Lossy compression algorithm for encrypted binary images using Markov random field [J]. Journal of Computer Applications, 2020, 40(5): 1354-1363.
[4]	WU Wanting, ZHU Yan, HUANG Dingjiang. Semi-exponential gradient strategy and empirical analysis for online portfolio selection [J]. Journal of Computer Applications, 2019, 39(8): 2462-2467.
[5]	WANG Jince, DENG Yueping, SHI Ming, ZHOU Yunfei. Time series trend prediction at multiple time scales [J]. Journal of Computer Applications, 2019, 39(4): 1046-1052.
[6]	YANG Shiqiang, LUO Xiaoyu, QIAO Dan, LIU Peilei, LI Dexin. Continuous action segmentation and recognition based on sliding window and dynamic programming [J]. Journal of Computer Applications, 2019, 39(2): 348-353.
[7]	GAO Junqiang, TANG Xiaqing, ZHANG Huan, GUO Libin. Processing method of INS/GPS information delay based on factor graph algorithm [J]. Journal of Computer Applications, 2018, 38(11): 3342-3347.
[8]	GUO Leiyong, LI Yu, LIN Shengyi, TAN Hongzhou. Excitation piecewise expansion method for speech bandwidth expansion based on hidden Markov model [J]. Journal of Computer Applications, 2017, 37(8): 2416-2420.
[9]	CUI Jianhua, WANG Zhongyong, ZHANG Chuanzong, ZHANG Yuanyuan. Localization algorithm based on factor graph and hybrid message passing for wireless networks [J]. Journal of Computer Applications, 2017, 37(5): 1306-1310.
[10]	LI Fangwei, LI Qi, ZHU Jiang. Improved method of situation assessment method based on hidden Markov model [J]. Journal of Computer Applications, 2017, 37(5): 1331-1334.
[11]	WANG Dongli, CAO Peng, HUANG Guoce, SUN Qilu, LI Lianbao. High frequency cognitive frequency selection mechanism based on hidden Markov model [J]. Journal of Computer Applications, 2016, 36(5): 1179-1182.
[12]	LI Qiang, CHEN Hao, CHEN Dingdang. Voice activity detection algorithm based on hidden Markov model [J]. Journal of Computer Applications, 2016, 36(11): 3212-3216.
[13]	YAN Bin JIA Xia WANG Xiaoming GUO Yinjing HAO Jianjun. Joint estimation-decoding approach based on factor graph expectation maximization algorithm over correlated block fading channels [J]. Journal of Computer Applications, 2013, 33(03): 607-610.
[14]	LIU Wei LI He-cheng. Uighur characters recognition based on locality preserving projection and hidden Markov model [J]. Journal of Computer Applications, 2012, 32(08): 2309-2312.
[15]	WEN Kai GUO Fan YU Min. Adaptive anomaly detection method of Web-based attacks [J]. Journal of Computer Applications, 2012, 32(07): 2003-2006.