Minimum 1-regular bipartite graph deletion set problem

Abstract

This thesis presents an algorithmic solution to a certain N P -hard problem called ND( 1 ) wherein the solution is determined through two di⇥erent orthogonal approaches : (I) Com- binatorial Optimization and (II) Graph Theoretic Optimization. The author has considered ND( 1 ) in two di⇥erent settings, solved it with two di⇥erent approaches, and obtained matching (tight) bounds in both cases - hinting at the equivalence of the two approaches taken. In approach (I), the author begins by explaining some basic concepts of N P -hardness and Approximation Algorithms in reference to ND( 1 ), followed by a brief look at the Primal-Dual Algorithm. The next two chapters in part (I) go on to formally detail ND( and its proposed 2 1 ), optimal solution respectively. A largely similar sequence is followed in part (II), wherein the author additionally explains some graph (and hypergraph) terminol- ogy, followed by reformulating ND( a2 1 ) in di⇥erent terms. The final chapter then proposes approximation algorithm for the same. Keywords : Approximation Algorithms, N P -hardness, Node-Deletion Problem, Matroids, Primal-Dual Algorithm, Graph, Hypergraph, Greedy Algorithm.