Projects

chaincover

chaincover finds the minimum chain cover of a graph and is written in C. Simple chain: Set of vertices i, Vi + 1, Vi + 2, ..., Vi + k> such that the degree of the vertices Vi and Vi + k is not 2 while the degree of every other vertex is 2, with k being greater than or equal to 1. What: The ... [More] program finds the minimum set of vertices in the given graph so that every simple chain in the graph at least one vertex in common with the chosen vertex set. This set is called the minimum chain cover for the given graph. Includes a graph data structure implemented using adjacency lists and parameter based random graph generation to generate test cases. How: It considers every possible k subset of vertices to see if it is possible to reach all the simple chains from the chosen set of vertices and spits out the smallest subset that satisfies this condition. Also plan to make use of other heuristic methods to improve the performance of this exact solver(See TODO). It is implemented in C and is fairly fast. Why: The problem, being reducible to and generalized from the well known Vertex Cover problem, is NP-Complete. Hence this problem is currently intractable. Proving the existence of an exact solver that can run in polynomial time amounts to proving P = NP. TODO Include a linear time approximation algorithm that does no worse than twice the size of the minimum chain cover. Use this approximation algorithm to eliminate all k subsets of size less than b/2 upfront, b being the size of the approximate minimum chain cover in the best run of the approximation algorithm on the given graph. Make changes to to allow solving the vertex cover problem as well. (Mostly easy because the chain cover problem is a generalization of the vertex cover problem) Post a graph of its performance on varied input sizes. Screenshot: [Less]