This PILOT project is designed to be a proof of concept for "Triple Acceleration." Triple Acceleration (TA), a concept termed and conceived by Dr. Michael Langston, seeks to exploit three areas of Computer Science and Engineering to analyze and compute problems that arise in Graph Theory, sorting, searching, and network flow. The first component of TA focuses on fast, polytime algorithms that apply to Fixed Parameter Tractable problems. The second component is designed to exploit hardware, namely FPGAs, to accelerate the process of reducing input size and obtaining an equivalent instance of bounded size, a problem kernel. The final component of TA is designed to take advantage of UTK's Scalable Intracampus Research Grid (SinRG) to develop an unbounded parallel solution to the bounded search tree. This PILOT project focuses on the hardware component of Triple Acceleration. .
Background:.
There exists a class of problems, called the NP-Complete problems, which are not known to be solved in any realistic (polynomial) time span and considered intractable. If we use the most powerful computer, equipped with dedicated hardware and software, depending on the input size, we cannot guarantee a solution to any NP-Complete problem, no matter how much time is spent for computation. These problems are hard, yet their applications are practical and solving these problems could prove very useful. But, no theorist, algorithm designer or person has ever developed (or will likely develop) a polynomial time algorithm that solves any NP-Complete problem exactly. However, if we fix one or more input parameters to these problems, we find that an acceptable solution can be found in polynomial time, thus considered Fixed Parameter Tractable. For this PILOT, we chose to explore Vertex Cover (VC) as our prototypical problem. A brief description of the Vertex Cover problems follows. Vertex Cover is a widely known and popular NP-Complete problem.