Polynomial Kernels for Graph and Hypergraph Optimisation Problems

Gabriele Muciaccia

Research output: ThesisDoctoral Thesis

223 Downloads (Pure)

Abstract

When dealing with hard problems, problems which we are not able to solve in polynomial time, it is common practice to preprocess an instance to reduce its size and make the task of solving it easier. Parameterized Complexity offers a theoretical framework to prove the efficiency of preprocessing algorithms, which are called kernelizations. The underlying idea is that for every problem we identify a parameter which represents the part of the input which is 'difficult' to solve, then we try to reduce the input size and we measure the result in terms of the parameter.

Especially successful kernelizations are the ones that compute a kernel whose size is bounded by a polynomial in the parameter. In this thesis we consider some combinatorial optimisation problems on graphs and hypergraphs, and we study the existence (or non-existence) of polynomial kernels for these problems. In particular, we describe a generic kernelization for a theoretical class of graph problems, which can be used to derive the existence of a polynomial kernel for many graph problems of interest.
Original languageEnglish
QualificationPh.D.
Awarding Institution
  • Royal Holloway, University of London
Supervisors/Advisors
  • Gutin, Gregory, Supervisor
  • Yeo, Anders, Supervisor, External person
Award date1 Dec 2014
Publication statusUnpublished - 2014

Keywords

  • Parameterized Complexity
  • Kernelization
  • graph
  • optimization

Cite this