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.
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.
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:
<k>
< 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:
10
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
4
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.
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);
Do not ask me to type in a file name as a command line parameter.
A sample input file:
in.txt
A corresponding output file with terse output:
out0.txt
A corresponding output file with verbose output:
out1.txt
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).
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.