设 $G=(V,E)$ 是一个图, 其中 $V$ 是有限的顶点集, 边集 $E$ 为 $V$ 的某些二元子集构成的集族. 超图 $H=(V,E)$ 是图的推广, 边集为 $V$ 的某些子集构成的集族. 图的树宽定义为其树分解宽度的最小值.树宽是算法图论和结构图论中的重要参数. 许多 NP-完全问题在将树宽作为参数的条件下，是可以多项式时间求解的. 然而判定任意图的树宽是否小于等于 $k$ 被证明是 NP-完全问题. 因此确定特殊图类树宽的精确值或上下界就显得尤为重要.本文的主要研究成果如下：1. 对广义 Kneser 图 $K(n,k,t)$, 在 $n,k,t$ 满足一定条件时, 我们证明了其树宽的精确值； 对 $t=k-1$ 时, 我们给出了全部的 $n,k$ 关系下 $K(n,k,k-1)$ 的精确值. 并且根据 著名的 Erd\H{o}s-Ko-Rado 定理给出了广义 Kneser 图树宽取到精确值的树分解.2. 对线性超图 $H$ 的二截口图类 $[H]_2$, 我们分别给出了以 $H$ 的平均秩, 最小秩作为主项的下界. 前者为差 1 紧的, 后者为紧的. 我们提出了超树宽的概念, 并给出了 $[H]_2$ 的树宽关于 $H$ 的超树宽的上界, 此界也是紧的.3. 我们提出了完全子图类问题的概念, 并在树宽有界的条件下, 给出了完全子图覆盖问题、完全子图染色问题和完全子图完美匹配计数问题的参数化算法. 以完全子图覆盖问题为例, 当取完全子图集分别为所有的团、边集和超边在其二截口中对应的完全子图时, 我们可以对应地得到团覆盖问题, 图的顶点覆盖问题和超图的顶点覆盖问题的参数化算法.4.在树宽有界的条件下, 使用快速集合卷积, 给出了 $w$-控制集问题的参数化算法, 并改进了完全子图完美匹配计数问题的复杂度.

Let $G=(V,E)$ be a graph, where $V$ is the vertex set and $E\subseteq {V\choose 2}$ is the edge set. Hypergraph $H=(V(H),E(H))$ is the generalization of the graph, where $E(H) \subseteq 2^{V(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 solvable in polynomial time on graphs of bounded treewidth. However, the problem of deciding whether a graph has tree decomposition of treewidth at most $k$ is NP-complete. Therefore, one of the major problems in studying of 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\geq2$ 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 $\overline{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 $\overline{J(n,k)}$ for any $n$ and $k$. Furthermore, assisting of the well-known Erd\H{o}s-Ko-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-Counting-Perfect-Matching problem. Here is an example about the Complete-Subgraph-Transversal-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.