The approximation of maximum subgraph problems

, and . Automata, Languages and Programming, page 40--51. Berlin, Heidelberg, Springer Berlin Heidelberg, (1993)


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.

Links and resources

BibTeX key:
search on:

Comments and Reviews  

There is no review or comment yet. You can write one!


Cite this publication