UNIVERSITY OF HAIFA

You are cordially invited to a CRI Haifa -- Special Graph Theory Lecture

Place:   Caesarea Rothschild Institute - University of Haifa
Room 665 Education Bldg. Univ. of Haifa
Date:    Wed. Aug.1 at 11am

Speaker: Igor Razgon, University of Leicester, UK:

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

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.

---------------------------------------------------------
Technion Math Net-2 (TECHMATH2)
Editor: Michael Cwikel   <techm@math.technion.ac.il>
Announcement from:   Martin Charles Golumbic   <golumbic@cs.haifa.ac.il>