Full Title

From Graph Theory to Matroids: Algorithmic Issues and Applications

Call: Thalis: Enhancement of the interdisciplinary research and innovation with the likelihood of approaching high level researchers from abroad by conducting basic and applied research. (Ministry of Education, Lifelong Learning and Religious Affairs, Special Management Service of Business Program “Education & Lifelong Learning”)

Project Duration: 3 Years (2012 -2015)
Website: (under construction)

Short Summary

This project lies in the intersection of two of the most active and rich in deep problems areas in Discrete Mathematics, namely Graph Theory and Matroids. There are four main axes of proposed research, as reflected by the four research teams in this project, which range from the theoretical to the algorithmic. Starting from the matroids, the project aims to develop a decomposition theory for signed graphic matroids as well as recognition algorithms for the aforementioned class that will provide the means for answering some of the most important questions in this field. Furthermore the examination of important algorithmic consequences of the much celebrated Graph Minor Theory of Robertson and Seymour, extend the techniques so developed to other areas and problems. In the third axis of the project’s research the goal is to develop the first detailed polyhedral analysis of matroid intersection, thereby providing a general solid mathematical framework for the majority of discrete optimization problems, and also a polyhedral description for the most important structural theorems in matroid theory. Finally efficient exact solution algorithms will be developed and implemented using the aforementioned theoretical results, for a plethora of integer programming problems. Therefore, this research project possesses the rare characteristic of being both theoretical and applied, in the sense that the problems which proposes to solve have both a deep theoretical and applied impact. The theoretical impact will be due to the settling of various conjectures in the field as well as by providing deep structural results, while these results will also foster the development of a number of algorithms for various important combinatorial problems.