Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Assignment 3

COMP6741: Algorithms for Intractable Problems

Students: insert your names and zIDs here

1 Instructions

Assignment 3 is a group assignment.  Groups are determined by the lecturer-in-charge and each group consists of at least 3 members.

For the solutions to this assignment, you may rely on all theorems, lemmas, and results from the lecture notes. If any other works (articles, Wikipedia entries, lecture notes from other courses, etc.)  inspired your solutions, please cite them and give a list of references at the end. You may use any result you find in the literature, without re-proving it. Existing implementations and libraries may also be used, as long as their licenses allow unrestricted academic use.

If you have questions about this assignment, please post them to the Forum.

Due date. This assignment is due on Friday, 14 April 2023, at 5pm Sydney time.  Submitting x hours after the deadline, with x > 0, reduces the obtained mark by 5 · ⌈x/24⌉ marks. No submissions will be accepted 5 days (120 hours) or more after the deadline.

How to submit. There is one Bitbucket GIT repository per group. The Readme.md file in this repository describes where to put various files, including the report answering the questions below, by the submission deadline.

2 Background

The PACE challengeis an annual challenge that brings theoretical ideas from parameterized complexity into practice. This year’s challenge is to compute the twinwidth parameter of graphs, or compute an upper bound via heuristics.

2.1 Outline

In this assignment, your task revolves around writing a solver for the Heuristic Track of PACE 2023, submit a report discussing your findings, and giving a presentation about your work.

A part of the Assignment 3 mark is determined by peer grading where students are asked to grade the work of other students based on the collaboration within their own team and the presentation of other teams.

Each team is responsible for dividing the work among the team members.

2.2 Programming environment

All implementations will be done in SageMath 9.5 (or later, up to the most recent stable version, which is 9.8). It extends Python3 by adding mathematical capability from either external Python packages or inbuilt methods.  It has an extensive implementation of graphs and some graph algorithms.

In your group, decide which version of SageMath you use and how you plan to collaborate.  For example, in Ubuntu 22.04, sudo  apt  install  sagemath installs SageMath 9.5 by default.

Figure 1: This graph and its tikz representation were generated in SageMath.

Make sure to write good quality code, following general conventions, with appropriate naming, spacing, testing procedures, comments and documentation.

2.3 Expectations

It is expected that you consult the literature and use sound theoretical underpinnings of your work.  Design and discuss various heuristics for computing contraction sequences with small width. Aim for at least 3 implementations / variants. Think about preprocessing (simplification rules) and postprocessing (once we have found a contraction sequence, can we make local modifications to try to get another one with smaller width?), and randomization where we get a variety of solutions by running the algorithm multiple times.

Random numbers If you use randomization, it is recommended to use the built-in pseudo-random number generator of Python as a proxy for random number generators.  For your work to be reproducible (and to more easily debug and update results of a battery of tests), it is recommended to work with fixed seeds.

import  random

random .seed(int(5787549218))  #  using  a  seed  helps  with  reproducibility

print(random .randint(1 ,100))  # prints  the  same  integer  each  time  we  run  this  code

Experimental evaluation To test your implementations, use a small-scale test set of up to 100 instances (these should not all be random instances), describe the origin of these instances, and how you would scale up the testing for a more rigorous experimental analysis.

3 Exercises

Exercise 0. Describe how you collaborated, how you split up the work, and the contributions of each team member.    [10 points]

Exercise 1. Design heuristics for Twinwidth. What is the reasoning why these heuristics should perform well?   [20 points]

Exercise 2. Implement these heuristics, describe challenges you faced, and how you overcame them. [20 points]

Exercise 3. Describe your benchmark instances, the setup of your experimental analysis, and your testing environment. How would you scale up this experimental analysis?         [20 points]

Exercise 4. Describe your experimental results and draw conclusions about the effectiveness of the heuristics.    [20 points]

Exercise 5. Give an honest assessment how competitive your team would be at PACE 2023.  What additional steps are needed to increase your competitiveness?                   [10 points]