Parameterized complexity of finding subgraphs with hereditary properties

Subhash Khot, Venkatesh Raman

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We consider the parameterized complexity of the following problem under the framework introduced by Downey and Fellows[4]: Given a graph G, an integer parameter k and a non-trivial hereditary property, are there k vertices of G that induce a subgraph with property II? This problem has been proved NP-hard by Lewis and Yannakakis [9]. We show that if includes all independent sets but not all cliques or vice versa, then the problem is hard for the parameterized class W [1] and is xed parameter tractable otherwise. In the former case, if the forbidden set of the property is nite, we show, in fact, that the problem is W[1]-complete (see [4] for denitions). Our proofs, both of the tractability as well as the hardness ones, involve clever use of Ramsey numbers.

Original languageEnglish (US)
Title of host publicationComputing and Combinatorics - 6th Annual International Conference, COCOON 2000, Proceedings
EditorsDing-Zhu Du, Peter Eades, Vladimir Estivill-Castro, Xuemin Lin, Arun Sharma
PublisherSpringer Verlag
Pages137-147
Number of pages11
ISBN (Print)3540677879, 9783540677871
DOIs
StatePublished - 2000
Event6th Annual International Conference on Computing and Combinatorics, COCOON 2000 - Sydney, Australia
Duration: Jul 26 2000Jul 28 2000

Publication series

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

Other

Other6th Annual International Conference on Computing and Combinatorics, COCOON 2000
CountryAustralia
CitySydney
Period7/26/007/28/00

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Parameterized complexity of finding subgraphs with hereditary properties'. Together they form a unique fingerprint.

Cite this