Linear time algorithm for computing a small biclique in graphs without long induced paths

Aistis Atminas*, Vadim V. Lozin, Igor Razgon

*Corresponding author for this work

Research output: Chapter in Book or Report/Conference proceedingConference Proceedingpeer-review

27 Citations (Scopus)


The biclique problem asks, given a graph G and a parameter k, whether G has a complete bipartite subgraph of k vertices in each part (a biclique of order k). Fixed-parameter tractability of this problem is a longstanding open question in parameterized complexity that received a lot of attention from the community. In this paper we consider a restricted version of this problem by introducing an additional parameter s and assuming that G does not have induced (i.e. chordless) paths of length s. We prove that under this parameterization the problem becomes fixed-parameter linear. The main tool in our proof is a Ramsey-type theorem stating that a graph with a long (not necessarily induced) path contains either a long induced path or a large biclique.

Original languageEnglish
Title of host publicationAlgorithm Theory, SWAT 2012 - 13th Scandinavian Symposium and Workshops, Proceedings
Number of pages11
Publication statusPublished - 2012
Externally publishedYes
Event13th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2012 - Helsinki, Finland
Duration: 4 Jul 20126 Jul 2012

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7357 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference13th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2012

Cite this