Ricerc@Sapienza

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 is a continuation of the 2018 ATENEO Progetto Medie with the same title, building and expanding on the work accomplished in the 2018 project to develop a general decomposition theorem for graphs under vertex minors and extend these techniques to problems 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. Under the 2018 project, we have developed tools for such a structure theorem and proved several special cases of the conjecture. The proposed work extends this foundation with the goal or proving a general structure theorem.

The second main line of research looks 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.