TY - JOUR
T1 - Parameterized complexity of finding subgraphs with hereditary properties
AU - Khot, Subhash
AU - Raman, Venkatesh
N1 - Funding Information:
Part of this work was done while the %rst author was at IIT Bombay and visited the Institute of Mathematical Sciences, Chennai. Part of the second author’s research was supported by a DST-DAAD grant. ∗Corresponding author. E-mail addresses: [email protected] (S. Khot), [email protected] (V. Raman).
PY - 2002/10/30
Y1 - 2002/10/30
N2 - We consider the parameterized complexity of the following problem under the framework introduced by Downey and Fellows: Given a graph G, an integer parameter k and a nontrivial hereditary property Π, are there k vertices of G that induce a subgraph with property Π? This problem has been proved NP-hard by Lewis and Yannakakis. We show that if Π includes all trivial graphs but not all complete graphs or vice versa, then the problem is complete for the parameterized class W[1] and is fixed parameter tractable otherwise. Our proofs of both the tractability and hardness involve nontrivial use of the theory of Ramsey numbers.
AB - We consider the parameterized complexity of the following problem under the framework introduced by Downey and Fellows: Given a graph G, an integer parameter k and a nontrivial hereditary property Π, are there k vertices of G that induce a subgraph with property Π? This problem has been proved NP-hard by Lewis and Yannakakis. We show that if Π includes all trivial graphs but not all complete graphs or vice versa, then the problem is complete for the parameterized class W[1] and is fixed parameter tractable otherwise. Our proofs of both the tractability and hardness involve nontrivial use of the theory of Ramsey numbers.
KW - Hereditary properties
KW - Parameterized complexity
KW - Ramsey numbers
UR - http://www.scopus.com/inward/record.url?scp=0037202068&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0037202068&partnerID=8YFLogxK
U2 - 10.1016/S0304-3975(01)00414-5
DO - 10.1016/S0304-3975(01)00414-5
M3 - Conference article
AN - SCOPUS:0037202068
SN - 0304-3975
VL - 289
SP - 997
EP - 1008
JO - Theoretical Computer Science
JF - Theoretical Computer Science
IS - 2
T2 - Computing and Combinatorics (COCOON 2000)
Y2 - 1 July 2000 through 1 July 2000
ER -