Project - Task 3

You and your team were given one of the settings from here. You have formalized the problem in the first task and designed an exact solver for it using Branch-and-Bound in the second task. In the third task you have flexibility to take the project in the direction you want.

Guidelines

• The third task is the final one. It was originally planned to be in two parts.
• You can freely choose a direction into which you further explore your problem. Suggestions can be found below. Depending on your problem, some of the goals may be more suitable, others less; some may be harder and others easier.
• The work for this task should be a bit more than in each of the previous tasks. As a rough guideline, aim for 8-10 pages. If for example there is a straight-forward reduction showing NP-hardness of your problem and this does not feel like a significant enough contribution, then add more goals.
• When working on either a theoretical or practical goal below, you may encounter unexpected obstacles or outcomes. Your report can also be on a failed attempt and an interpretation of why it did not work.
• If you do not manage to prove hardness, try to find a generalization of your problem for which you can show hardness.
• If you do not manage to design an FPT algorithm, either add more parameters, assume that some parameters are constant, or restrict the problem by removing features.

Possible goals (choose)

• prove NP-hardness
• prove parameterized hardness under ETH for your problem
• prove that for solution size or other natural parameter (or a combination of several) there exists an FPT algorithm
• prove via dynamic programming or Courcelle’s Theorem that your problem has an FPT algorithm parameterized by treewidth
• implement your Branch-and-Bound algorithm or another exact algorithm
  • decide on benchmark instances and test your algorithm on them
  • interpret the results of the experiments

Submission

Your submission is a report in PDF format. Please submit a joint report of all 3 tasks together. You may revise the previous tasks. An appropriate length for task 3 (without the others) is 8-10 pages. It is highly recommended to write this report using LaTeX. The report should have one introduction for all tasks together and should generally read as one cohesive document.

You will submit a draft on ItsLearning. On this draft you will get feedback, which you can incorporate afterwards. The final report will consist of revised versions of the drafts for each of the 4 tasks. Although you receive feedback for each draft, only the final report will be graded.