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 -