DMS-EPSRC: The Power of Graph Structure

这项研究项目由美国国家科学基金会和英国EPSRC共同支持。一个在美国，一个在英国，PI将在图论和理论计算机科学的界面上处理问题。指导这一研究项目的研究思路如下：一般图和不包含特定结构的图(称为诱导子图)之间的全局差异是什么？这是一个基本问题，对它的数学理解是非常有限的。该项目将研究这些配置的缺失对图的算法属性的影响：如果我们被给予关于输入的这种额外信息，哪些问题(已知通常很难)变得容易处理？该项目还将在美国和英国提供研究生培训。近年来，理论计算机科学界在设计方法方面取得了重大进展，当输入受到一定限制时，这些方法可以解决图论中的NP完全问题。这些都是美丽而强大的结果，大大加深了人们对高效算法局限性的理解。这个项目旨在将结构图理论的力量与这些最新的发展结合起来，并将它们应用于几个长期悬而未决的问题。该项目将研究排除诱导子图对诸如寻找图的色数、稳定数和团数(以及它们的加权类似物)等众所周知的算法任务的复杂性的影响。在这些方面的任何进展都将促进对由禁用诱导子图定义的图族结构的理解，有助于回答重要的公开问题，并具有重要的算法结果。该奖项反映了NSF的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

This research project is jointly supported by NSF in the US and EPSRC in the UK. The PIs, one in the US and the other in UK, will work on questions at the interface of graph theory and theoretical computer science. The line of inquiry that guides this research project is the following: what is the global difference between general graphs and graphs that do not contain particular configurations (known as an induced subgraphs)? This is a fundamental question and the mathematical understanding of it is very limited. The project will study the impact of the absence of those configurations on algorithmic properties of the graph: what questions (that are known to be difficult in general) become tractable if we are given this kind of additional information about the input? This project will also provide graduate student training both in the US and UK.In recent years significant progress has been made in the theoretical computer science community toward designing methods that address NP-complete problems in graph theory when certain restrictions are placed on the input. These are beautiful and powerful results that have significantly deepened the understanding of the limits of efficient algorithms. This project aims to combine the power of structural graph theory with these recent developments and apply them to several longstanding open questions. The project will study the impact of excluding an induced subgraph on the complexity of such well-known algorithmic tasks as finding the chromatic number, the stability number, and the clique number of a graph (as well as their weighted analogues). Progress on any of these aspects will advance the understanding of the structure of families of graphs defined by forbidden induced subgraphs, contribute to answering important open questions, and have significant algorithmic consequences.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.