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.
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
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.
my wechat：_0206girl
Don't hesitate to contact me
