A vertex cover is a set of vertices, from a given graph G = (V, E), that covers all the edges in E. The VC problem is to find a set of vertices of minimal size in a given graph. In other words, chose a vertex from a graph, that vertex is either a) in the cover or b) all its neighbors most be in set. The time to find the exact set, O (2^k n); k set number, n number of vertices. For a fixed parameter k, deciding whether a graph has a Vertex Cover, of k or less, the "worst case" algorithm takes linear time. Moreover, new techniques that are emerging in the realm of Fixed Parameter Tractability led to an O (1.271^k + n^2) time algorithm. .
Objective and PILOT Scope:.
We want to investigate whether Field Programmable Gate Arrays (FPGA) would be an efficient device to perform and optimize the kernelization process on a given graph. FPGAs are very well suited to perform simple arithmetic operations on large amounts of data quickly and efficiently and therefore an ideal solution to the kernelization problem. The algorithm we have chosen to implement requires simple addition, subtraction, comparison and primitive logic operations. The primitive operations required for graph kernelization, would seem an appropriate application for exploiting FPGAs. .
The scope of this PILOT has been limited to the full design, development and verification by functional simulation of Version 1, described in following sections. This PILOT has been specifically designed to work with the Pilchard boards in the UTK ECE Department. The chosen algorithm was implemented in Very High Speed Integrated Circuit (VHSIC) Hardware Description Language (VHDL.) Three main cores were developed for this algorithm: the maskGeneratorCore, CompactionCore and an address counter. In addition, two Dual Port RAM Cores, generated by Xilinx's CoreGen software were needed for the design. .
The objective of this PILOT was not to find the Vertex Cover of a graph.