TY - GEN

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

AU - Atminas, Aistis

AU - Lozin, Vadim V.

AU - Razgon, Igor

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84863100078&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-31155-0_13

DO - 10.1007/978-3-642-31155-0_13

M3 - Conference Proceeding

AN - SCOPUS:84863100078

SN - 9783642311543

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 142

EP - 152

BT - Algorithm Theory, SWAT 2012 - 13th Scandinavian Symposium and Workshops, Proceedings

T2 - 13th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2012

Y2 - 4 July 2012 through 6 July 2012

ER -