Files
Abstract
Many intractable problems on graphs are polynomial time solvable when the graphs have bounded treewidth. An important class of the graphs with bounded treewidth is called k-trees, which are formed by starting with a k-clique and then repeatedly adding vertices in such a way that each added vertex has exactly k neighbors that form a new clique. Finding spanning k-trees has applications in networks where it was first studied in networks, and was later shown to be NP-Complete even for k =2.Biomolecule (protein, RNA) structure prediction is a grand challenge which leads to many computation methods in bioinformatics. We model the biomolecular structure prediction problem as finding the maximum spanning k-tree on the backbone graphs, where the backbone graphs are characterized by a linear sequence of the vertices. However, most of the traditional methods are not powerful to search through the huge conformation space. This implies a strong demand for more efficient models.We prove that the problem is W[1]-hard for the objective function defined on the cliques of the input graph. For solving the problem, we show that the problem can be solved in time O(k.(n)^{k+1}(k+1)^{k+2}) for every given k and we give evidence that our algorithm is very likely to be optimal.Our algorithm also works for different objective function defined over the cliques of the k-tree, which enables pertinent characterizations of real world problems.