摘要: 一个图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公式的因子图树分解。通过实验观察公式因子图的树宽度与求解难度之间的联系。
中图分类号:
[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. |
|