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 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 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 ′ ⊂ 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.
1
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) 6= 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
The following show typical input instances. Note that you should assume each input t-parse graph
fits on one line. All test cases will be given from stdin/keyboard and the last cases has t = 0.
Tasks 1 and 3 sample input
2 ( 10 21 1 10 21 0 10 20 2 20 21 )
2 ( ( 10 21 1 10 21 1 21 10 ) ( 21 2 21 20 ) )
4 ( ( 10 20 30 41 4 41 31 ) ( ( 40 21 32 42 ) ( 10 0 43 10 20 ) ) )
3 ( 32 31 30 20 21 10 0 10 20 21 1 10 21 1 10 21 1 10 0 10 30 20 )
2 ( 21 2 21 2 21 20 1 10 1 10 1 21 1 10 2 21 1 10 21 2 21 1 10 2 20 0 20 10 )
3 ( ( 30 32 21 10 1 10 21 2 21 32 1 21 10 31 1 21 10 31 ) ( 20 21 32 2 21 32 ) 0 21 10 30 20 )
4 ( 10 20 30 40 43 21 32 2 20 21 42 0 30 40 10 2 21 3 30 31 4 41 43 42 40 )
0 ( )
Task 1 smple output
4 3 3 2 2 2
4 4 3 2 2 1
6 4 4 4 4 1 1
7 5 4 4 3 3 2 2 2
7 3 3 3 2 2 2 2 2 1 1 1 1 1 1
7 6 5 5 3 3 3 3 3 2
7 5 5 4 4 4 3 3 3 2
0
Task 3 smple output
3
3
4
5
6
5
6
0
2
Tasks 2 and 4 sample input
2 ( 10 21 1 10 21 0 10 20 2 20 21 )
2 ( ( 10 21 1 10 21 1 21 10 ) ( 21 2 21 20 ) ( 10 ) )
4 ( ( 10 20 30 41 4 41 31 ) ( ( 40 21 32 42 ) ( 10 0 43 10 20 ) ) )
0 ( ( 0 ) ( 0 0 ) )
Task 2 sample output
6
1 3
0 2
1 3 4
0 2 4 5
2 3 5
3 4
6
1 2 3 4
0 2
0 1 3 4
0 2
0 2 5
4
7
1 2 3 5
0 2 3 4 5 6
0 1 3 5
0 1 2 5
1
0 1 2 3
1
4
Task 4 sample output
10
10
None
4
3
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-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.