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 irst 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 ij ( ) |
a vertex operator i, represented as an integer, where 0 ≤ i ≤ t ≤ 9 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 irst 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 decreas- ing 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 irst 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、⊂ V such that the subgraph G / V、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 ! f1, 2, 3g such that for all (u, v) 2 E we have f(u) 
f(v). The chromatic sum of a graph G is the minimum sum Σv2Vf(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
The following show typical input instances. Note that you should assume each input t-parse graph its on one line. All test cases will be given from stdin/keyboard and the last cases has t = 0.
Submission and Marks
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-ile 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 inal 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 irst 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.