As implementing approximation algorithms for NP-hard problems seems to be impractical, a fixed-parameter algorithm is one that provides an optimal solution to a discrete combinatorial problem. The fundamental idea is to re-strict the corresponding, seemingly unavoidable, combinatorial explosion that causes the exponential growth in the running time of certain problemspecific parameters. An odd cycle transversal (OCT) is a subset of the vertices of a graph G that hits all the odd cycles in G. Clearly the deletion of such a vertex set leaves a bipartite graph. Thus the problem of finding an odd cycle transversal of min-imum cardinality is just the classical graph bipartization problem. A feedback vertex set F (briefly, FVS) for G is a set of vertices in G such that every directed cycle in G contains at least one vertex in F, or equivalently, that the removal of F from the graph G leaves a directed acyclic graph (i.e., a DAG). Odd Cycle Transversal and Feedback Vertex Sets are the NP-Hard problems which can be practically implemented by fixed parameter algorithms. This re-port is an study of algorithms for OCT and FVS. The study shows the influence of various factors, such as number of nodes, optimum solution size, edge density, and parameter size, on the performance of the FPT algorithm.
Graph, Odd Cycle Transversals, Feedback vertex Sets, Bipartization
