Research On Constraint Solving Symbolic Algorithm For Subgraph Isomorphic Based On Tree Decomposition Technique

Subgraph isomorphism,as a query technique in graph databases,is widely used in fields such as computer vision,social network analysis,and biochemical analysis.Subgraph isomorphism is an NP-complete problem,and as the size of the graph increases,the time and space complexity of the algorithm grows exponentially.Improving candidate set filtering techniques,reducing memory computing space,and reducing the problem-solving scale are effective ways to improve the efficiency of subgraph isomorphism solutions.Constraint satisfaction problems are a general framework for solving combinatorial optimization problems.By using constraint propagation and decomposition techniques,they can reduce the matching candidate set and lower the problem-solving scale.By combining symbolic techniques,they can use the compactness and ease of operation of algebraic decision diagrams to reduce memory consumption and mitigate combinatorial explosions.Symbolic operations have parallelism and can effectively accelerate computation.Therefore,this article combines constraint solving techniques and symbolic techniques to study the problem of subgraph isomorphism,and the main research content and conclusions are as follows:(1)In order to describe the problem of subgraph isomorphism,this article combines constraint solving techniques and symbolic techniques to propose a new constraint symbolic model for the problem of subgraph isomorphism.Firstly,pseudo-Boolean functions are used to formally describe the various elements of the new model,and then the model is compressed and stored using the ADD data structure.Compared with traditional constraint models,this model has better applicability and compactness.(2)In order to improve the filtering effect of the candidate set,based on the constraint symbolic model of subgraph isomorphism,the article studies the all-different constraint and proposes a generalized arc consistency symbolic algorithm for the all-different constraint,which preliminarily reduces the range of values,and optimizes the algorithm by proposing a redundant edge filtering algorithm and a trivial SCC pruning algorithm to speed up computation.At the same time,by mining the structure and attribute information of the graph,a neighborhood label constraint filtering algorithm is proposed,which effectively reduces the range of values.Then,combined with the propagation algorithm of the all-different constraint,the value range of variables is further filtered.(3)In order to mitigate the combinatorial explosion of states,the article adopts the idea of divide and conquer,and combines the tree decomposition algorithm to decompose the original CSP problem into multiple subproblems,limiting the problem-solving scale and reducing the difficulty of problem solving.The symbolic tree decomposition algorithm is improved by introducing a priority function to improve parallelism and accelerate computation.Finally,the non-backtracking tree search algorithm is used to solve and combine subproblems to obtain the solution of the original problem.(4)In order to verify the effectiveness of the algorithm,all symbolic algorithms are implemented using the CUDD software package,and extensive experiments and comparisons are conducted on random test instances and publicly available benchmark datasets.The experimental results show that the algorithm proposed in this article improves the time and space efficiency of subgraph isomorphism solution.