Starting Date: June
Prerequisites: None formal, but you will need good programming skills and to be comfortable with the abstract language of graph theory and, preferably, the mathematical side of computer science.
Will results be assigned to University:
Parameterized Complexity is a research field that, by its own self-description, strives to provide practical, yet theoretically well-founded ways to deal with computationally hard problems (e.g., so-called NP-hard problems). However, the vast majority of the work in the field is purely theoretical — there is a great toolbox of interesting and powerful algorithmic methods, which have been proven to have good properties on paper, but these methods are only rarely tested out in practice. Hence there is a gap between theory and practice.
The PACE (Parameterized Algorithms and Computational Experiments) Challenge is a new implementation challenge that has as one of its goals to bridge this gap. It runs for the first time this summer. More information can be found on the following link:
https://pacechallenge.wordpress.com/
This project is a proposal for an entry in Track B of this challenge, which means developing, implementing and experimenting with algorithms for the problem known as Feedback Vertex Set: Given a graph G=(V,E), find a minimum number of vertices to remove such that the remaining graph has no cycles. This is a fundamental problem, which has been studied from many perspectives both in parameterized complexity and in computer science more broadly.
You would be working with me on implementing various algorithms for solving this problem, trying them out on benchmark instances provided at the above link, and learning from the experience to find an implementation that solves the problem as quickly as possible.
The competition ends on August 1st, and the best entries are announced at
the IPEC conference this autumn.
Please contact me (Magnus Wahlström) if you have any questions.