Graph Computing on Long Cycles and Small Dense Subgraphs With Applications

本课题包括图论中两个相互关联的研究领域：环和密集子图。近似图的周长是np困难的问题。对于大多数典型的np困难问题，要么已经设计出了显著改进的近似算法，要么已经建立了强烈的否定结果，从而大大提高了对这些问题的近似性的理解。然而，最长周期问题，即找出图中最长周期的问题，抵制了设计正或负结果的所有尝试。研究最长周期问题的一种可行方法是考虑一些特殊的图类。在这个奖项下，PI将研究以下类图的最长周期问题：平面图和可嵌入在某些表面上的图，具有某些禁止次次的图，具有有界度的图和具有大度的图。这四类图中的每一类在图论的研究中都起着重要的作用。PI和他的合作者已经成功地解决了该领域的一些猜想，并在解决该领域的一些问题方面取得了重大进展。他计划研究该领域一些长期存在的猜想，并希望他的经验能帮助他解决其中一些猜想。这个提议的第二个组成部分是找到“密集”子图，并将一个图划分为“密集”子图。在网络图的研究中，实验表明密集的子结构对应网络上的社区，即与同一主题相关的网页的集合。寻找密集子图的问题近年来受到了广泛的关注。然而，PI寻找小密度子图的动机源于两个实际的生物信息学问题：蛋白质中钙结合位点的设计和蛋白质结构和构象变化的建模。本课题的研究方向是图论及其应用。PI希望项目第一部分的结果能够更好地理解np困难问题，这是计算机科学中为数不多的基本问题之一。蛋白质的功能与其结构和辅助因子（如金属结合）有关。除了加深对生物学机制的理解外，检测金属结合位点有助于蛋白质设计，进而有助于基于蛋白质的药物开发，生物传感器等。

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.