Atminas, Aistis, Lozin, Vadim V. and Razgon, Igor (2012) Linear time algorithm for computing a small biclique in graphs without long induced paths. In: Algorithm Theory – SWAT 2012. Algorithm Theory – SWAT 2012 Book Subtitle 13th Scandinavian Symposium and Workshops, Helsinki, Finland, July 4-6, 2012. Proceedings, Vol.7357 . London : Springer, pp. 142-152.

Full text not available from this repository.

Abstract

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.

Item Type:	Book Item
Divisions:	Faculty of Science > Mathematics
Series Name:	Algorithm Theory – SWAT 2012 Book Subtitle 13th Scandinavian Symposium and Workshops, Helsinki, Finland, July 4-6, 2012. Proceedings
Publisher:	Springer
Place of Publication:	London
ISSN:	0302-9743
Book Title:	Algorithm Theory – SWAT 2012
Date:	2012
Volume:	Vol.7357
Page Range:	pp. 142-152
Identification Number:	10.1007/978-3-642-31155-0_13
Status:	Peer Reviewed
Publication Status:	Published
Description:	Algorithm Theory – SWAT 2012 : 13th Scandinavian Symposium and Workshops, Helsinki, Finland, July 4-6, 2012. Proceedings
URI:	http://wrap.warwick.ac.uk/id/eprint/48956

Request changes to a record

Actions (login required)

View Item