Exact Exponential Algorithms to solve NP-Hard Problems

Abstract

The first part of the thesis is mainly a literature study of the book, ”Exact Exponential Algorithms” by Fomin and Krastch. We explain different techniques to solve computational problems through exact algorithms. The techniques are branching, dynamic programming and measure and conquer and also treewidth. These are explained using examples and di↵erent algorithms. In the second part of the thesis, we introduce the problem, Component order connectivity using some examples and ILP formulation. We also introduce it’s edge version, component order edge connectivity and parameterized version and give some results. Then we give algorithms to find the solution when the instance is tree or a bounded degree graph.