计算机科学 ›› 2020, Vol. 47 ›› Issue (5): 51-58.doi: 10.11896/jsjkx.191100118

所属专题: 理论计算机科学

• 理论计算机科学 • 上一篇    下一篇

图的树分解算法及其应用

雷莹, 许道云   

  1. 贵州大学计算机科学与技术学院 贵阳550025
  • 收稿日期:2019-11-15 出版日期:2020-05-15 发布日期:2020-05-19
  • 通讯作者: 许道云(dyxu@gzu.edu.cn)
  • 作者简介:1152586591@qq.com
  • 基金资助:
    国家自然科学基金(61762019,61862051)

Tree Decomposition Algorithm of Graph and Its Application

LEI Ying, XU Dao-yun   

  1. College of Computer Science and Technology,Guizhou University,Guiyang 550025,China
  • Received:2019-11-15 Online:2020-05-15 Published:2020-05-19
  • About author:LEI Ying,born in 1992,postgraduate,is a member of China Computer Federation.Her main research interest is include algorithm design and analysis.
    XU Dao-yun,born in 1959,professor,Ph.D supervisor,is a senior member of China Computer Federation.His main research interests include computability and computational complexity.
  • Supported by:
    This work was supported by the National Natural Science Foundation of China(61762019, 61862051)

摘要: 一个图G=(V,E)的树分解是将结点集V的子集作为树T的节点,使得在T上任意一条路径上的两个端节点的交集包含于该路径上的任意一个节点中。将T上最小(节点)对应子集的元素个数减1定义为分解树T的宽度,用宽度最小的分解树T的树宽度定义图G的树宽度。一个合取范式(Conjunctive Normal Form,CNF)公式F可以用一个二分图G=(V∪C,E)表示(公式的因子图),其中变元结点集V对应公式F中的变元集,子句结点集C对应公式F中的子句集,变元在子句中的正(负)出现用实(虚)边表示。 忽略公式因子图中边上的符号,得到一个二分图。文中研究了图的树分解算法,并将树分解算法应用到CNF公式的因子图树分解。通过实验观察公式因子图的树宽度与求解难度之间的联系。

关键词: CNF公式, 求解难度, 树分解, 树宽度

Abstract: A tree decomposition of the graph G=(V,E) refers to taking a subset of the node set V as a node of the tree T,to make the intersection of the two endpoints on any path of T included in any node on the path.The number of elements of the mini-mum (node) corresponding subset on T minus 1 is defined as the width of the decomposition tree T,and the tree width of the graph G is defined by the tree width of the decomposition tree T with the smallest width.The CNF formula F can be represented by a bipartite graph G=(V∪C,E) (factor graph of the formula),where the variable node set V corresponds to the variable set,and the clause node set C corresponds to the clause set in the formula F.The positive (negative) occurrence of the element in the clause is represented by the real (virtual) side.In order to study the bipartite graph,the symbols on the edges of the formula factor graph are ignored.This paper studies the tree decomposition algorithm of graphs and applies the tree decomposition algorithm to the factor graph tree decomposition of CNF formula,aiming to explore the relationship between the tree width of the formula factor graph and the difficulty of the solution-finding through experiments.

Key words: CNF formula, Difficulty of solution-finding, Tree decomposition, Tree width

中图分类号: 

  • TP301
[1]BODLAENDER H L,KOSTER A M C A.Treewidth computations II.Lower bounds[J].Information and Computation,2011,209(7):1103-1119.
[2]HAMMERL T,MUSLIU N,SCHAFHAUSER W.Metaheuristic algorithms and tree decomposition[M]//Springer Handbook of Computational Intelligence.Berlin:Springer,2015:1255-1270.
[3]BODLAENDER H L.A linear-time algorithm for finding tree-decompositions of small treewidth[J].SIAM Journal on Computing,1996,25(6):1305-1317.
[4]COOK S A.The complexity of theorem-proving procedures[C]//Proceedings of the Third Annual ACM Symposium on Theory of Computing.ACM,1971:151-158.
[5]ABSEHER M,DUSBERGER F.Improving the efficiency of dynamic program ming on tree decompositions via machine learning[J].Journal of Artificial IntelliIgence Research,2017,58:829-858.
[6]TELLE J A,ROSKUROWSKI A.Algorithms for vertex partitioning problems on partial k-trees[J].SIAM Journal on Discrete Mathematics,1997,10(4)529-550.
[7]BLIEM B,MOLDOVAN M.The Impact of Treewidth on ASP Grounding and Solving[C]//Twenty-sixth International Joint Conference on Artificial Intelligence.Melbourne,Australia,2017:852-858.
[8]ZHANG N L.Computational properties of two exact algorithms for Bayesian networks[J].Applied Intelligence,1998,9(2):173-183.
[9]DUBOIS O,MONASSON R,SELMAN B,et al.Phase transitions in combinatorial problems[J].Theoretical Computer Science,2001(265):1-2.
[10]XU K,LI W.Exact phase transitions in random constraint satisfaction problems[J].Journal of Artificial Intelligence Research,2000,12(1):93-103.
[11]SZEIDER S.Generalizations of matched CNF formulas[J].Annals of Mathematics and Artificial Intelligence,2005,43(1/2/3/4):223-238.
[12]SZEIDER S.Matched formulas and backdoor sets[C]//Interna-tional Conference on Theory and Applications of Satisfiability Testing.Berlin:Springer,2007:94-99.
[13]SURYNEK P.Compact representations of cooperative path-finding as SAT based on matchings in bipartite graphs[C]//2014 IEEE 26th International Conference on Tools with Artificial Intelligence.IEEE,2014:875-882.
[14]XU D Y,WANG X F.A Regular NP-Complete problem and its inapproximability[J].Journal of Frontiers of Computer Science and Technology,2013,7(8):691-697.
[15]KRISHNAMURTHY S,SAHOO S.Balanced k-satisfiabilityand biased random k-satisfiability on trees[J].Physical Review E,2013,87(4):042130.
[16]CHEN J.Parameterized Computation and Complexity:A NewApproach Dealing with NP-Hardness[J].Journal of Computer Science and Technology,2005,20(1):18-25.
[17]RAIBLE D,FERNAU H.A new upper bound for Max-2-SAT:A graph-theoretic approach[C]//International Symposium on Mathematical Foundations of Computer Science.Berlin:Springer,2008(8):551-562.
[18]ROBERTSON N,SEYMOUR P D.Graph minors.X.Obstructions to tree-decomposition[J].Journal of Combinatorial Theory(Series B),1991,52(2):153-190.
[19]GOTTLOB G,LEONE N,SCARCELLO F.A comparison ofstructural CSP decomposition methods[J].Artificial Intelligence,2000,124(2):243-282.
[20]CHEN H B.Quantified Constraint Satisfaction and BoundedTreewidth.[C]// Eureopean Conference on Artificial Intelligence.DBLP,2004:161-165.
[21]BORDEAUX L,CADOLI M,MANCINI T.CSP properties for quantified constraints:Definitions and complexity[C]//AAAI.2005:360-365.
[22]WANG X F,XU D Y,WEI L.Convergence of Warning Propagation Algorithms for Random Satisfiable Instances[J].Journal of Software,2013,24(1):1-11.
[23]XU D Y,DENG T Y,ZHANG Q S.k-LSAT is NP-Complete for k≥3[J].Journal of Software,2008(3):511-521.
[24]PORSCHEN S,SPECKENMEYER E,RANDERATH B.Onlinear CNF formulas[M]//Proc.of the 19th Int'l Conf.on Theory and Applications of Satisfiability Testing-SAT 2006.New York:Springer-Verlag,2006:212-225.
[25]PORSCHEN S,SPECKENMEYER E.NP-Completeness ofSAT for restricted linear formulas classes[C]//Proc.of the Guangzhou Symp.& On Satisfiability in Logic-Based Modeling.2006:111-123.
[1] 何彬, 许道云.
正则(3,4)-CNF公式的社区结构
Community Structure of Regular (3,4)-CNF Formula
计算机科学, 2021, 48(4): 26-30. https://doi.org/10.11896/jsjkx.201000178
[2] 宋俊花, 魏欧.
基于线性时间算法的故障树模块扩展分解方法
Fault Tree Module Expansion Decomposition Method Based on Liner-time Algorithm
计算机科学, 2019, 46(1): 226-231. https://doi.org/10.11896/j.issn.1002-137X.2019.01.035
[3] 宋景琦,刘慧,张彩明.
基于自适应块聚类的医学图像超分辨重建
Medical Image Super Resolution Reconstruction Based on Adaptive Patch Clustering
计算机科学, 2016, 43(Z11): 210-214. https://doi.org/10.11896/j.issn.1002-137X.2016.11A.048
[4] 张明明,许道云.
正则3-SAT问题的相变现象
Phase Transition Phenomenon of Regular 3-SAT Problem
计算机科学, 2016, 43(4): 33-36. https://doi.org/10.11896/j.issn.1002-137X.2016.04.006
[5] 高文宇,李绍华.
图的树分解及其算法应用研究进展
Tree Decomposition and its Applications in Algorithms:Survey
计算机科学, 2012, 39(3): 14-18.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!