%0 Conference Paper %1 10.1007/3-540-56939-1_60 %A Lund, Carsten %A Yannakakis, Mihalis %B Automata, Languages and Programming %C Berlin, Heidelberg %D 1993 %E Lingas, Andrzej %E Karlsson, Rolf %E Carlsson, Svante %I Springer Berlin Heidelberg %K approximation node_deletion_problem np_complete %P 40--51 %T The approximation of maximum subgraph problems %X We consider the following class of problems: given a graph, find the maximum number of nodes inducing a subgraph that satisfies a desired property $\pi$, such as planar, acyclic, bipartite, etc. We show that this problem is hard to approximate for any property $\pi$ on directed or undirected graphs that is nontrivial and hereditary on induced subgraphs. %@ 978-3-540-47826-3

@inproceedings{10.1007/3-540-56939-1_60, abstract = {We consider the following class of problems: given a graph, find the maximum number of nodes inducing a subgraph that satisfies a desired property $\pi$, such as planar, acyclic, bipartite, etc. We show that this problem is hard to approximate for any property $\pi$ on directed or undirected graphs that is nontrivial and hereditary on induced subgraphs.}, added-at = {2019-06-05T13:33:33.000+0200}, address = {Berlin, Heidelberg}, author = {Lund, Carsten and Yannakakis, Mihalis}, biburl = {https://www.bibsonomy.org/bibtex/2ec2153051ac1dcf1e37678e2a4182864/duerrschnabel}, booktitle = {Automata, Languages and Programming}, editor = {Lingas, Andrzej and Karlsson, Rolf and Carlsson, Svante}, interhash = {182f4ca38b3aadd66f5b5000a10491c1}, intrahash = {ec2153051ac1dcf1e37678e2a4182864}, isbn = {978-3-540-47826-3}, keywords = {approximation node_deletion_problem np_complete}, pages = {40--51}, publisher = {Springer Berlin Heidelberg}, timestamp = {2019-06-05T13:33:33.000+0200}, title = {The approximation of maximum subgraph problems}, year = 1993 }