Graph Structure Theory and Applications to Algorithms

这项提议的中心主题是图结构理论及其在算法中的应用。更具体地说，PI将研究与图的次要包含有关的图的结构，以及关于有向图的更少被理解的对应物。PI最近的工作表明，应该有可能在图的子集理论的关键结果中获得更好的界。这种改进的界将立即应用于高效算法的设计。对于有向图，主要的问题是所谓的柱面网格猜想是否成立，以及是否可以改进现有的有界树宽有向图的算法，使之成为固定参数易处理的算法。柱面网格猜想似乎既是一个基本的数学问题，也是一个可能解开许多算法应用的潜在问题。PI还提出了一种新的方法来攻击Negami的平面覆盖猜想，这个问题从1988年开始就受到了相当大的关注。最初的动机来自计算机科学，其想法是如果一个图G覆盖一个图H，那么H的连接可以用G来模拟，而G可能有一个更简单的结构。Negami猜想将刻画具有平面覆盖的图。这项工作属于图论领域，与理论计算机科学和数学规划(运筹学)密切相关。图是一种抽象的数学概念，用于对电话网络、交通网络或互联网等网络进行建模。在对这类网络的研究中出现了各种问题，而本建议涉及的是结构性问题。为什么有些网络拥有某些特定的理想属性，而其他网络则没有？一个令人满意的答案可以有很多应用，从更好地理解底层结构，到设计有效的算法，再到实际的计算。例如，PI早些时候回答的一个问题解决了1913年乔治亚·波利亚的一个问题，它也解决了另一个困扰理论计算机科学家25年的问题，并在经济学中有应用。

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.