Postdoc positions are available at the Institute for Computer Science and Control (Hungarian Academy of Sciences), Budapest, Hungary, supported by the European Research Council (ERC) Consolidator Grant SYSTEMATICGRAPH: Systematic mapping of the complexity landscape of hard algorithmic graph problems" held by Dániel Marx. The positions are for one year, with the possibility of renewal.

The goal of the project is to put the search for tractable algorithmic graph problems into a systematic and methodological framework: instead of focusing on specific sporadic problems, we intend to obtain a unified algorithmic understanding by mapping the entire complexity landscape of a particular problem domain. A dichotomy theorem is a complete classification result that characterizes the complexity of each member of a family of problems: it identifies all the cases that admit efficient algorithms and proves that all the other cases are computationally hard. Achieving such a complete understanding for a family of problems requires the joint effort of algorithm design (to identify all the tractable cases) and computational complexity (to give lower bounds for the hard cases). While dichotomy theorems are common in the context of Constraint Satisfaction Problems, there is growing evidence that the theory of algorithmic graph problems have an equally rich set of classification results waiting to be discovered. The framework of parameterized complexity and fixed-parameter tractability seems to be a particularly good source of potential dichotomy theorems, but the search for polynomial-time exact or approximation algorithms can be also done in such an exhaustive manner. The project will demonstrate that complete complexity classifications are feasible for a wide range of graph problems coming from areas such as finding patterns, routing, and survivable network design, and novel algorithmic results and new levels of algorithmic understanding can be achieved even for classic and well-studied problems.

The candidates should have (or expect to have shortly) a PhD degree in Computer Science or related area; research experience at postdoctoral level is of advantage. A successful candidate should have excellent knowledge of algorithms and/or complexity. Strong background in parameterized complexity, fixed-parameter tractability, graph theory, combinatorics, or approximation is of advantage.

The review of applicants will begin immediately and continue until the positions are filled. The ideal starting date is March 1, 2018. A completed PhD degree is an administrative prerequisite for starting the position. Applications received by November 15, 2017 will receive full consideration. To apply, send a CV and a research statement by email to Dániel Marx ( dmarx at cs dot bme dot hu ) and arrange two letters of recommendation to be send to this address. Questions and informal inquiries are welcome.

Budapest ("The Pearl of the Danube") is a beautiful and livable capital city in Central Europe. The institute is located in downtown Budapest.