DMS-EPSRC - The Power of Graph Structure

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

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.