Efficient Graph Minors Theory

Abstract in Lay TermsApplication no. 2018302Ecient Graphs Minors TheoryPIs: Daniel Lokshtanov, Department of Computer Science, University of California, SantaBarbara, CA, USA; Meirav Zehavi, Department of Computer Science, Ben-Gurion Universityof the Negev, Beersheba, Israel.

Design and analysis of algorithms lie at the heart of computer science. However, for a classof problems calledNP-hard problems, ecient exact algorithms seem to be beyond our reach.

Over the years, multiple paradigms have been suggested for coping withNP-hard problems. Acentral such paradigm is parameterized complexity, which connes the explosion in the runningtime to a particular parameter of the problem. The birth of parameterized complexity in theearly 1990s was inspired by one of the most impressive feats of modern mathematics, the graphminors project of Robertson and Seymour, which spans a series of over 23 papers publishedfrom 1983 to 2004. One of the main reasons the graph minors project has had so much impactis the sheer number of algorithms and algorithmic techniques that were developed as part ofit. Unfortunately, the algorithms that the graph minors theory yields are wildly impractical.

In this project, we will make the key algorithms of the graph minors project ecient. Toimplement our ambitious plan, we will have to re-shape a large part of the graph minors theory.

Therefore, even though we focus on the development of three concrete algorithms, there willbe ample opportunity|even necessity|for theory-building. The graph minors theory plays amajor role not only in parameterized complexity, but also in approximation algorithms, exactexponential-time algorithms, logic, computational geometry and property testing. Algorith-mically ecient graph minors theory will have an immense, lasting impact on all of these areassimultaneously.