DMS-EPSRC - The Power of Graph Structure

图是一种数学对象，用于模拟不同领域中出现的各种问题，如计算机科学、社会科学、交通运输、电信、分子生物学、工业工程等。指导我们研究的探究路线是：一般图和不包含特定子结构的图之间的总体差异是什么？我们专注于以下问题：如果在输入上放置某些结构限制（更准确地说：某些诱导子图被禁止），那么对于一般图来说，哪些已知很难的算法问题（NP-hard，意思是不太可能有一种有效的方法来通过计算机解决它们）可以有效地解决（在多项式时间内）？无论是在离散数学还是在理论计算机科学中，理解这种现象都是一个非常有趣的问题。近年来，理论计算机科学界开发了强大的方法来解决这个问题。我们的目标是利用我们在结构图论方面的专业知识来增强和加强这些方法，并将它们应用于几个长期存在的开放问题。

Graphs are mathematical objects used to model a variety of problems arising in diverse areas such as computer science, social science, transportation, telecommunication, molecular biology, industrial engineering, etc.The line of inquiry that guides our research is: what is the global difference between general graphs and graphs that do not contain a particular substructure? We focus on the following question: what algorithmic problems that are known to be hard (NP-hard, meaning that it is highly unlikely that there will ever be an efficient way to solve them by a computer) for general graphs can be solved efficiently (in polynomial time) if certain structural restrictions are placed on the input (more precisely: certain induced subgraphs are forbidden)? Understanding this phenomenon is a very interesting question, both in discrete mathematics and in theoretical computer science. In recent years powerful methods were developed in the theoretical computer science community to address this question. Our goal is to use our expertise in structural graph theory to augment and strengthen these methods, and apply them to several long-standing open problems.