Graph Decompositions and their Applications
Graph decompositions have proven to be a powerful tool, both for proving theoretical properties of graphs, as well as in applications of graph theory in theoretical computer science. The proposed project looks at basic questions on graph decompositions and develops applications of graph decomposition techniques in theoretical computer science and complexity theory.
The specific research topics to be tackled lay in two primary directions. First, we consider the development of an approximate structural characterization of excluded vertex minors, a model of graph containment generalizing recent work on excluded matroid minors of Geelen, Gerards, and Whittle as well as the classic work of Robertson and Seymour on excluded graph minors. Second, we look at new approaches to proving rigorous lower bounds on proof complexity for difficult NP problems such as SAT and k-clique. The two research topics will proceed in parallel with techniques from one being applied in the other, and vice versa.
Success on each target will constitute a significant advance on the current state of the art; furthermore, progress on the proposed targets should lead to new algorithmic techniques to tackle computationally difficult problems in theoretical computer science.