Graph Structure Theory and Applications to Algorithms

点击翻译按钮获取中文摘要

The central theme of this proposal is graph structure theory and its applications to algorithms. More specifically, the PI will investigate the structure of graphs pertaining to the graph minor inclusion and its much less understood counterpart for directed graphs. Recent work of the PI suggests that it should be possible to obtain much improved bounds in key results of the Graph Minors theory. Such improved bounds will have immediate applications to the design of efficient algorithms. For directed graphs the main questions are whether the so-called cylindrical grid conjecture is true, and whether the algorithms for digraphs of bounded tree-width that are currently known can be improved to become fixed parameter tractable. The cylindrical grid conjecture seems to be both a fundamental mathematical problem as well as one that could potentially unlock many algorithmic applications. The PI also proposes a new approach to attacking Negami's planar cover conjecture, a problem from 1988 that has received a considerable amount of attention. The original motivation came from computer science, the idea being that if a graph G covers a graph H, then the connections of H can be simulated by G, and yet G could potentially have a simpler structure. Negami's conjecture would characterize graphs that have a planar cover.This work falls within the area of graph theory, and is closely related to theoretical computer science and mathematical programming (operations research). A graph is an abstract mathematical notion used to model networks, such as telephone networks, transportation networks or the Internet. Various problems arise in the study of such networks, and this proposal is concerned with problems of structural nature. Why do some networks possess certain specific desirable properties, and others do not? A satisfactory answer can have many applications, ranging from better understanding of the underlying structure, to the design of efficient algorithms, to practical computations. For instance, one such question answered earlier by the PI settles a question of Georgia Polya from 1913, it also solves a different problem that baffled theoretical computer scientists for quarter of a century, and has applications in economics.