Biclique Partition Problem

Abstract

A lot of problems that arise in nature can be modelled using graphs. In this thesis, we look at one such problem from display optimization which can be articulated through Biclique Partition problem on Bipartite graphs(BPP). In BPP, given an arbitrary bipartite graph G and an integer k, we have to determine whether there exists a partition of the edge set of G of size k such that each part in the partition is a complete bipartite subgraph. It has been proven that this problem is NP-complete but xed parameter tractable with exponential kernel. In this thesis, we try to answer if the size of the kernel can be bettered. To do this, we explore tools from partially ordered sets. We present results on how partially ordered sets can induce structures in the solution instances and how these structures can lead to a better kernel. We also state and prove how the previous kernel does not lead to a polynomial kernel. This gives an incentive to look at certain graph classes and answer if on them BPP is polynomial time solvable or not. This helps us in understanding properties crucial in determining solution. We present new results in this direction. In particular, we prove that BPP is NP-hard on perfect elimination bipartite graph.