Beyond-P: Algorithm Design and Analysis Beyond the Polynomial Time

Each team will involve 4 members to the proposal, among them 3 PhD students and 1 permanen researcher (8 researchers in total). From the LIRMM-team the students will be Lucas Isenmann, Abhijat Sarma, and Jocelyn Thiebaut, while from the UOB-team the students will be Kristine Vitting Klinkby Knudsen, Kirill Simonov, and Strømmme Torstein. From the LIRMM-team the senior researcher is Prof. Dimitrios Thilikos, while from the UiB-team the permanent researcher is Prof. Fedor Fomin. In order to establish links for further collaboration, we propose to initiate the study in the following directions Direction 1: (Exact & mono-variate) Moving beyond the limits of polynomial-time computation by exploring the further possibilities and powerfulness of exponential algorithms for computing exact solutions of NP-hard problems and by providing more mathematical and computational tools, as well as structural results. Direction 2: (Exact & multi-variate) Investigating further the multi-variate algorithmic approach and developing generic techniques for parameterized algorithm design and analysis. In particular, the study of kernelization is an important ingredient in this direction. Direction 3: (Approximate & mono-variate) Going beyond the limits of polynomial-time approximability by exploring moderately exponential approximation and by building tools able to solve problems not amenable to polynomial-time approximation. Direction 4: (Approximate & multi-variate) Combining both the multi-variate and the approximation approaches. This direction, still being in an early stage, appears to offer a multitude of theoretical challenges that have not been investigated so far. These four directions will form the basis for more fundamental cooperation.