Computing small bicliques in graphs without long induced paths and related results

Igor Razgon, University of Leicester, UK

Abstract:

Fixed-parameter algorithms allow to efficiently solve NP-hard problems. The algorithms are based on the following idea. Assume that besides the input size $n$, the problem is associated with an additional parameter $k$, often it is the output size. The runtime of such algorithm is of the form $O(f(k) n^c)$ where $f(k)$ carries all the exponential time load and $c$ is a constant independent on $k$. For example, when $c=1$, we say that the considered algorithm takes a linear time for every fixed $k$.

Problems that can be solved in this manner are called Fixed-Parameter Tractable (FPT). Similarly to the classification of P vs. NP hard problems, there is a classification of problems into those that FPT and those that are probably not. For some computational problems, their classification is a very challenging research question. One such challenging problem is the Biclique problem whose task is to test whether the given graph has a subgraph which is a Biclique of order $k$, i.e. a complete bipartite graph with $k$ vertices on each side. The problem is widely believed to be not FPT and its resistance to the investigation attempts is so notorious that some parameterized problems are characterized as Biclique-hard.

We make the first progress (to the best of our knowledge) towards resolution of this problem. In particular, we consider a restricted version of the Biclique problem by introducing an additional parameter $r$ and assuming that the considered graph does not have induced paths of length larger than $r$. We prove that under this additional parameterization the problem can be solved in a linear time for every fixed $k$ and $r$. In order to establish the algorithm for the above problem, we prove a Ramsey-like theorem stating that if a graph has a long path then this graph has either a long induced path or a large biclique. In fact, the algorithm is a direct consequence of this theorem. The result has been presented in SWAT'12 conference. It is a joint work with Aistis Atminas and Vadim Lozin. A copy of the conference paper is available at http://www.cs.le.ac.uk/people/ir45/papers/biclique-final.pdf

Our further research has revealed that the above Ramsey-like theorem is of an independent interest. In particular, we applied it in order to prove the following result related to well quasi orders. Let ${\bf Q}$ be a hereditary class of graphs where the set of forbidden induced subgraphs contains $K_q$ and $K_{r,r}$ for some $q$ and $r$ (i.e. a clique of size $q$ and a biclique of order $r$) and assume that ${\bf Q}$ is \emph{well quasi-ordered} by the \emph{induced subgraphs} relation. Then {\bf Q} has a bounded treewidth, i.e. there is a constant $c$ such that the treewidth of each graph of ${\bf Q}$ is at most $c$. This result partially confirms (even in a stronger form) the hypothesis of Thomasse that every class of graphs well quasi ordered by the induced subgraphs relation has a bounded cliquewidth.

My talk will go along the above outline. That, I will first introduce fixed-parameter algorithms, then I will describe the algorithm for the restricted biclique problem, formulate the Ramsey-like theorem and briefly present the proof idea, and finish the talk with the outline of the recent extension of the conference result. This talk will be self contained and no familiarity with any of the considered topics is needed for its understanding.