Dynamic Programming using Representative Families [HBNI Th87]

Abstract

This thesis studies algorithms mainly in the parameterized complexity framework. The thesis has three conceptual parts, (i) efficient computation of representative families, and its application in FPT and exact algorithms, (ii) study of Matroid Girth and Matroid Connectivity problems under various natural parameters and (iii) single exponential polynomial space FPT algorithm for Steiner Tree parameterized by the number of terminals.

Let S be a family of p sized sets over a universe U. A subfamily S' of S is called a q-representative family of S, if S' satisfies the following condition: for any q sized subset Y of U, if there is a set S_1 in S which is disjoint from Y, then there is a set S_1' in S' which is disjoint from Y. The definition of representative family can be extended to matroids. We give efficient computation of representative family both for set systems and matroids. It is demonstrated that, how the efficient construction of representative families can be a powerful tool for designing single-exponential parameterized and exact exponential time algorithms. The applications of our approach include fastest known parameterized (and exact) algorithms for Long Directed Cycle, Minimum Equivalent Graph, "connectivity" problems such as Steiner Tree on graphs of treewidth at most t and Multilinear Monomial Testing. These methods are also used to resolve parameterized complexity of graph editing problems.

Matroid Girth and Matroid Connectivity problems are studied on linear matroids representable over a field F_q in the parameterized complexity framework. The following parameters are considered; (i) solution size, k, (ii) rank(M), and (iii) rank(M) + q, where M is the input matroid. It is shown that these problems are unlikely to be in FPT when parameterized by k or rank(M). Fast FPT algorithm is given for these problems when parameterized by rank(M) + q. Another problem considered in this thesis is weighted Steiner Tree problem parameterized by the number of terminals and gives the first single-exponential time, polynomial-space FPT algorithm for the problem.