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 II, 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 II includes all independent sets but not all cliques or vice versa, then the problem is hard for the parameterized class W[1] and is fixed parameter tractable otherwise. In the former case, if the forbidden set of the property is finite, we show, in fact, that the problem is W[1]-complete (see [4] for definitions). Our proofs, both of the tractability as well as the hardness ones, involve clever use of Ramsey numbers.
Part of this work was done while the first author was at IIT Bombay and visited the Institute of Mathematical Sciences, Chennai
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
L. Cai, Fixed Parameter Tractability of Graph Modification Problem for Hereditary Properties, Information Processing Letters, 58 (1996), 171–176.
R.G. Downey, M.R. Fellows, Fixed Parameter Tractability and Completeness I: Basic theory, SIAM Journal on Computing 24 (1995) 873–921.
R.G. Downey, M.R. Fellows, Fixed Parameter Tractability and Completeness II: Completeness for W[1], Theoretical Computer Science 141 (1995) 109–131.
R.G. Downey, M.R. Fellows, Parameterized Complexity, Springer Verlag New York, 1999.
R.G. Downey, M.R. Fellows, V. Raman, The Complexity of Irredundant sets Parameterized by Size, Discrete Applied Mathematics 100 (2000) 155–167.
M. R. Garey and D. S. Johnson, Problem [GT21], Computers and Intractability, A Guide to The Theory of NP-Completeness, Freeman and Company, New York, 1979.
M. C. Golumbic, Algorithmic Graph Theory and Perfect Graphs. Academic Press, New york, 1980.
Harary, Graph Theory, Addison-Wesley Publishing Company, 1969.
J. M. Lewis and M. Yannakakis, The Node-Deletion Problem for Hereditary Properties is NP-complete, Journal of Computer and System Sciences 20(2) (1980) 219–230.
M. Mahajan and V. Raman, Parameterizing above Guaranteed Values: MaxSat and MaxCut, Journal of Algorithms 31 (1999) 335–354.
A. Natanzon, R. Shamir and R. Sharan, Complexity Classification of Some Edge Modification Problems, in Proceedings of the 25th Workshop on Graph-Theoretic Concepts in Computer Science (WG’99), Ascona, Switzerland (1999); Springer Verlag Lecture Notes in Computer Science.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Khot, S., Raman, V. (2000). Parameterized Complexity of Finding Subgraphs with Hereditary Properties. In: Du, DZ., Eades, P., Estivill-Castro, V., Lin, X., Sharma, A. (eds) Computing and Combinatorics. COCOON 2000. Lecture Notes in Computer Science, vol 1858. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44968-X_14
Download citation
DOI: https://doi.org/10.1007/3-540-44968-X_14
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67787-1
Online ISBN: 978-3-540-44968-3
eBook Packages: Springer Book Archive