COMPSCI 720 : Advanced Design and Analysis of Algorithms

Computer Science 720 S1 – (2024)

Assignment 1 (Bound Combinatorial Width Algorithms)

Requirements

For this assignment we use the following t-parse input format for graphs of bounded treewidth for four separate tasks.

The first token will be a positive integer t ≤ 9 denoting the pathwidth/treewidth of the graph (i.e., it indicates a t-parse will follow). The interpretation for the remaining tokens are given in the next table.

token	semantic meaning
i	a vertex operator i, represented as an integer, where 0 ≤ i ≤ t ≤ 9
ij	an edge operator (i, j) where t ≥ i > j ≥ 0 (note: no space between i and j)
(	a begin marker for a pathwidth t-parse (can be nested for treewidth t-parses)
)	an end marker for a pathwidth/treewidth t-parse

Thus, if you read/encounter the two tokens ‘)’ and ‘(’ in sequence then this denotes a circle plus ⊕ operator. Note that it is guaranteed that each right token ‘(’ will have a matched left token ‘)’.

We assume boundary vertices 0, 1, . . . , t precede the first token of a pathwidth t-parse (and these empty boundaried graph axioms are not given in the input format). Assume left-associativity for all operators and at least one space between each of them, including the parentheses.

Input taken from stdin/keyboard is terminated by a t = 0 case, which is also processed. You print your output to the stdout/console.

Tasks Required

Task 1 You need to read in each graph and output its degree sequence (space separated) in decreasing sorted order. Note that we are interested in the degrees of the vertices of a simple graph (multi-edges should be ignored).

Task 2 You need to output an adjacency list representation using a sorted ‘CompSci 220 graph format’. Here the first line is an integer n representing the order of the graph. The next n lines consist of a (sorted integer) adjacency lists, for vertices indexed 0 to n − 1, of neighbor indices. To have unique isomorphic representation of the graph, the vertex indices are assigned labels to vertices in the same order as the new vertex operators appear in the t-parse from left-to-right.

Task 3 Recall the Vertex Cover problem for a graph G = (V, E), as discussed in Lecture 11, is the mininum number of vertices for a subset V 0 ⊂ V such that the subgraph G \ V 0 has no edges.

You may either implement the algorithm we covered in class or develop your own solution.

Task 4 For this part you need to develop bounded pathwidth/treewidth soluton for a known NP-hard graph problem: 3-Chromatic Sum. Here we want to decide if a t-parse representing a graph can be colored with at most 3 colors and if so output its chromatic sum, otherwise output ‘None’ .

A graph G = (V, E) is 3-colorable if there is a function (e.g. proper coloring) f : V → {1, 2, 3} such that for all (u, v) ∈ E we have f(u) = f(v). The chromatic sum of a graph G is the minimum sum Σv∈V f(v) of a proper coloring f of G. Note the minimum number of colors needed (chromatic number) may not necessarily correspond with its minimum chromatic sum as shown in the following example. The 2-coloring on the left has a sum of 12 while the 3- coloring on the right has a smaller sum of 11.

Examples

Due: Saturday, April 6 (11.59pm).

All solutions should be submitted to http://www.cs.auckland.ac.nz/automated-marker for each of these four tasks. Your single-source-file programs should use one of the valid programming language extension allowed. Please read the automarker help/FAQ page. Develop and program your own solutions (e.g. don’t search the Internet or share code with fellow classmates). You are allowed to submit up to 8 times before a 20% penalty per task is applied.

This assignment is worth 15% of your final grade but marked out of a total of 20 marks. Each task will have two sets of test cases where one of them contains only of the easier pathwidth t-parses. It is recommended to first pass those test cases before submitting the harder treewidth t-parse cases.

The marks awarded per test cases range from 4 marks to 1 mark (4,3,3,3,2,2,2,1, as indicated on the automarker scoreboard). Here, more marks are intentionally given for the easier tasks. A small amount of partial credit may be given if you are close to getting all test cases correct for a task.