Linear time algorithm for computing a small biclique in graphs without long induced paths
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.
Official URL: http://dx.doi.org/10.1007/978-3-642-31155-0_13
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|
|Place of Publication:||London|
|Book Title:||Algorithm Theory – SWAT 2012|
|Page Range:||pp. 142-152|
|Description:||Algorithm Theory – SWAT 2012 : 13th Scandinavian Symposium and Workshops, Helsinki, Finland, July 4-6, 2012. Proceedings|
Actions (login required)