TY - GEN

T1 - Parameterized complexity of finding subgraphs with hereditary properties

AU - Khot, Subhash

AU - Raman, Venkatesh

N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2000.

PY - 2000

Y1 - 2000

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

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

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

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

U2 - 10.1007/3-540-44968-x_14

DO - 10.1007/3-540-44968-x_14

M3 - Conference contribution

AN - SCOPUS:71549142137

SN - 3540677879

SN - 9783540677871

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

SP - 137

EP - 147

BT - Computing and Combinatorics - 6th Annual International Conference, COCOON 2000, Proceedings

A2 - Du, Ding-Zhu

A2 - Eades, Peter

A2 - Estivill-Castro, Vladimir

A2 - Lin, Xuemin

A2 - Sharma, Arun

PB - Springer Verlag

T2 - 6th Annual International Conference on Computing and Combinatorics, COCOON 2000

Y2 - 26 July 2000 through 28 July 2000

ER -