The proposed project consists of two interrelated research areas in graph theory: cycles and dense subgraphs. The problem of approximating the circumference of a graph is NP-hard. For most canonical NP-hard problems, either dramatically improved approximation algorithms have been devised, or strong negative results have been established, leading to a substantially improved understanding of the approximability of these problems. However, the longest cycle problem, finding the longest cycles in a graph, has resisted all attempts at devising either positive or negative results. One feasible way to study the longest cycle problem is to consider some special classes of graphs. Under this award, the PI will investigate the longest cycle problem for the following classes of graphs: Planar graphs and graphs embeddable on certain surfaces, graphs with certain forbidden minors, graphs with bounded degrees, and graphs with large degrees. Each of these four classes of graphs plays an important role in the study of graph theory. The PI and his collaborators have successfully solved a few conjectures in the areas and made significant progresses towards solving some problems in this area. He plans to work on problems surrounding a few long-standing conjectures in the area and hopes his experience will help him to solve some of the conjectures. The second component of this proposal is finding "dense" subgraphs and partitioning a graph into "dense" subgraphs. In studying web graph, experiments suggest that dense substructures correspond communities on the web, i.e. collections of web pages related to the same topic. The problem of finding dense subgraphs has received a lot attention recently. However, the PI's motivation of finding small dense subgraphs arises from two practical bioinformatics problems: Design of calcium-binding sites in proteins and Modeling the Protein Structure and Conformation Changes.
This proposed research lies in graph theory and its applications. The PI hopes the results from the first part of the project will provide a better understanding of NP-hard problems, which is one of few fundamental problems in computer science. Protein functions are associated with their structures and the cofactors, such as the metal-binding. In addition to deepening understanding the biology mechanism, detecting metal-binding sites benefits the protein design, and thereafter, protein-based drug development, biosensor, and more.
