DMS-EPSRC: The Power of Graph Structure

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

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.