The Estimation And Application Of Treewidth

Let G=(V,E)be a graph,where V is the vertex set and E(?)(?)is the edge set.Hypergraph H=(V(H),E(H))is the generalization of the graph,where E(H)(?)2V(H)is the hyperedge set.The treewidth tw(G)of G is the minimum width of the tree decompositions of G.The treewidth of a graph is an important invariant in structural and algorithmic graph theory.Treewidth is commonly used as a parameter in the parameterized complexity analysis of graph algorithms,since many NP-complete problems can be solved in polynomial time on graphs of bounded treewidth.However,the problem of deciding whether a graph has a tree decomposition of width at most k is NP-complete.Therefore,one of the major problems in studying treewidth is to determine the exact value or the lower and upper bounds of the treewidth of some specific graphs.The main results of this thesis are as follows:1.We give the exact value of treewidth of the generalized Kneser graphs K(n,k,t)for t? 2 and large n with respect to k and t.In the special case when t=k-1,the graph K(n,k,k-1)usually denoted by J(n,k)which is the complement of the Johnson graph J(n,k).We give a more precise result for the exact value of the treewidth of J(n,k)for any n and k.Furthermore,using the well-known Erd(?)sKo-Rado Theorem we give the tree decomposition of K(n,k,t)for above cases.2.We use the minimum degree,maximum degree,minimum rank and average rank of a linear hypergraph H to determine the lower bounds of the treewidth of its 2-section[H]2.We give a new definition of decomposition of a hypergraph which is called a supertree decomposition of a hypergraph,and use it to give an upper bound of tw([H]2).These above bounds are all precisely sharp or almost precisely sharp.3.We propose the concept of the Complete-Subgraph problem.And on graphs of bounded treewidth,we solve the Complete-Subgraph-Transversal-Set problem,the Complete-Subgraph-Coloring problem,and the Complete-Subgraph-CountingPerfect-Matching problem.Here is an example about the Complete-SubgraphTransversal-Set problem.When we let the complete subgraph set be all the cliques,edges,and all the complete subgraphs in 2-section corresponding to a hyperedges of a given hypergraph respectively,we can correspondingly obtain the parameterized algorithms to the Clique-Transversal-Set problem,Vertex Cover problem and that on hypergraph.4.We use the Fast Set Convolution method to give an parameterized algorithm to the w-Dominating-Set problem and optimize the complexity of the algorithm to the Complete-Subgraph-Counting-Perfect-Matching problem.