CSC 422/CSC 522: Summer 2017
Assignment #1 Programming part [40 marks]

Due Friday May 19 at 11:00pm.

It is very important that you follow the specifications for the programming submissions. I intend to evaluate them electronically. If you do not follow the instructions, the automated grading will not work for your program.

Dominating Sets

A dominating set of a graph G is a subset S of V(G) such that every vertex of G is either in S or it has at least one neighbour in S. The problem:

Input: Graph G and integer k
Question: Does G have a dominating set of size k?

is NP-complete.

When the answer is yes, a certificate consisting of the set S can be provided and it is possible to check if this certificate is correct in polynomial time. The goal of this assignment is to write a program to check dominating set problem certificates. Your program should be written in C or C++. Please do not hesitate to come see me if you need some help.

Input format

Your program should take as input a sequence of certificates where each certificate consists of a simple undirected graph in adjacency list format followed by a proposed dominating set. Vertices of an n-vertex graph are numbered from 0 to n-1.

The adjacency list format consists of:
<number of vertices>
Then for each vertex v:
<degree of v> <neighbours of v>
A dominating set of size k is input as:
< The k integers representing the vertices in the dominating set >

For example, for this graph and the dominating set represented by the red vertices:

The input is:
3 1 5 9
2 0 2
2 1 3
2 2 4
2 3 5
3 0 4 6
2 5 7
2 6 8
2 7 9
2 0 8

0 3 5 8

Your program should permit the user to use arbitrary amount of white space and arbitrary line spacing when typing these numbers in. The input files contain only integers.

Error handling

If your program encounters an illegal graph, it should not try to read in the proposed dominating set or any more graphs. Your program should continue execution if a proposed dominating set is not correct.

Output format

The program should run in two modes. The usage will be like this:
Usage: a.out <verbose>
If verbose is set to 0 then your program should print two integers for each graph (and nothing else). The first integer for each graph is the graph number where the first graph is numbered by 1. The second integer is -1 if the graph is illegal in any way. Otherwise, the next integer is 0 if the set given is not a dominating set and 1 if it is a dominating set.

If verbose is set to 1, print the graph and if the graph is valid, the proposed dominating set. If the graph and the dominating set are valid then use
printf("%5d: OK\n", graph_number);
If your program encounters an error with the graph, print an informative message followed by
printf("Graph %5d: BAD GRAPH\n", graph_num);
If there is an error with the dominating set, print an informative error message followed by:
printf("Graph %5d: BAD CERTIFICATE\n", graph_num);

Running the program

Input MUST be from standard input and output MUST go to standard output. I am going to run it like this if I want terse output:
a.out 0 < in.txt > out.txt
and like this if I want your verbose output (detailed error messages):
a.out 1 < in.txt > out.txt

Do not ask me to type in a file name as a command line parameter.

A sample input file:

A corresponding output file with terse output:

A corresponding output file with verbose output:

Submission information

Keep your code in one file. The name of your file should be either Last_Name1.c or Last_Name1.cpp. For example, my program would be called Myrvold1.c or Myrvold1.cpp. Upload your program to connex (go to assignment #1 to find the place to submit). Do not compress, zip, gzip, tar or archive anything.

You can submit your program an unlimited number of times until the deadline. Do not use the connex option of submitting a "Draft". Draft submissions will not be graded (they are not included when I download student submissions from connex).

To make sure your code compiles and runs properly

#include <stdio.h>
#include <stdlib.h>
This ensures that the programs will run using any compiler or machine. Some compilers include these automatically. Others do not and programs without them do not compile.

Use a constant NMAX set to 100 for the maximum number of vertices:
#define NMAX 100
If NMAX is not big enough, print an error message that explains that the user should increase NMAX and recompile. Do not use malloc/free. Using repeated malloc/free calls will end up slowing the program down and could create bugs that cause memory leaks. Memory leaks are a disaster when you are working with large computations.

It is very important that your program works when I try to run it on more than one graph at a time. As part of our research efforts we want to be able to find a minimum dominating set on potentially thousands of graphs and so it is essential to have programs that work on more than one input.

All code submitted must be your original work. If you use code taken from the internet, an API, other students, previous model solutions or other sources and submit it as your own work you will not get credit for that code. Further if your source is not acknowledged, you are subject to disciplinary action according to the department policies for plagiarism.

CSC 422/522 Assignments / maintained by Wendy Myrvold / / revised May 2, 2017