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.