Computer Science 720 S1 – (2021)
Assignment 2 (Bounded Treewidth Algorithms)
Due: Friday, April 23, 11:59pm
Requirements
In this assignment you will learn how to use and understand the t-parse data structure for graphs
of bounded pathwidth/treewidth. We will do some basic programming regarding the t-parse repre-
sentation of graphs.
We use the following t-parse input format for graphs of bounded treewidth. 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 ‘)’.
Each ’(’ except first token must be preceded by a parenthesis and ’)’ may be succeeded “up the parse
tree” by pathwidth operators. 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.
For each part of the assignment the input will consist of several test cases, each on its own line. The
input is terminated by a t = 0 case, which is also processed.
1
Problem 1: Parse and Extract Graph
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
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.
The following show typical input instances and expected output. Note that you can assume that
each input graph fits on one line.
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 ) )
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
2
Problem 2: Weighted Independent Sets
In this part of the assignment you will learn how to exploit the structure of bounded pathwidth/treewidth
for a known hard graph problem:
Problem: Degree-Weighted Independent Set (DWIS)
Input: (undirected) Graph G = (V,E)
Question: Let the weight of each vertex be its degree (number of vertex neighbors).
What is the largest sum of vertex weights over all independent sets of vertices?
That is, maxV ′⊆V
∑
v∈V ′ deg(v) where for all {v1, v2} ⊆ V ′ we have (v1, v2) 6∈ E.
Your main requirements are to do the following.
1. For input graph of bounded pathwidth (in t-parse representation described above), determine
the DWIS.
2. Extend your linear-time program for item 1 for input of bounded treewidth.
The following show typical input instances. Again you can assume each input t-parse graph fits on
one line.
Sample input output
2 ( 10 21 1 10 21 0 10 20 2 20 21 ) 7
2 ( ( 10 21 1 10 21 1 21 10 ) ( 21 2 21 20 ) ) 7
4 ( ( 10 20 30 41 4 41 31 ) ( ( 40 21 32 42 ) ( 10 0 43 10 20 ) ) ) 6
3 ( 32 31 30 20 21 10 0 10 20 21 1 10 21 1 10 21 1 10 0 10 30 20 ) 11
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 ) 16
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 ) 14
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 ) 13
0 ( 0 0 ) 0
Submission and Marks
All solutions should be submitted to the automarker http://automarker.cs.auckland.ac.nz/.
All input should be taken from the keyboard (stdin) and output to the console (stdout). There will
be two test cases for each of our problems.
The first data set will only contain pathwidth t-parses and are worth 3 marks. The slightly harder
treewidth t-parse input cases will be worth 2 marks each. This assignment is worth 10% of your
final grade, where both Problems 1 and 2 are worth 5 marks each. Partial marks may be awarded
later (after due date) if determined to be close to correct.
3

































































































学霸联盟