|
11:00 am, Lecture Hall 1 M.Sc Thesis Defence FPT Algorithms using Algebraic Techniques Prantar Ghosh Chennai Mathematical Institute. 28-04-17 Abstract In this survey talk we look at how algebraic techniques have been used to design fixed-parameter tractable (FPT) algorithms for various NP-hard path and packing problems. Very roughly speaking, the algorithm for each problem constructs a polynomial, each monomial of which corresponds to a solution of the input instance. Checking whether this polynomial contains at least one non-zero monomial then tells us if the instance has a solution. In each of these problems the task is to check if a substructure (for instance, a subgraph) with some specified properties is present in a given structure (for instance, a graph). In each case we define the notion of a "relaxed" substructure which can be "efficiently" encoded in terms of a polynomial in which each monomial represents a relaxed substructure. We then work in a suitable field (usually a field of characteristic 2) such that the monomials which correspond to "bad" substructures cancel out, and what remain are only the monomials corresponding to the "good" substructures that we want. This polynomial is thus an encoding of a set of solutions to the problem, and the problem has a solution if this polynomial is not identically zero. The algorithm checks for this latter condition using the Schwartz-Zippel lemma. We will also look at a variant where the bad monomials in the constructed polynomial do not necessarily cancel out, and we have to do some extra work to deduce the solution from the polynomial. We will illustrate how these techniques have been used to design fast FPT algorithms for a number of fundamental problems on set systems and graphs.
|
